846. 树的重心

给定一颗树，树中包含 n 个结点（编号 1∼n）和 n−1条无向边。
请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。
重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。
输入格式
第一行包含整数 n，表示树的结点数。
接下来 n−1 行，每行包含两个整数 a和 b，表示点 a 和点 b 之间存在一条边。
输出格式
输出一个整数 m，表示将重心删除后，剩余各个连通块中点数的最大值。
数据范围
1≤n≤105
输入样例

  1. 9
  2. 1 2
  3. 1 7
  4. 1 4
  5. 2 8
  6. 2 5
  7. 4 3
  8. 3 9
  9. 4 6

输出样例：

  1. 4

思路：

使用邻接表存储树
深度优先搜索求树中每个节点作为被删除节点的最大连通块，用一个全局变量保存个节点最大连通块中的最小值。

作为被删除节点的每个节点的连通块的组成：

  • 父节点组成的连通块
  • 每个子树构成一个连通块

具体做法：

  1. 深搜每个节点，用st记录已经被搜索过的节点
  2. 记录该节点各子树的最大连通块 res ，同时记录以该节点为根节点的连通块的节点数 sum
  3. 找到该节点各子树最大连通块后与父节点组成的连通块数进行比较得到删除该节点后的最大连通块数，更新全局变量 ans 
  1. import java.util.*;
  3. public class Main {
  4.     static int n, idx;
  5.     static int[] h, e, ne;
  6.     static int ans = Integer.MAX_VALUE;
  7.     static boolean[] st;
  9.     public static void main(String[] args) {
  10.         Scanner sc = new Scanner(System.in);
  11.         n = sc.nextInt();
  13.         h = new int[n + 1];
  14.         Arrays.fill(h, -1);
  15.         e = new int[n * 2];
  16.         ne = new int[n * 2];
  17.         st = new boolean[n + 1];
  20.         int m = n - 1;
  22.         while (m-- > 0) {
  23.             int a = sc.nextInt(), b = sc.nextInt();
  25.             add(a, b);
  26.             add(b, a);
  27.         }
  29.         dfs(1);
  31.         System.out.println(ans);
  33.     }
  35.     static int dfs(int u) {
  36.         st[u] = true;
  38.         int sum = 1, res = 0;
  39.         for (int i = h[u]; i != -1; i = ne[i]) {
  40.             int j = e[i];
  41.             if (st[j]) continue;
  43.             int s = dfs(j);
  44.             res = Math.max(res, s);
  45.             sum += s;
  46.         }
  48.         res = Math.max(res, n - sum);
  49.         ans = Math.min(res, ans);
  51.         return sum;
  52.     }
  54.     static void add(int a, int b) {
  55.         e[idx] = b;
  56.         ne[idx] = h[a];
  57.         h[a] = idx ++;
  58.     }
  59. }