NTPFECT - Đại diện hoàn hảo

Tác giả: skyvn97

Ngôn ngữ: Java

import java.util.*;
import java.lang.*;
import java.io.*;
public class Main {
	public static void main(String args[]) {
		InputStream inputStream=System.in;
		OutputStream outputStream=System.out;
		InputReader in=new InputReader(inputStream);
		PrintWriter out=new PrintWriter(outputStream);
		while (true) {
			int n=in.nextInt();
			if (n==0) break;
			NTPFECT solver=new NTPFECT(n);
			solver.solve(in,out);
		}
		out.close();
	}
}
class NTPFECT {
	private static final int INF=(int)1e9+7;
	class Node {
		List<Integer> adj;
		int par;
		int[] dp;
		public Node() {
		 	adj=new ArrayList<Integer>();
			par=0;
			dp=new int[3];
			Arrays.fill(dp,0);
		}
	}
	private int n;
	private int[] vstPos;
	private Node[] node;
	public NTPFECT(int n) {
		this.n=n;
		vstPos=new int[n];
		node=new Node[n+1];
		for (int i=1;i<=n;i=i+1) node[i]=new Node();
	}
	private void loadtree(InputReader in) {
		for (int i=0;i<n-1;i=i+1) {
			int u=in.nextInt();
			int v=in.nextInt();
			node[u].adj.add(v);
			node[v].adj.add(u);
		}
	}
	private void bfs() {
		int nVst=0;
		Queue<Integer> q=new LinkedList<Integer>();
		q.add(1);
		while (!q.isEmpty()) {
			int u=q.remove();
			vstPos[nVst++]=u;
			for (int v: node[u].adj) if (v!=node[u].par) {
				node[v].par=u;
				q.add(v);
			}
		}
	}
	private void calc(int u) {
		boolean leaf=true;
		boolean need=true;
		int minChange=INF;
		for (int v: node[u].adj) if (v!=node[u].par) {
			leaf=false;
			node[u].dp[0]+=node[v].dp[1];
			node[u].dp[1]+=Math.min(node[v].dp[1],node[v].dp[2]);
			if (node[v].dp[2]<=node[v].dp[1]) need=false;
			else minChange=Math.min(minChange,node[v].dp[2]-node[v].dp[1]);
			node[u].dp[2]+=Math.min(node[v].dp[0],Math.min(node[v].dp[1],node[v].dp[2]));
			for (int i=0;i<3;i=i+1) node[u].dp[i]=Math.min(node[u].dp[i],INF);
		}
		if (leaf) {
			node[u].dp[0]=0;
			node[u].dp[1]=INF;
			node[u].dp[2]=1;
		} else {
			if (need) node[u].dp[1]+=minChange;
			node[u].dp[2]++;
		}
	}
	private void answer(PrintWriter out) {
		for (int i=n-1;i>=0;i=i-1) calc(vstPos[i]);
		out.println(Math.min(node[1].dp[1],node[1].dp[2]));
	}
	public void solve(InputReader in,PrintWriter out) {
		loadtree(in);
		bfs();
		answer(out);
	}
}
class InputReader {
	public BufferedReader reader;
	public StringTokenizer tokenizer;
	public InputReader(InputStream stream) {
        reader=new BufferedReader(new InputStreamReader(stream),32768);
        tokenizer=null;
    }
    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }
    public int nextInt() {
        return Integer.parseInt(next());
    }
    public long nextLong() {
    	return Long.parseLong(next());
    }
}

Download