洛谷P10962题解：换根DP算法详解与应用

1. 项目概述：洛谷P10962与换根DP算法

洛谷P10962是一道典型的树形动态规划问题，题目名为"Computer"，考察的是换根DP（也称为二次扫描法）这一经典算法技巧。这道题要求我们在树结构中找到最优根节点，使得以该节点为根时所有节点的深度之和最大。这类问题在算法竞赛中具有重要地位，也是大厂面试中考察树形DP的常见题型。

我第一次接触这道题时，也被其O(n^2)暴力解法与O(n)优化解法之间的思维跳跃所震撼。通过系统学习换根DP，不仅能解决这类特定问题，更能培养对树形结构的深刻认知。下面我将结合自己的刷题经验，详细解析这道题的解题思路和实现细节。

2. 问题分析与暴力解法

2.1 题目理解与建模

题目给出一个N个节点的树（无向无环图），要求找到一个根节点，使得所有节点到根的深度之和最大。这里的深度定义为节点到根的路径边数。例如：

1 / \ 2 3 / \ 4 5

若以1为根，深度和为0+1+1+2+2=6；以3为根，深度和为1+2+0+1+1=5。

2.2 暴力解法实现

最直观的做法是枚举每个节点作为根，通过DFS计算总深度和：

int maxSum = -INF, bestRoot = 0; for (int root = 1; root <= n; root++) { int sum = 0; function<void(int, int, int)> dfs = [&](int u, int fa, int dep) { sum += dep; for (int v : tree[u]) { if (v != fa) dfs(v, u, dep + 1); } }; dfs(root, -1, 0); if (sum > maxSum) { maxSum = sum; bestRoot = root; } }

这种解法时间复杂度为O(n^2)，当n=1e6时显然无法通过。我们需要寻找线性解法。

3. 换根DP核心思想

3.1 算法直觉建立

观察暴力解法，发现每次换根后大量计算是重复的。例如从父节点u切换到子节点v时，只有u和v之间连接的子树深度发生变化。具体来说：

• v的子树中所有节点深度减1
• 非v子树中所有节点深度加1

这种变化可以用数学表达式描述。设f[u]表示以u为根的总深度和，sz[v]表示以v为根的子树大小，则有转移方程：

f[v] = f[u] - sz[v] + (n - sz[v]) = f[u] + n - 2 * sz[v]

3.2 算法步骤拆解

换根DP通常分为三个阶段：

1. 预处理阶段：任选一个根(通常选1)，计算每个节点的子树大小sz和初始深度dep
2. 第一次DFS：计算基准根(如root=1)的答案f[1]
3. 第二次DFS：根据转移方程计算其他节点作为根时的答案

4. 详细实现与优化

4.1 数据结构准备

const int N = 1e6 + 10; vector<int> tree[N]; int sz[N], dep[N], f[N]; int n; // 节点数

4.2 预处理DFS实现

void dfs1(int u, int fa) { sz[u] = 1; dep[u] = fa == -1 ? 0 : dep[fa] + 1; for (int v : tree[u]) { if (v == fa) continue; dfs1(v, u); sz[u] += sz[v]; } }

4.3 换根DFS实现

void dfs2(int u, int fa) { for (int v : tree[u]) { if (v == fa) continue; f[v] = f[u] + n - 2 * sz[v]; dfs2(v, u); } }

4.4 主函数逻辑

int main() { cin >> n; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; tree[u].push_back(v); tree[v].push_back(u); } dfs1(1, -1); // 计算f[1] for (int i = 1; i <= n; i++) f[1] += dep[i]; dfs2(1, -1); int maxSum = *max_element(f + 1, f + n + 1); cout << maxSum << endl; return 0; }

5. 算法正确性证明

5.1 转移方程推导

设u是v的父节点，当根从u变为v时：

1. v的子树中所有节点深度减1 → 总和减少sz[v]
2. 其他节点深度加1 → 总和增加(n - sz[v]) 因此总变化量为：-sz[v] + (n - sz[v]) = n - 2*sz[v]

5.2 边界情况验证

考虑链式树1-2-3：

• 以1为根：f[1]=0+1+2=3
• 转移到2：f[2]=3+3-2*2=2 (0+1+1=2)
• 转移到3：f[3]=2+3-2*1=3 (0+1+2=3) 结果正确。

6. 复杂度分析与优化

6.1 时间复杂度

• 两次DFS都是O(n)
• 总时间复杂度O(n)

6.2 空间复杂度

• 邻接表存储树：O(n)
• 额外数组：sz,dep,f各O(n)
• 总空间O(n)

6.3 常数优化技巧

1. 使用前向星替代vector存图（节省约30%内存）
2. 递归DFS改为迭代DFS（防止栈溢出）
3. 合并两次DFS（某些情况下可行）

7. 常见错误与调试技巧

7.1 典型错误案例

1. 子树大小计算错误：忘记初始化sz[u]=1
2. 根节点处理错误：未正确处理fa==-1的情况
3. 转移方向错误：在dfs2中错误处理父子关系

7.2 调试方法

1. 打印中间变量：在dfs中输出sz和dep
2. 小数据测试：手动计算3-4个节点的树
3. 对拍：写暴力程序与优化程序对比

重要提示：当n很大时，递归DFS可能导致栈溢出。在OJ提交时需要注意栈空间设置，或者改用非递归实现。

8. 算法扩展与应用

8.1 带权树扩展

如果边有长度w，转移方程变为：

f[v] = f[u] - sz[v]*w + (n - sz[v])*w = f[u] + (n - 2*sz[v])*w

8.2 其他换根DP问题

1. 树上最长路径：记录每个节点到子树最远距离和次远距离
2. 树上黑白染色：统计满足特定颜色分布的方案数
3. 树形背包问题：结合分组背包思想处理子树合并

8.3 实际工程应用

1. 网络拓扑中的中心节点选择
2. 分布式系统中的数据放置策略
3. 社交网络中的影响力最大化

9. 同类题目推荐

1. 洛谷P2986：Great Cow Gathering（带权版本）
2. CF1324F：Maximum White Subtree（颜色统计）
3. POJ3107：Godfather（找重心应用）
4. 洛谷P3647：连珠线（复杂状态设计）
5. 洛谷P5536：核心城市（多维度换根）

10. 个人心得与进阶建议

在实际刷题过程中，我发现换根DP最难的部分是状态转移方程的推导。以下是我的几点经验：

1. 画图辅助：一定要在纸上画出父子节点转换的示意图
2. 增量分析：重点分析根节点变化时哪些部分发生了改变
3. 小数据验证：用3-4个节点的树手动计算验证方程
4. 模板整理：总结自己的代码模板，包括常用变量名和初始化逻辑

对于想深入掌握树形DP的同学，建议按照以下路径学习：

1. 基础树形DP（最大独立集等）
2. 换根DP
3. 树上背包
4. 虚树与树上数据结构结合

最后提醒一点：在竞赛中遇到换根DP问题时，通常n都很大（1e5-1e6量级），务必确保算法是线性复杂度。我曾在一次比赛中因为没注意数据范围，写了O(nlogn)的解法导致TLE，这个教训非常深刻。