 两遍 DFS 求解)
OI-wiki 树的中心详解定义、性质与 O(n) 两遍 DFS 求解【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki树的中心Tree Center是树上问题中与直径、重心并列的基础概念它是在树中选择一个节点作为根时能令从该根出发的最长链最短的节点。本文以 OI-wiki 的 树的中心 文档为主体系统讲解树的中心的定义、五条核心性质、基于len1 / len2 / up三个数组的 O(n) 求法及完整参考代码并通过与 树的直径、树的重心 的对比帮助读者在 OI / ICPC 竞赛与算法面试中快速识别与运用这一概念。读完本文你将掌握树的中心的数学刻画、其与直径的深度绑定关系以及一套可直接套用的两遍 DFS 求解模板。前置知识在深入树的中心之前需要先熟悉以下基础概念树无根树有 n 个节点、n-1 条边的连通无向图任意两点之间有且仅有一条简单路径。相关完整定义与存储方式vectorint adj[N]邻接表等见 树基础。树的直径树上任意两节点之间最长的简单路径。直径可以通过两次 DFS 或树形 DP 在 O(n) 时间内求出其核心性质是若所有边权均为正则树的所有直径中点重合。详见 树的直径。理解树的中心时最关键的直觉来源是直径树的中心一定位于树的直径上因此本文的讨论会反复与直径进行对照。定义在树中如果节点 x 作为根节点时从 x 出发的最长链最短那么称 x 为这棵树的中心。形式化地说设 $f(x) \max_{y \in V} \text{dist}(x, y)$ 为节点 x 到树上所有节点的最大距离即以 x 为根时的树高树的中心就是使 $f(x)$ 取到最小值的节点 x$$ \text{center} \arg\min_{x \in V} f(x) $$注意最长链指的是一条简单路径的长度即路径上的边数边权为正时也可推广为带权路径长度。与 树的重心 的删去该节点后各连通分量大小不超过一半这一基于规模的定义不同树的中心是一个基于距离/深度的最优化概念——这决定了二者在应用场景上的根本区别。性质设树 T 的节点数为 n其中心为 x树的直径长度为 D则树的中心满足以下性质中心不一定唯一但最多有 2 个且这两个中心相邻。这是中心与重心在唯一性上相似的结论当且仅当树的直径为偶数时存在唯一中心当直径为奇数时恰好存在两个中心且它们就是直径的中部相邻的两个节点。这与直径性质所有直径中点重合见 树的直径相互印证——直径中点正是中心。中心一定位于树的直径上。因为 $f(x)$ 的最小值必然在直径的中间位置取得任何偏离直径的节点到某一直径端点的距离都会严格增大。树上所有点到其最远点的路径一定交会于树的中心。以中心为根的视角下树的极值路径每个点通往它最远点的路径会在中心处汇聚这使得中心成为研究树最坏情况距离的枢纽。当中心为根节点时其到达直径端点的两条链分别为最长链和次长链。以中心为根时直径的两个端点分别落在中心的两条不同分支上这两条分支恰好构成中心的最长链长为 $\lceil D/2 \rceil$与次长链长为 $\lfloor D/2 \rfloor$且这两条链互不重叠没有公共边。这正是下文求法中用len1最长链与len2不与len1重叠的最长链即次长链两个数组刻画中心的动机。当通过在两棵树间连一条边以合并为一棵树时连接两棵树的中心可以使新树的直径最小。这一性质是最小直径生成树见 最小直径生成树等构造类问题的核心思想来源在两棵树之间连边时最优连边位置必然在两棵树的中心处因为此时新直径的上界被控制在 $\max(D_1, D_2, \lceil D_1/2 \rceil 1 \lceil D_2/2 \rceil)$ 这一最小可能范围内。中心到其他任意节点的距离不超过树直径的一半。即 $\forall y \in V,\ \text{dist}(x, y) \le \lceil D/2 \rceil$。这直接由中心的定义$f(x)$ 最小且 $f(x) \lceil D/2 \rceil$得出是中心最坏情况下也足够近的保证。对比记忆直径刻画最远能有多远中心刻画以谁为根最均衡重心刻画删掉谁子树最均衡。三者是树上三个不同维度的最优点求解方式与性质各异。求法寻找一个点 x使其作为根节点时最长链的长度最短。等价于最小化 $\max(\text{len1}_x, \text{up}_x)$其中$\text{len1}_x$ 表示节点 x 子树内的最长链以 x 为根向下能延伸的最大深度$\text{up}_x$ 表示节点 x 子树外的向上最长链——即从 x 出发、绕过父节点方向能走出的最长路径长度。具体步骤第一遍 DFS自底向上维护len1[x]表示节点 x 子树内的最长链。对每个子节点 nxt用len1[nxt] ww 为边权尝试更新len1[x]。同步维护len2[x]表示不与len1[x]重叠的最长链即从 x 出发、走向不同于最长链所在子节点的另一条分支的最长长度。当len1[nxt] w不能更新len1[x]时用它尝试更新len2[x]。这一步是为了在第二步中处理最长链恰好来自某个子节点的情况。第二遍 DFS自顶向下维护up[x]表示节点 x 子树外的最长链该链必定经过 x 的父节点。递推式为 $$ \text{up}[nxt] w \max\big(\text{up}[cur],\ \text{len1}[cur] \text{当最长链不在 } nxt \text{ 子树时或 } \text{len2}[cur] \text{当最长链在 } nxt \text{ 子树时}\big) $$ 关键在于判断cur的子树内最长链是否来自子节点nxt若来自nxt则对nxt而言只能用次长链len2[cur]兜底避免重复经过同一条边。统计答案遍历所有节点找到使得 $\max(\text{len1}_x, \text{up}_x)$ 最小的点即为树的中心若存在第二个取值相同的节点则两节点同为树的中心。参考代码以下代码完整继承自 树的中心 文档默认节点编号从 1 开始即 $i \in [1, n]$使用vector存图支持带权边// 这份代码默认节点编号从 1 开始即 i ∈ [1,n]使用vector存图 int d1[N], d2[N], up[N], x, y, mini 1e9; // d1,d2对应上文中的len1,len2 struct node { int to, val; // to为边指向的节点val为边权 }; vectornode nbr[N]; void dfsd(int cur, int fa) { // 求取len1和len2 for (node nxtn : nbr[cur]) { int nxt nxtn.to, w nxtn.val; // nxt为这条边通向的节点val为边权 if (nxt fa) { continue; } dfsd(nxt, cur); if (d1[nxt] w d1[cur]) { // 可以更新最长链 d2[cur] d1[cur]; d1[cur] d1[nxt] w; } else if (d1[nxt] w d2[cur]) { // 不能更新最长链但可更新次长链 d2[cur] d1[nxt] w; } } } void dfsu(int cur, int fa) { for (node nxtn : nbr[cur]) { int nxt nxtn.to, w nxtn.val; if (nxt fa) { continue; } up[nxt] up[cur] w; if (d1[nxt] w ! d1[cur]) { // 如果自己子树里的最长链不在nxt子树里 up[nxt] max(up[nxt], d1[cur] w); } else { // 自己子树里的最长链在nxt子树里只能使用次长链 up[nxt] max(up[nxt], d2[cur] w); } dfsu(nxt, cur); } } void GetTreeCenter() { // 统计树的中心记为x和y若存在 dfsd(1, 0); dfsu(1, 0); for (int i 1; i n; i) { if (max(d1[i], up[i]) mini) { // 找到了当前max(len1[x],up[x])最小点 mini max(d1[i], up[i]); x i; y 0; } else if (max(d1[i], up[i]) mini) { // 另一个中心 y i; } } }代码要点说明dfsd自底向上求出每个节点子树内的最长链d1与次长链d2。注意更新d1时先将原最长链降级为次长链d2[cur] d1[cur]从而保证d1与d2来自不同的子节点分支、无公共边。dfsu自顶向下传递向上链up[nxt]的初值是up[cur] w继续沿父方向向上再根据cur的最长链是否经过nxt用d1[cur]或d2[cur] w取最大。if (d1[nxt] w ! d1[cur])这一判断是整个转移的分水岭。GetTreeCenter中通过严格小于 / 等于的比较区分唯一中心与双中心情形等于mini的第二个点被记入y。数组大小N、全局变量n需根据题目数据范围自行声明mini初始化为足够大的值代码中为1e9。示例假设我们有一棵树如下所示A / \ B C / \ \ D E F树的直径为 $D \rightarrow B \rightarrow A \rightarrow C \rightarrow F$。直径长度为 $4$。树的中心为节点 A因为从 A 出发的最长链到 D 或 F均为 $2$。如果将 B 或 C 作为树的根则从这些节点出发的最长链将增加因此它们不是树的中心。该示例同时验证了性质 2 与性质 6中心 A 恰为直径的中点且 A 到任意节点的距离不超过 $4 / 2 2$。由于直径长度 4 为偶数中心唯一符合最多两个中心且相邻的性质 1。时间复杂度上述算法共进行两遍 DFSdfsd与dfsu每遍访问每个节点及其邻边一次再加上一次 O(n) 的线性扫描统计答案总时间复杂度为 $O(n)$其中 n 是树中节点的数量。空间上需要d1、d2、up三个 O(n) 数组与邻接表总空间复杂度为 $O(n)$。正确性说明从源码结构看该算法的正确性建立在两个递推的完备性上len1与len2覆盖了以任意节点 x 为根时向下的所有链信息。树上任意一条从 x 出发的路径要么落在len1对应的子节点分支内要么落在其他分支被len2记录。up覆盖了 x 的所有非子树方向路径。由于树是连通的x 到任意节点 y 的路径若第一步不走入 x 的子树则必经其父节点——这正是up递推式up[nxt] up[cur] w的由来。因此 $\max(\text{len1}_x, \text{up}_x)$ 精确等于 $f(x)$x 到树上所有节点的最大距离对全节点取最小即得到树的中心定义式。这一向下最长链 向上最长链的换根思想与 树的重心 中DFS 统计子树大小 总结点数减去当前子树大小得到向上子树的换根 DP 思路一脉相承。与树的重心的辨析树的中心与 树的重心 名称相近、极易混淆二者的核心差异如下维度树的中心树的重心最优化目标最小化以该点为根时离根最远的距离深度维度最小化删去该点后最大连通分量的大小规模维度等价刻画$f(x) \max_y \text{dist}(x, y)$ 最小任一删去后连通分量大小不超过 n/2典型应用最小直径生成树、消防站选址类最坏距离问题点分治重心分解、子树大小均衡类问题参考文档docs/graph/tree-center.mddocs/graph/tree-centroid.md在 OI 中树的中心常用于使最远距离最小的构造与判定题而树的重心则是点分治见 树分治的基础做题时务必先确认题目优化的是距离还是规模。总结树的中心是树上均衡性在距离维度上的体现它由 $\arg\min_x \max_y \text{dist}(x, y)$ 定义最多两个、彼此相邻、必在直径上且到任意节点的距离不超过直径一半。求解只需两遍 DFS——一遍自底向上统计子树内最长链len1与次长链len2一遍自顶向下统计子树外最长链up最后线性扫描 $\max(\text{len1}_x, \text{up}_x)$ 的最小值即可时间复杂度 $O(n)$。掌握这一模板后建议结合 树的直径 中的直径求法对比学习并在遇到两棵树合并使直径最小一类问题时优先联想到连接两棵树的中心这一性质。参考本文核心内容继承自 docs/graph/tree-center.md概念背景参考了仓库内 树基础 与 树的直径 文档原文档的参考文献TutorialsPoint 的 Centers of a Tree、ProofWiki 的 Definition of Center of Tree、Wikipedia 的 Tree (graph theory)可作为进一步了解该概念历史定义的延伸阅读。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
