OI-wiki 树的重心Centroid完全指南定义、性质证明与 O(n) 求法【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki树的重心centroid是树上最重要的结构性质之一删去它之后原树会被拆成若干棵大小均不超过原树一半的连通块。这个性质让分而治之在树上成为可能——OI-wiki 文档 docs/graph/tree-centroid.md 系统讲解了重心的定义、等价刻画、常用性质、两种 O(n) 求法以及典型例题。读完本文你将掌握重心的数学定义与全部核心性质含证明思路、两种可运行的 O(n) 求解模板DFS 统计子树大小 / 换根 DP 统计深度和以及如何在点分治重心分解与求每棵子树重心这类经典问题中运用它。重心的定义在无根树 $T$ 中如果删去某个结点 $v$ 后得到的图 $T\setminus{v}$ 中每个连通分量的大小均不超过原树结点数的一半就称 $v$ 为整棵树的重心。删去某一结点后得到的最大连通分量的大小称为该结点的重量weight。借助重量概念重心的定义可以等价叙述为重量不超过树结点数一半的结点。这个定义背后最关键的性质是删去重心后树的规模被砍半。这些连通分量本身仍然是无根树。正是这一特性使得在树上应用分治思想成为可能——这就是 点分治在国外竞赛圈也常称为树的重心分解centroid decomposition每次选取子树的重心作为分治中心可以保证递归层数最少总时间复杂度为 $O(n\log n)$。「子树」概念的约定树的重心讨论中常涉及无根树、有根树以及换根操作为避免混淆本文沿用 OI-wiki 原文档的记号用 $T$ 表示无根树用 $T^{(v)}$ 表示以结点 $v$ 为根的有根树文中的「子树」均指有根树中一个结点及其所有子孙构成的树有根树 $T^{(v)}$ 中结点 $u$ 对应的子树记为 $T^{(v)}_u$它包含整棵树本身明确不含整棵树时称「真子树」无根树中的「子树」通常指连通子图与有根树的子树集合不一致故文中不对无根树使用「子树」概念实际求解时往往有默认树根。此时删掉非根结点 $v$ 得到的连通分量中除了各子结点对应子树外还有一棵向上的子树设 $v$ 的父结点为 $u$它即 $T_u^{(v)}$。文中会显式称它为「向上」的子树默认情况下所提及的子树均不包括它。重心的等价定义树的重心有如下三种等价刻画分别从删点后连通块大小最大连通块最小化距离和最小化三个角度描述同一个对象 无根树版本1. 删去结点 $v$ 后$T\setminus\{v\}$ 中每个连通分量的大小均不超过原树结点数的一半 2. 在所有删去某结点后得到的最大连通分量大小中删去 $v$ 所得到的值最小即重量最小 3. 树中所有结点到某个结点的距离和中到 $v$ 的距离和最小。 有根树版本1. 当树以 $v$ 为根时任一真子树的大小均不超过原树结点数的一半 2. 在所有以某个结点为根时的最大真子树大小中以 $v$ 为根时所得到的值最小 3. 在所有以某个结点为根时所有结点的深度和中以 $v$ 为根时深度和最小。等价性证明思路原文档给出了严谨证明核心脉络如下理解它能帮你真正看穿重心的本质设 $W(x)\max_{u\sim x}|T_u^{(x)}|$$u\sim x$ 表示相邻$S(x)\sum_{u\in T}d(u,x)$ 为到 $x$ 的距离和。则定义 1 等价于 $W(v)\le |T|/2$定义 2 等价于 $v\in\arg\min W(x)$定义 3 等价于 $v\in\arg\min S(x)$。三个定义的等价性可以这样建立定义 1 ⇔ 定义 3距离和的极小把 $S(x)$ 理解为以 $x$ 为根时的深度和考虑树根从 $v$ 换到相邻结点 $u$。删去边 $(v,u)$ 后得到两个连通分量 $T_v^{(u)}$ 与 $T_u^{(v)}$换根时前者中每个结点深度 1后者深度 -1因此 $$ \Delta S_{v\to u}S(u)-S(v)|T|-2|T_u^{(v)}|. $$ 定义 1 的条件正是要求 $\Delta S_{v\to u}\le 0$ 对 $v$ 的所有邻点成立即 $v$ 是 $S(x)$ 的极小值点。极小 ⇔ 全局最小设 $v$ 是 $S(x)$ 的一个最小值点它必然是极小值点。考虑 $T^{(v)}$ 中任意非根结点 $u$设 $v$ 到 $u$ 路径上 $v$ 的后继为 $y$、$u$ 的前驱为 $x$由 $T_u^{(x)}\subseteq T_y^{(v)}$ 可推出 $2|T_x^{(u)}|\ge |T|$。随后分两种情形讨论存在 $u$ 使 $2|T_x^{(u)}||T|$ 成立则必有 $(x,u)(v,y)$ 且 $|T|2|T_u^{(v)}|$即 $|T|$ 为偶数此时满足三个条件的结点集合均为 ${v,u}$恰有两个相邻重心删去其连边后两分量大小相等不存在这样的 $u$则对一切 $u\ne v$ 都有 $W(u)|T|/2$三个条件唯一地指向 $v$唯一重心。两种情形中三个条件给出的结点集合完全相同故定义等价。重心的常用性质除等价定义外重心的以下性质在解题中极其常用重心个数树的重心若不唯一则恰有两个且这两个重心相邻删去它们的连边后树被分成两个大小相等的连通分量。叶子增减的局部性在一棵树上添加或删除一个叶子重心最多只移动一条边的距离。两树合并的路径性把两棵树通过一条边相连得到新树新树的重心在连接原来两棵树的重心的路径上。重链关联性一棵有根树的重心一定在根结点所在的重链上一棵树的重心一定是该树根结点重子结点对应子树的重心的祖先。其中性质 4 的证明依赖 重链剖分性质树剖保证每向下经过一条轻边子树大小至少减半。若重心 $v$ 到根的路径上经过轻边其所在子树大小将严格小于 $|T|/2$与重心定义矛盾因此 $v$ 必然位于根结点所在重链上再结合性质 3重心沿当前重心与根路径移动可推得祖先关系。性质 3 由性质 2 归纳可得把树 $T$ 的结点逐一作为叶子加入 $T$每一步重心都保持在旧重心到新叶子的路径上归纳即证。求法两种 O(n) 算法设 $n$ 为树的大小根据等价定义有两种方法在 $O(n)$ 时间内求出树的所有重心。方法一DFS 统计子树大小对无根树任选根做一次 DFS计算每个子树的大小对每个结点记录其各子结点子树大小并用总结点数减去当前子树大小得到「向上」的子树大小然后直接依据定义重量 ≤ n/2判定即可。参考实现见 docs/graph/code/tree-centroid/tree-centroid-2.cpp其核心片段被原文档以:core标记引用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); }要点weight[cur]同时取各子结点子树大小最大值与向上子树大小 $n-\text{siz}[cur]$的最大值正对应重量 删点后最大连通分量大小的定义。该实现已在 Codeforces Gym 101649G Godfather 与 tree-centroid-2.ans对 6 个结点的树边 1-2, 2-3, 2-5, 3-4, 3-6输出2 3——这正是两个相邻重心情形的直观体现。方法二换根 DP 统计深度和利用等价定义 3用换根 DP 计算出以每个结点为根时所有结点的深度和即到根的距离和深度和最小的结点即为重心。参考实现见 docs/graph/code/tree-centroid/tree-centroid-3.cppconst 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); } }两次 DFS 分别完成以 1 为根的深度和计算与换根转移从 $u$ 换根到子结点 $v$ 时$v$ 子树内所有结点深度 -1贡献 $-\text{siz}[v]$其余 $n-\text{siz}[v]$ 个结点深度 1故转移式为ans[v] ans[u] - siz[v] (n - siz[v])与前面证明中的 $\Delta S$ 公式完全一致。最后取最小值即得全部重心相等者并列加入。该代码同样在 Gym 101649G 上验证样例见 tree-centroid-3.in / tree-centroid-3.ans。经典例题CF 685B Kay and Snowflake题目给定一棵有根树根为 1求出每一棵子树的重心共 $q$ 次询问。解题思路利用性质 3——对以 $u$ 为根的子树其重心一定在以 $u$ 的直接子结点为根的子树的重心到 $u$ 的路径上。做法类似于 DFS 求重心对每棵子树先递归求出各直接子结点子树的重心叶子结点的重心是它自己然后沿父指针向上逐个判断路径上的结点是否为重心即可。每棵子树的重心只需从子结点子树重心出发向上爬均摊后总复杂度为 $O(n)$。参考代码见 docs/graph/code/tree-centroid/tree-centroid-1.cpp核心逻辑如下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]; } } }注意此处weight[p]不包含向上的子树代码注释亦如此说明向上检查时需用siz[u] - siz[p]补上以 $p$ 为根向上那一块的大小二者取最大值与 $siz[u]/2$ 比较即是在以 $u$ 为根的子树这个局部语境中套用重心定义。配套样例 tree-centroid-1.in7 个点父亲序列1 1 3 3 5 3询问子树 1、2、3、5对应答案 tree-centroid-1.ans 为3 2 3 6。习题Gym 101649G Godfather重心模板两种求法均已在此验证POJ 1655 Balancing Art删点后最大连通分量最小化洛谷 P1364 医院设置距离和最小化对应等价定义 3Codeforces 1406C Link Cut CentroidsCodeforces 708C Centroids参考资料《信息学奥林匹克辞典》2.4.7.11 章 树的重心树的重心相关性质及动态维护的经典资料fanhq666树的直径、树的重心与树的点分治cyendra树的重心的性质及其证明suxxsfe若想继续深入建议结合 docs/graph/tree-divide.md 阅读点分治完整内容含点分树的重构实现体会每次选重心如何把递归层数压到 $O(\log n)$重心与重链的关联细节可参考 docs/graph/hld.md。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考