定义

  1. 对于树上的每一个点，计算其所有子树中最大的子树节点数，这个值最小的点就是这棵树的重心。
  3. 这里以及下文中的“子树”都是指无根树的子树，即包括“向上”的那棵子树，并且不包括整棵树自身。

性质

  1. 以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。
  3. 树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。
  5. 把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。
  7. 在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。

求法

  1. 在 DFS 中计算每个子树的大小，记录“向下”的子树的最大大小，
  3. 利用总点数 - 当前子树（这里的子树指有根树的子树）的大小得到“向上”的子树的大小，
  5. 然后就可以依据定义找到重心了。

代码

  1. // 这份代码默认节点编号从 1 开始，即 i ∈ [1,n]
  2. int size[MAXN],  // 这个节点的“大小”（所有子树上节点数 + 该节点）
  3.     weight[MAXN],  // 这个节点的“重量”
  4.     centroid[2];   // 用于记录树的重心（存的是节点编号）
  6. void GetCentroid(int cur, int fa) {  // cur 表示当前节点 (current)
  7.   size[cur] = 1;
  8.   weight[cur] = 0;
  9.   for (int i = head[cur]; i != -1; i = e[i].nxt) {
  10.     if (e[i].to != fa) {  // e[i].to 表示这条有向边所通向的节点。
  11.       GetCentroid(e[i].to, cur);
  12.       size[cur] += size[e[i].to];
  13.       weight[cur] = max(weight[cur], size[e[i].to]);
  14.     }
  15.   }
  16.   weight[cur] = max(weight[cur], n - size[cur]);
  17.   if (weight[cur] <= n / 2) {  // 依照树的重心的定义统计
  18.     centroid[centroid[0] != 0] = cur;
  19.   }
  20. }

例题，D. Kay and Snowflake

  1. 题意：
  2. 给你n个点，以1为根，然后给你2-n的节点的父亲节点编号。Q个询问，问以询问的节点为根的重心编号。
  4. 性质：
  5. 1.树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么他们的距离和一样。 
  6. 2.把两个树通过一条边相连得到一个新的树，那么新的树的重心在连接原来两个树的重心的路径上。 
  7. 3.把一个树添加或删除一个叶子，那么它的重心最多只移动一条边的距离。 
  9. 本题使用的就是第2条定理。
  10. 如果深搜此树，在回溯的时候，遇到一个以u为节点的子树，
  11. 如果其u的临接点v是u的重儿子（节点u的儿子中规模最大的子树的节点）。
  12. 那么两个部分相连之后的新的重心在u到以v为根的子树的重心这条链上。
  14. 性质：
  15. 一棵树的重心一定在它的根上或是在它的子树最大的子节点所在子树内,
  16. 且一定在该子树的重心或其上方
  17. (u的重心，一定在最大的儿子里面（重儿子）)
  19. 因此我们可以从下往上找,重心默认为它自己,
  20. 若存在一个子节点的子树大小大于其一半,就将重心改为这个子节点的重心,
  21. 并不断向上跳,
  22. 直到满足重心(树的重心的定义:以这个点为根，那么其所有的子树的大小都不超过整个树的一半)。
  24. 因为每条边最多被跳一次,所以复杂度仍然为O(n),不仅好写,而且时间空间均十分优越
  1. Solve it for all subtrees. 
  3. We can solve the problem for some subtree, 
  4. after solving the problem for all of it's children. 
  5. Let's choose the heaviest child. 
  6. Note that the centroid of the child after a certain lifting goes into our centroid. 
  7. Let's model the lifting.
  9. Thus we get the answers for all vertex and we need only output answers for queries.
  11. Complexity O(n + q)
  1. #include <bits/stdc++.h>
  3. using namespace std;
  5. const int N = 3e5 + 10;
  7. int h[N], e[N * 2], ne[N * 2], idx;
  8. int fa[N], mxs[N], sz[N];
  9. int ans[N];
  10. int n, q;
  12. void add(int a, int b){
  13.     e[idx] = b, ne[idx] = h[a], h[a] = idx++;
  14. }
  16. void dfs(int u, int father){
  17.     sz[u] = 1, ans[u] = u, mxs[u] = u;
  18.     int mx = 0;
  20.     for (int i = h[u]; i != -1; i = ne[i]){
  21.         int j = e[i];
  22.         if (j == father) continue;
  24.         dfs(j, u);
  26.         sz[u] += sz[j];
  27.         if (mx < sz[j]){
  28.             mx = sz[j];
  29.             mxs[u] = j;  // 更新重儿子
  30.         }
  31.     }
  33.     // 一棵树的重心一定在它的根上或是在它的子树最大的子节点所在子树内
  34.     // 且一定在该子树的重心或其上方
  35.     ans[u] = ans[mxs[u]];
  36.     //while (ans[u] != u && ((sz[u] - sz[ans[u]]) > sz[u] / 2)){
  37.     //    ans[u] = fa[ans[u]];
  38.     //}
  40.     while (ans[u] != u && sz[ans[u]] * 2 < sz[u]){
  41.         ans[u] = fa[ans[u]];
  42.     }
  43. }
  45. int main(){
  46.     cin >> n >> q;
  47.     memset(h, -1, sizeof h);
  48.     for (int i = 2; i <= n; i++){
  49.         int x;
  50.         scanf("%d", &x);
  51.         fa[i] = x;
  52.         add(i, x); add(x, i);
  53.     }
  55.     dfs(1, 0);
  57.     while (q--){
  58.         int x;
  59.         scanf("%d", &x);
  60.         printf("%d\n", ans[x]);
  61.     }
  63.     return 0;
  64. }