一、题意

一棵树有n个结点（n<=1e6），每个结点的权重为其深度，根节点深度为0。给这棵树选一个根节点，使得它的权重和最小。

二、解析

即使没学过树的重心这个概念，凭直觉就能感受到，以“重心”为根节点的树的权重和应该是最小的。事实上也是如此。

树的重心：

定义：对于一棵树的每一个结点u，它们的最大子树的结点数记为dp[u]。所有的结点中，dp最小的那个结点就是重心。

性质：

  1. 重心到所有节点的距离和最小（边权为1）
  2. 两棵树合并，新的重心在两棵树重心的路径上
  3. 一棵树添加或删除一个节点，重心最多移动一条边的位置
  4. 重心的最大的子树的节点数最小

三、代码

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int maxn = 1e6 + 5, INF = 1 << 30;
vector<int> G[maxn];
int n, cnt[maxn], dp[maxn], min_dp = INF;  // dp[i]存放以i为根的树的最大子树的结点个数

int dfs(int u, int fa) {
    int res = 1;
    for(int v : G[u]) if(v != fa) {
        int tmp = dfs(v, u);
        res += tmp;
        dp[u] = max(dp[u], tmp);
    }
    dp[u] = max(dp[u], n - res);
    min_dp = min(min_dp, dp[u]);
    return res;
}

int solve(int u, int fa, int dep) {
    int res = dep;
    for(int v : G[u]) if(v != fa) {
        res += solve(v, u, dep + 1);
    }
    return res;
}

int main() {
    cin >> n;
    for(int i = 0; i < n - 1; i ++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, 0);
    for(int i = 1; i <= n; i ++) if(dp[i] == min_dp) {
        cout << solve(i, 0, 0) << endl;
        break;
    }
}

四、归纳

  • 树的重心求法：
    • 先以任意点为根求出每个结点子树的结点数目 cnt[maxn]；
    • 在计算cnt时顺便计算每个结点的最大子树结点数 dp[maxn]；
    • 最后遍历所有结点，dp[i] == min_dp 的就是重心（可以有多个）。
  • 树重心模板： 
vector<int> G[maxn];
int n, cnt[maxn], dp[maxn], min_dp = INF;  // dp[i]存放以i为根的树的最大子树的结点个数

int dfs(int u, int fa) {
    int res = 1;
    for(int v : G[u]) if(v != fa) {
        int tmp = dfs(v, u);
        res += tmp;
        dp[u] = max(dp[u], tmp);  // 维护dp
    }
    dp[u] = max(dp[u], n - res);  // 不要漏了以“上面”的结点构成的子树
    min_dp = min(min_dp, dp[u]);  // 维护最小的dp，它对应的树根u就是重心
    return res;
}

int main() {
    ......
    dfs(1, 0);
    for(int i = 1; i <= n; i ++) if(dp[i] == min_dp) {
        ... // i就是重心
    }
}