洛谷 P3478（POI 2008 STA-Station）是我见过最适合入门换根DP的题目，没有之一。题面非常直白：给你一棵树，找出一个节点来做根，让所有节点的深度之和最大。如果数据范围小，直接每个点跑一遍DFS就完事，但这题的数据规模接近百万量级，O(n^2) 根本跑不动。换根DP的做法，就是先随便选一个根把答案算出来，再通过一个 O(1) 的递推式把答案“搬”到相邻节点上，整棵树每个点都能在 O(n) 时间内得到答案。这篇文章就沿着这条主线，把状态定义、公式推导、两份可提交的代码，以及那些容易被坑的细节一次说清楚。适合刚学完树形DP、但遇到“每个点都要当一次根”这类问题容易懵的选手，也适合想系统理解换根DP套路的人。
1. 项目概述：旧题新解，换根DP的经典模板
1.1 题目到底在问什么
题目给出一棵无根树，要求我们选一个点作为根，计算出这棵树上所有节点的深度之和。这里“深度”可以定义为根节点为 0，也可以定义为根节点为 1，题目本身不会因为这个基准不同而改变答案对应的那个节点，后面推导公式的时候这点会自然体现出来。
举个例子，假设树长这样：
- 1-2
- 2-3
- 3-4
- 2-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 换到 2：
dp[2] = dp[1] + n - 2 * sz[2] = 8 + 5 - 2 * 4 = 5手动以 2 为根算一下深度总和：节点深度为 1、0、1、2、1，总和确实是 5。公式正确。
从 2 换到 3：
dp[3] = dp[2] + n - 2 * sz[3] = 5 + 5 - 2 * 2 = 6从 3 换到 4：
dp[4] = dp[3] + n - 2 * sz[4] = 6 + 5 - 2 * 1 = 9最后答案是 9，对应节点 4，跟最开始手动枚举的结果一致。整棵树的答案表如下：
| 根节点 | 深度总和 |
|---|---|
| 1 | 8 |
| 2 | 5 |
| 3 | 6 |
| 4 | 9 |
| 5 | 8 |
最大值出现在节点 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 能装下的
这是新手最容易犯的错，没有之一。深度总和最大值出现在树退化成一条链的时候，如果根选在链的端点，所有节点深度之和大概是 0+1+2+...+(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 表示子树已经处理完，要回溯累加sz：
void dfs1_iter(int root) { stack<tuple<int, 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值一定先算好，只要保证从根到叶子的顺序即可：
queue<int> 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) continue |
4.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 教给我的，正是这件事。
