思想
树形DP计算最大独立集——选出树中尽量多的点,使得任何两个节点均不相邻。
代码
import java.io.*;
import java.util.Arrays;
public class Main{
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static int N = 400010, idx = 0;
static int[][] f = new int[N][2];
static int[] h = new int[N];
static int[] e = new int[N];
static int[] ne = new int[N];
public static int nextInt()throws IOException{
in.nextToken();
return (int)in.nval;
}
public static void add(int a, int b){
e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}
public static void dfs(int u, int fa){
f[u][1] = 1;
f[u][0] = 0;
for(int i=h[u]; i!=-1; i=ne[i]){
int j = e[i];
if(j==fa) continue;
dfs(j, u);
f[u][1] += f[j][0];
f[u][0] += Math.max(f[j][1], f[j][0]);
}
}
public static void main(String[] args)throws IOException{
int n = nextInt();
Arrays.fill(h, -1);
for(int i=1; i<n; i++){
int a = nextInt(), b = nextInt();
add(b, a);
add(a, b);
}
dfs(1, -1);
out.println(Math.max(f[1][1], f[1][0]));
out.flush();
out.close();
}
}