fork download
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. public class Main {
  5. static List<Integer>[] graph;
  6. static int[][] dp;
  7.  
  8. public static void main(String[] args) throws IOException {
  9. String[] firstLine = br.readLine().split(" ");
  10. int n = Integer.parseInt(firstLine[0]);
  11. int s = Integer.parseInt(firstLine[1]);
  12.  
  13. graph = new ArrayList[n + 1];
  14. for (int i = 1; i <= n; i++) {
  15. graph[i] = new ArrayList<>();
  16. }
  17.  
  18. for (int i = 0; i < n - 1; i++) {
  19. String[] edge = br.readLine().split(" ");
  20. int u = Integer.parseInt(edge[0]);
  21. int v = Integer.parseInt(edge[1]);
  22. graph[u].add(v);
  23. graph[v].add(u);
  24. }
  25.  
  26. dp = new int[n + 1][2];
  27. dfs(s, 0);
  28.  
  29. System.out.println(dp[s][1]);
  30. }
  31.  
  32. static void dfs(int node, int parent) {
  33. dp[node][0] = 0; // 不选当前节点
  34. dp[node][1] = 1; // 选当前节点
  35.  
  36. for (int neighbor : graph[node]) {
  37. if (neighbor == parent) continue;
  38.  
  39. dfs(neighbor, node);
  40.  
  41. // 不选当前节点时,子节点可选可不选
  42. dp[node][0] += Math.max(dp[neighbor][0], dp[neighbor][1]);
  43. // 选当前节点时,子节点不能选
  44. dp[node][1] += dp[neighbor][0];
  45. }
  46. }
  47. }
Success #stdin #stdout 0.12s 54992KB
stdin
4 1
1 2
2 3
3 4
stdout
2