【板子】求树的重心

一、什么是树的重心对一棵无根树删除节点 u后会得到若干连通块设最大连通块点数为 f(u)。使 f(u)最小的节点称为树的重心质心。等价定义以 u为根时所有子树含“向上”那棵的点数最大值最小。二、核心性质数量至少有 1 个至多 2 个若有 2 个则必然相邻常出现在偶数链的中点。平衡性以重心为根时每棵子树大小 ≤n/2删除重心后最大连通块 ≤n/2。距离和最小所有点到重心的距离和最小两个重心时距离和相等。稳定性增/删一个叶子重心最多移动一条边。三、求法思路DFS 一次O(n)任选一点如 1为根 DFS计算sz[u] 以 u 为根的子树大小含 u。对 u 的每个子节点 vmax_part max(max_part, sz[v])。父方向连通块大小为n - sz[u]更新max_part max(max_part, n - sz[u])。使max_part最小的 u 即为重心若max_part n/2也直接判定为重心(特性当重心旁移动一次一定会出现大于n/2的块出现小于等于已经是绝对最优)四、C 模板代码#include bits/stdc.h using namespace std; const int N 1e5 5; vectorint g[N]; int sz[N], n; int best N; // 最小的最大连通块 vectorint cents; // 所有重心 void dfs(int u, int fa) { sz[u] 1; int mx 0; for (int v : g[u]) { if (v fa) continue; dfs(v, u); sz[u] sz[v]; mx max(mx, sz[v]); // 子树方向 } mx max(mx, n - sz[u]); // 父方向连通块 if (mx best) { // 找到更优的重心 best mx; cents.clear(); cents.push_back(u); } else if (mx best) { // 另一个重心 cents.push_back(u); } } int main() { cin n; for (int i 1, a, b; i n; i) { cin a b; g[a].push_back(b); g[b].push_back(a); } dfs(1, 0); cout cents.size() \n; for (int x : cents) cout x ; return 0; }