OI Wiki 树的重心如何求树的重心并应用其性质【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki给定一棵树你需要找出它的重心centroid——删去该结点后剩下的每个连通分量大小都不超过原树结点数一半的结点。OI-wiki 在 树的重心 一文中给出了两种 $O(n)$ 求法并配套了可直接编译运行的 C 参考实现和样例输入。本文按“理解定义与性质 → 用两种方法求出重心 → 用样例验证 → 在点分治中应用”这条路径带你走通这个任务。代码为 C17编译时建议加g -O2样例输入文件已包含在仓库中。定义什么是重心什么是重量OI-wiki 的定义是如果在树 $T$ 中删去某个结点 $v$ 后得到的图 $T\setminus{v}$ 中每个连通分量的大小均不超过原树结点数的一半就称 $v$ 为整棵树的重心。删去某一结点后得到的最大连通分量的大小称为该结点的重量——重心就是重量不超过树结点数一半的结点。注意区分“无根树”和“有根树”的讨论对象有默认根时删去非根结点 $v$ 得到的连通分量中除了它各子结点对应的子树还有一棵“向上”的子树设为 $v$ 的父结点 $u$它就是 $T_u^{(v)}$。求重心时“向上”子树的大小要用总结点数 $n$ 减去 $v$ 所在子树大小得到这一点在后面的代码里直接体现。性质判断重心还有哪些等价办法OI-wiki 给出了重心的等价定义其中最常用的一条是树中所有结点到某结点的距离和中到重心时的距离和最小有根树版本即“以重心为根时深度和最小”。这正是第二种求法的基础。文档还列出四条常见性质求重心和应用重心时都会用到重心如果不唯一则恰有两个且这两个重心相邻删去它们的连边后树分成大小相同的两个连通分量在一棵树上添加或删除一个叶子重心最多移动一条边的距离把两棵树用一条边相连得到新树新树的重心在连接原来两棵树重心的路径上一棵有根树的重心一定在根结点所在的重链上见 重链剖分 的定义。方法一DFS 统计子树大小求重心按定义直接做DFS 计算每个结点子树的大小对每个结点取所有子树大小和“向上”子树大小的最大值作为重量重量 $\le n/2$ 的结点就是重心。整棵树一次 DFS时间 $O(n)$。下面是仓库中 tree-centroid-2.cpp 的完整代码节点编号默认从 1 开始MAXN为 50005 的数组容量上界结点数超过时需要自行调大#include iostream #include vector using namespace std; const int MAXN 50005; int n; // 这份代码默认节点编号从 1 开始即 i ∈ [1,n] int siz[MAXN], // 这个节点的「大小」所有子树上节点数 该节点 weight[MAXN]; // 这个节点的「重量」即所有子树「大小」的最大值 vectorint centroids; // 用于记录树的重心存的是节点编号 vectorint g[MAXN]; void dfs(int cur, int fa) { // cur 表示当前节点 (current) siz[cur] 1; weight[cur] 0; for (int v : g[cur]) { if (v ! fa) { // v 表示这条有向边所通向的节点 dfs(v, cur); siz[cur] siz[v]; weight[cur] max(weight[cur], siz[v]); } } weight[cur] max(weight[cur], n - siz[cur]); if (weight[cur] n / 2) { // 依照树的重心的定义统计 centroids.push_back(cur); } } void get_centroids() { dfs(1, 0); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n; for (int i 1; i n; i) { int u, v; cin u v; g[u].push_back(v); g[v].push_back(u); } get_centroids(); if (centroids.size() 1) cout centroids.front() \n; else cout min(centroids.front(), centroids.back()) max(centroids.front(), centroids.back()) \n; return 0; }输出约定重心唯一时输出一个编号有两个重心时按编号从小到大输出两个编号两个重心恰好相邻。方法二换根 DP 统计距离和求重心利用“重心使距离和最小”的等价定义先以 1 号结点为根 DFS 求出dp[u]u 子树内结点到 u 的距离和和子树大小siz[u]再做换根 DP——当根从 $u$ 换到相邻结点 $v$ 时$v$ 子树内结点距离 $1$、其余结点距离 $-1$得到转移式ans[v] ans[u] - siz[v] (n - siz[v])。最后取ans最小的结点同样 $O(n)$。完整代码见仓库 tree-centroid-3.cpp#include iostream #include limits #include vector using namespace std; const int N 50005; int n, siz[N]; long long dp[N], ans[N]; vectorint g[N], centroids; // 求 1 号节点到所有其他节点的距离和 void dfs1(int u, int fa) { siz[u] 1; dp[u] 0; for (int v : g[u]) { if (v fa) continue; dfs1(v, u); siz[u] siz[v]; dp[u] dp[v] siz[v]; // 子树节点到 u 的距离和 } } // 通过换根 DP 求所有节点为树根时对应的距离和 void dfs2(int u, int fa) { for (int v : g[u]) { if (v fa) continue; ans[v] ans[u] - siz[v] (n - siz[v]); dfs2(v, u); } } // 求树的重心 void get_centroids() { dfs1(1, 0); ans[1] dp[1]; dfs2(1, 0); long long mini std::numeric_limitslong long::max(); for (int i 1; i n; i) { if (ans[i] mini) { mini ans[i]; centroids {i}; } else if (ans[i] mini) centroids.push_back(i); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n; for (int i 1; i n; i) { int u, v; cin u v; g[u].push_back(v); g[v].push_back(u); } get_centroids(); if (centroids.size() 1) cout centroids.front() \n; else cout min(centroids.front(), centroids.back()) max(centroids.front(), centroids.back()) \n; return 0; }两种方法互为印证方法一按“重量 $\le n/2$”筛选方法二按“距离和最小”筛选对同一棵树的输出应当一致。用样例输入验证仓库 docs/graph/examples/tree-centroid/ 下为两种方法各配了一份相同的样例。tree-centroid-2.in 的内容6 1 2 2 3 2 5 3 4 3 6这是一棵 6 个结点的树。删去结点 2 后最大连通分量大小为 3结点 3、4、6删去结点 3 后最大连通分量也是 3结点 1、2、5——恰好是 $n/2$所以有两个相邻重心 2 和 3。文档给出的示例输出tree-centroid-2.ans方法二的 tree-centroid-3.ans 相同2 3你可以把上面任一代码保存为centroid.cpp后这样运行g -O2 -stdc17 -o centroid centroid.cpp ./centroid docs/graph/examples/tree-centroid/tree-centroid-2.in两份代码应分别输出文档示例中的2 3。应用把重心用作点分治的分治中心求重心最主要的用途是为树上的分治服务。按 点分治 一文的说法点分治中每一层递归合计对每个结点处理一次若共递归 $h$ 层则总时间复杂度为 $O(hn)$而每次选择当前子树的重心作为分治根删去重心后每块子树至多原树大小的一半递归深度被压到 $\log n$总时间复杂度为 $O(n\log n)$——因此点分治在国外竞赛圈也叫树的重心分解centroid decomposition。该文档同时提醒重新选择根节点之后一定要重新计算子树大小否则复杂度或正确性难以保证。进阶一次求出所有子树的重心OI-wiki 的例题是求给定有根树中每一棵子树的重心。思路利用性质 3以结点 $u$ 为根的子树的重心一定在 $u$ 到各直接子结点为根的子树重心所在的路径上。DFS 时先取子树重心ans[v]再沿父结点方向上移直到某个结点 $p$ 满足 $\max(weight[p],\ siz[u]-siz[p]) \le siz[u]/2$即为其重心总时间 $O(n)$。完整代码见 tree-centroid-1.cpp#include iostream #include vector using namespace std; constexpr int N 3e5 5; int n, q; // 点数询问数 int fa[N]; vectorint son[N]; int siz[N], // 子树大小 ans[N], // 以节点 u 为根的子树重心是 ans[u] weight[N]; // 节点重量不包括向上的子树 void dfs(int u) { siz[u] 1, ans[u] u; for (int v : son[u]) { dfs(v); siz[u] siz[v]; weight[u] max(weight[u], siz[v]); } for (int v : son[u]) { int p ans[v]; while (p ! u) { if (max(weight[p], siz[u] - siz[p]) siz[u] / 2) { ans[u] p; break; } else p fa[p]; } } } int main() { ios::sync_with_stdio(false); cin n q; for (int v 2; v n; v) cin fa[v], son[fa[v]].push_back(v); dfs(1); while (q--) { int u; cin u; cout ans[u] \n; } return 0; }它的输入格式与前两题不同第一行是结点数 $n$ 和询问数 $q$第二行依次给出 2 号到 $n$ 号结点的父结点之后每行一个询问 $u$输出以 $u$ 为根的子树的重心。样例 tree-centroid-1.in7 4 1 1 3 3 5 3 1 2 3 5文档示例输出tree-centroid-1.ans3 2 3 6限制与后续练习需要注意的几个边界样例代码的数组容量是固定上界方法一、二为MAXN 50005/N 50005进阶代码为3e5 5结点数超出时要调大否则越界重心可能有两个且两个重心相邻只输出一个编号的程序需确认题目要求进阶代码的weight不含“向上”的子树判断重心时要用siz[u] - siz[p]补上这部分这与整棵树求法用 $n - siz$的口径不同不能照搬。文档列出的练习题可继续沿这条路径练习题目链接见 docs/graph/tree-centroid.md 习题一节Gym 101649G Godfather、POJ 1655 Balancing Art、洛谷 P1364 医院设置、Codeforces 1406C Link Cut Centroids、Codeforces 708C Centroids。求得重心后下一步自然是阅读 点分治 把重心分解用到树上路径问题上或结合 树链剖分 利用“重心在根结点所在重链上”这条性质做位置定位。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考