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());
}
}