洛谷 P3478POI 2008 STA-Station是我见过最适合入门换根DP的题目没有之一。题面非常直白给你一棵树找出一个节点来做根让所有节点的深度之和最大。如果数据范围小直接每个点跑一遍DFS就完事但这题的数据规模接近百万量级O(n^2) 根本跑不动。换根DP的做法就是先随便选一个根把答案算出来再通过一个 O(1) 的递推式把答案“搬”到相邻节点上整棵树每个点都能在 O(n) 时间内得到答案。这篇文章就沿着这条主线把状态定义、公式推导、两份可提交的代码以及那些容易被坑的细节一次说清楚。适合刚学完树形DP、但遇到“每个点都要当一次根”这类问题容易懵的选手也适合想系统理解换根DP套路的人。1. 项目概述旧题新解换根DP的经典模板1.1 题目到底在问什么题目给出一棵无根树要求我们选一个点作为根计算出这棵树上所有节点的深度之和。这里“深度”可以定义为根节点为 0也可以定义为根节点为 1题目本身不会因为这个基准不同而改变答案对应的那个节点后面推导公式的时候这点会自然体现出来。举个例子假设树长这样1-22-33-42-5如果拿 1 当根深度从 0 开始算那么各节点深度分别是 0、1、2、3、2总和是 8。如果拿 4 当根深度分别是 3、2、1、0、3总和是 9。可以看到不同的根答案会差不少。题目的核心就是在所有 n 个候选根里找出让深度总和最大的那个点。这种问题之所以值得专门讲是因为它不像普通树形DP那样只求一个固定根的答案而是要求“所有可能根”的状态。如果对每个点都重新DFS一次百万级别的节点数是绝对不可行的换根DP就是为此设计的。1.2 为什么不能枚举每个根很多新手拿到题的第一反应就是这还不简单n 次 DFS每次统计深度和取最大。这种思路在 n ≤ 2000 时没什么问题但放到百万量级就完全崩了。简单估算一下假设树是一条链每次DFS都要遍历全部 n 个节点做 n 次就是 n 的平方量级。n 100000 时已经是一百亿次操作n 1000000 时更是一万亿次这显然不是几秒能跑完的事。就算用再快的读入优化、再紧凑的邻接表也救不回来。所以我们必须换一种思路第一次DFS先算出一个根比如节点 1的答案第二次DFS时利用父子关系在常数时间内把父节点的答案“调整”成子节点的答案。因为树上任意两点之间只有一条路径根从 u 换到相邻的 v 时变化的只是所有节点的深度而且这种变化是可以批量计算的。这个“调整”的过程就是换根DP的核心。2. 核心细节解析状态定义与转移方程推导2.1 第一次DFS预处理子树大小和初始答案做换根DP前我们先约定两个基本状态sz[u]以节点 1 为根时u 的子树大小。注意这里说的“子树”方向是固定以 1 为参照系的。dp[u]以 u 为根时整棵树所有节点的深度之和。第一次DFS从 1 出发做三件事给每个节点记录深度、递归算子树大小、累加得到dp[1]。这里深度基准选 0 还是 1 都可以只要第一次DFS和后面公式里的基准保持一致就行。因为换根公式是相邻两个答案之间的差值关系基准常数会在差值中抵消掉最终不影响“哪个点最大”的结论。以 1 为根跑完第一次DFS后我们得到了一棵有向的“父子树”。每个节点 u 的sz[u]都明确了这棵子树里一共有多少个节点深度也明确了从 1 到每个节点的距离。dp[1]就是所有节点到 1 的距离总和。有了这份基础数据才能开始“搬家”。2.2 换根公式答案如何从父节点迁移到子节点这是整道题最核心的一步。假设现在知道dp[u]想把根从 u 换到它的某个儿子 v问dp[v]等于多少。不要试图重新计算每个节点的深度那是笨办法。我们只需要看换根之后哪些节点深度变了变了多少。以 1 为根时v 的子树大小为sz[v]。这些节点在 u 为根时v 的子树内所有节点都在 v 这一侧它们的深度都比原来少了 1所以总共减少了sz[v]。剩下的部分呢除了 v 子树内的节点其他节点在换根后都离根更远了。具体来说u 和 u 那边所有的节点深度都比原来多了 1。这部分节点数量是n - sz[v]所以总共增加了n - sz[v]。于是可以得到dp[v] dp[u] - sz[v] (n - sz[v]) dp[u] n - 2 * sz[v]这个式子就是换根DP的命根子。后面所有代码都是在反复用这个公式。这里有个很容易绕晕的点公式里的sz[v]是第一次DFS以 1 为根时算出的子树大小不是“以 u 为根时 v 的子树大小”。因为第一次DFS已经固定了整棵树的父子方向第二次DFS只是沿着这个方向从上往下推sz数组不会改变。很多初学者在这里会突然怀疑“根都换成 v 了v 的子树不就应该变成反方向了吗”其实不必纠结sz[v]只是一个预先算好的静态信息它告诉你如果根从 u 移到 v哪些节点深度会减少。减少的永远是以 1 为根时 v 子树里的那些节点。2.3 手算验证公式到底怎么用光看公式容易发虚拿前面那棵树实际算一遍。先以 1 为根DFS得到sz[1] 5, sz[2] 4, sz[3] 2, sz[4] 1, sz[5] 1dp[1] 0 1 2 3 2 8从 1 换到 2dp[2] dp[1] n - 2 * sz[2] 8 5 - 2 * 4 5手动以 2 为根算一下深度总和节点深度为 1、0、1、2、1总和确实是 5。公式正确。从 2 换到 3dp[3] dp[2] n - 2 * sz[3] 5 5 - 2 * 2 6从 3 换到 4dp[4] dp[3] n - 2 * sz[4] 6 5 - 2 * 1 9最后答案是 9对应节点 4跟最开始手动枚举的结果一致。整棵树的答案表如下根节点深度总和1825364958最大值出现在节点 4所以输出 4。如果没有换根公式这五个数每个都要重新DFS一遍才能得到有了公式只需要一次预处理的 O(n) 加一次 O(1) 的递推快得多。3. 实操过程从零写出这份AC代码3.1 建图选型邻接表还是链式前向星写树题第一步永远是怎么存图。常见的方案有两种vector邻接表和链式前向星。对于这道题vector写法读起来最友好代码也最少。但要注意如果 n 真的到百万级vector的扩容和遍历开销会比链式前向星高一些而且每个节点都要维护一个动态数组内存碎片和 cache 命中率都不如静态数组。竞赛里稳妥的做法是用链式前向星也就是用静态数组模拟邻接表。链式前向星本质上就是用一个head数组记录每个点第一条边的下标再用next把同一个点的所有边串起来。加边和遍历都非常直接内存是预先开好的连续数组性能稳定。如果只是想快速理解换根DP的逻辑vector版本完全够用。但如果想在 POI 原题这种大数据范围下求稳建议用链式前向星。下面先把完整代码给出来再解释每个部分。3.2 完整可提交代码#include bits/stdc.h using namespace std; const int MAXN 1000005; struct Edge { int to, next; } edge[MAXN 1]; int head[MAXN], tot; int n; int sz[MAXN]; long long dp[MAXN]; void addEdge(int u, int v) { edge[tot].to v; edge[tot].next head[u]; head[u] tot; } void dfs1(int u, int fa, int depth) { sz[u] 1; dp[1] depth; for (int i head[u]; i ! -1; i edge[i].next) { int v edge[i].to; if (v fa) continue; dfs1(v, u, depth 1); sz[u] sz[v]; } } void dfs2(int u, int fa) { for (int i head[u]; i ! -1; i edge[i].next) { int v edge[i].to; if (v fa) continue; dp[v] dp[u] n - 2LL * sz[v]; dfs2(v, u); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n; memset(head, -1, sizeof(head)); for (int i 1; i n; i) { int a, b; cin a b; addEdge(a, b); addEdge(b, a); } dfs1(1, 0, 0); dfs2(1, 0); int ans 1; for (int i 2; i n; i) { if (dp[i] dp[ans]) ans i; } cout ans \n; return 0; }代码核心逻辑并不复杂。dfs1里每次递归到一个新节点先把当前深度累加到dp[1]再递归处理子节点子节点返回后把子树的节点数累加到当前节点。dfs2就纯粹是套公式从 1 开始一路往下更新各个点的答案。注意最后一轮找答案ans初始设为 1更新时用的是dp[i] dp[ans]而不是。这样如果存在多个相同最大值的解最终会保留编号最小的那个题目如果要求输出编号最小的点这个细节可以帮你少踩一个坑。3.3 复杂度与空间核算整个算法只有两次遍历每次每个节点和每条边都只会被访问一次所以时间复杂度是 O(n)。空间上sz数组int 类型约 4MB百万级dp数组long long约 8MBhead数组int约 4MBedge数组每条边存 to 和 next 两个 int无向边要存两条共 2*(n-1) 条边约 16MB合计大约 32MB对现代竞赛评测机来说是很友好的。这也是为什么我们要用静态数组而不是反复动态开辟内存vector的默认扩容策略在百万节点下会多出不少不必要的开销。4. 常见问题与排查技巧实录4.1 爆 int答案不一定是 int 能装下的这是新手最容易犯的错没有之一。深度总和最大值出现在树退化成一条链的时候如果根选在链的端点所有节点深度之和大概是 012...(n-1)也就是 n*(n-1)/2。n 到百万级别时这个值大约是 5×10^11远超 int 的范围。所以在代码里dp数组、dp[1]的累加、换根公式中的dp[v] dp[u] n - 2LL * sz[v]都必须用 long long。尤其是公式里的2LL * sz[v]如果写成2 * sz[v]两个 int 相乘可能先溢出再转 long long结果就错了。4.2 递归栈溢出与迭代改写树题的递归深度最坏情况下就是链长n 很大时递归深度可能达到百万。本地环境或者部分评测机的栈空间不够就会出现段错误。这个问题在 Windows 上尤其明显默认栈只有 1MB 左右。解法有两种。第一种是在代码里加栈空间扩增指令但这种方法依赖编译器不同环境不通用。第二种是干脆把 DFS 改成迭代这里给一个迭代版本的思路。第一次DFS可以借助栈模拟递归用三元组(u, fa, state)表示节点 u、父节点 fa、当前状态。state 为 0 表示刚进入节点需要统计深度state 为 1 表示子树已经处理完要回溯累加szvoid dfs1_iter(int root) { stacktupleint, int, int st; st.emplace(root, 0, 0); while (!st.empty()) { auto [u, fa, state] st.top(); st.pop(); if (state 0) { sz[u] 1; dp[1] (fa ? dep[fa] 1 : 0); st.emplace(u, fa, 1); for (int i head[u]; i ! -1; i edge[i].next) { int v edge[i].to; if (v fa) continue; st.emplace(v, u, 0); } } else { if (fa) sz[fa] sz[u]; } } }第二次DFS其实不需要递归用队列从根开始往下推就行因为父节点的dp值一定先算好只要保证从根到叶子的顺序即可queueint q; q.push(1); while (!q.empty()) { int u q.front(); q.pop(); for (int i head[u]; i ! -1; i edge[i].next) { int v edge[i].to; if (v fa[u]) continue; fa[v] u; dp[v] dp[u] n - 2LL * sz[v]; q.push(v); } }实际做题时如果题目明确是百万级且有链状数据建议直接用迭代版本省心很多。递归版本在多数 Linux 评测机上靠 8MB 栈或许能过但没必要赌这种运气。4.3 常见问题速查表现象可能原因解决办法样例能过但大数据点超时使用了 O(n^2) 枚举根换根DP两次遍历答案输出负数或溢出int 溢出dp和公式用 long long递归写法在本地段错误系统栈太小改成迭代栈或扩栈指令多组解输出编号错误更新方案时用了改成保留最小编号建图后遍历不到某些边head未初始化使用memset(head, -1, sizeof(head))树的父子方向混乱没有正确跳过父节点DFS参数中记录fa遍历时if (v fa) continue4.4 关于“深度基准”的坑换根公式本身不关心深度从 0 还是 1 开始两个基准下算出来的dp值差了一个常数 n最大值对应的节点不会变。但如果你第一次DFS用深度 0 初始化第二次DFS又突然用深度 1 的思路来理解公式容易在推导时把自己绕进去。建议从一开始就固定一个基准根深度为 0。这样dp[1]的物理意义就是“所有节点到 1 的距离总和”换根公式dp[v] dp[u] n - 2*sz[v]可以直接解释为距离变化不用再额外加偏移。5. 从 P3478 延伸出去的换根DP套路5.1 什么样的题需要换根DP做了这道题之后可以把换根DP的识别方法沉淀下来。通常满足下面几个特征题面要求“每个点作为根时”或者“每个点作为起点时”的某种指标朴素做法是枚举每个点做完整树遍历指标能够从相邻点的答案加上子树的某些信息推导出来最典型的就是求深度和、距离和、最大深度、最小深度这一类树上统计问题。如果只是求某一个固定根的答案那普通树形DP就够了。一旦要求“所有点”就要考虑能不能用一次预处理一次递推完成。5.2 几个常见扩展方向换根DP不只是能求深度和。如果题目要求“所有点对之间的距离总和”也可以用类似思路只不过第一次DFS除了记录子树大小通常还要记录子树内所有节点到当前根的距离和然后换根时多做一次累加。如果边权不是 1而是带权值 w公式就变成dp[v] dp[u] w * (n - 2*sz[v])。原理完全一样v 子树内的节点离根近了 w其他节点离根远了 w。如果题目要求“哪个点作为根时到所有点的最远距离最小”那就需要在换根时维护每个点为根时到子树内的最远距离和子树外的最远距离第一次DFS求子树内信息第二次DFS用父节点信息更新子树外信息本质上也是换根DP的变种。之所以说 P3478 是入门经典是因为它剥掉了所有花哨的包装把换根DP最核心的“答案如何从父节点搬到子节点”这件事直接展示了出来。把这个公式吃透后续遇到带权、求最值、求距离和的题目思路会顺畅很多。5.3 个人实操体会我个人第一次做这道题时其实是先把递归版本写好并本地跑通然后才去思考迭代写法。我的建议是学的时候可以先用最直观的vector 递归把逻辑理清楚真正提交大数据范围前再改成链式前向星 迭代。不要一上来就同时追求代码性能和逻辑简洁那样容易在写代码时犯低级错误。另外有个很实用的调试技巧小范围数据下可以写一个暴力枚举根的代码跟换根DP跑出来的dp数组逐一对拍。P3478 这种题只要dp数组所有值能对上暴力结果基本上就说明公式本身没写错剩下的问题只可能在读入、建图这些边角上。最后分享一个小技巧如果你发现换根DP推出来的公式总是不对试着把size的概念和“深度变化方向”绑在一起想而不是死记公式。当根从 u 变成 v 时v 的子树是深度变小的那部分其他部分是深度变大的那部分变化的差值就是两边节点数量的差。理解了这一点就算面试或者比赛中忘了具体公式也能在 30 秒内重新推出来。做题不是背公式而是理解公式怎么来的。P3478 教给我的正是这件事。