算法自学__树的重心

参考资料：

• https://zhuanlan.zhihu.com/p/357938161

定义

计算以无根树的每个点为根节点时的最大的子树的大小，这个值最小的点称为无根树的重心。

性质

1. 某个点是树的重心等价于这个点的最大子树大小小于等于整棵树大小的一半。
2. 树至多有两个重心。如果树有两个重心，则这两个重心相邻，该树一定有偶数个结点，且可以被划分成两个大小相等的分支，每个分支各自包含一个重心。
3. 树中所有点到某个点的距离和中，到重心的距离和是最小的。反过来，距离和最小的点一定是重心。
4. 往树上增加或减少一个叶子，如果原结点数为奇数，则重心可能增加一个，原重心依然为重心；如果原结点数为偶数，则重心可能减少一个，另一个重心仍然是重心。
5. 把两个树通过一条边相连得到一颗新树，则新的重心在较大的树一侧的连接点与原重心的简单路径上。如果两颗树大小一样，则重心就是两个连接点。

求重心

int n, sz[MAXN], mss[MAXN]; // n：总结点数（请从外部传入），sz：树的大小，mss：最大子树大小
vector<int> ctr; // 重心
void dfs(int p, int fa = 0) // 找重心
{
    sz[p] = 1, mss[p] = 0;
    for (auto [to, w] : edges[p])
        if (to != fa)
        {
            dfs(to, p);
            mss[p] = max(mss[p], sz[to]);
            sz[p] += sz[to];
        }
    mss[p] = max(mss[p], n - sz[p]);
    if (mss[p] <= n / 2) ctr.push_back(p);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15