1. 换根DP的核心思想与应用场景换根DP也称为二次扫描法是树形动态规划中的一种特殊技巧主要用于解决需要以不同节点为根进行多次计算的问题。这类问题的典型特征是我们需要对树中的每个节点作为根的情况进行计算但直接暴力枚举每个节点作为根会导致O(n²)的时间复杂度这在处理大规模树结构时如n1e6显然不可行。换根DP的精妙之处在于它通过两次深度优先搜索DFS将时间复杂度优化到O(n)第一次DFS以任意节点通常选择1号节点为根计算子树相关信息第二次DFS利用父节点的信息推导子节点的信息实现换根操作这种技巧在以下场景特别有用需要找到使某种树指标最优的根节点如最大深度和、最小代价等需要对每个节点作为根时计算全局性质树结构动态变化时需要快速重新计算全局信息提示换根DP不是一种独立的算法而是对常规树形DP的优化技巧。掌握它需要先熟悉基础的树形DP和DFS遍历。2. 洛谷P10962问题解析2.1 题目重述与理解原题描述为给定一棵N个节点的树找出一个节点作为根使得所有节点的深度之和最大。其中节点深度定义为到根节点的距离边数树是无向无环连通图典型数据范围N ≤ 1e6这个问题如果采用暴力解法对每个节点作为根进行一次DFS计算深度和时间复杂度为O(n²)对于n1e6显然会超时1e12次操作。这正是换根DP大显身手的场景。2.2 暴力解法的局限性让我们先看看暴力解法的伪代码max_sum -inf best_root None for each node u in tree: total 0 perform DFS/BFS with u as root: for each node v: total depth[v] if total max_sum: max_sum total best_root u这种解法的问题在于每次换根都重新计算所有节点的深度没有利用之前计算的信息对于每个节点都进行O(n)的遍历整体O(n²)复杂度在树结构不变的情况下存在大量重复计算3. 换根DP的数学推导3.1 定义关键变量我们需要定义几个关键变量来帮助推导sz[u]以u为根的子树大小节点数dep[u]在初始根通常为节点1下的深度f[u]以u为根时的深度和即我们要求的量3.2 第一次DFS预处理第一次DFS以节点1为根计算两个基本信息每个节点的子树大小sz[u]每个节点到根节点的深度dep[u]同时我们可以计算出f[1]以1为根时的深度和def dfs1(u, parent): sz[u] 1 for v in children of u: if v parent: continue dep[v] dep[u] 1 dfs1(v, u) sz[u] sz[v] f[1] dep[u] # 累加所有节点的深度3.3 第二次DFS换根转移这是换根DP的核心部分。当我们从父节点u转移到子节点v时如何快速计算f[v]关键观察当根从u变为v时v的子树中所有节点的深度都减1因为它们离根更近了不在v子树中的节点深度都加1因为它们离根更远了因此转移方程为f[v] f[u] - sz[v] (n - sz[v])简化为f[v] f[u] n - 2 * sz[v]实现代码def dfs2(u, parent): for v in children of u: if v parent: continue f[v] f[u] n - 2 * sz[v] dfs2(v, u)4. 完整算法实现与优化4.1 C完整代码示例#include iostream #include vector using namespace std; const int MAXN 1e6 5; vectorint tree[MAXN]; int sz[MAXN], dep[MAXN]; long long f[MAXN]; int n; void dfs1(int u, int parent) { sz[u] 1; for (int v : tree[u]) { if (v parent) continue; dep[v] dep[u] 1; dfs1(v, u); sz[u] sz[v]; } } void dfs2(int u, int parent) { for (int v : tree[u]) { if (v parent) continue; f[v] f[u] n - 2 * sz[v]; dfs2(v, u); } } 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, 0); for (int i 1; i n; i) f[1] dep[i]; dfs2(1, 0); long long max_sum -1; int best_root 0; for (int i 1; i n; i) { if (f[i] max_sum) { max_sum f[i]; best_root i; } } cout best_root endl; return 0; }4.2 算法复杂度分析时间复杂度O(n)两次DFS都是O(n)的遍历最后的查找最大值也是O(n)空间复杂度O(n)存储树结构O(n)各种数组O(n)4.3 边界条件与注意事项树的存储对于大规模数据n1e6务必使用邻接表而非邻接矩阵数据类型深度和可能很大n²级别使用long long而非int初始根选择理论上可以选择任意节点作为初始根但通常选择1号节点最方便递归深度对于极端链状树递归DFS可能导致栈溢出可以改用BFS或显式栈实现5. 相关例题与变式5.1 洛谷P2986 [USACO10MAR] Great Cow Gathering题目变式每个节点有牛的数量c[i]边有长度w求使所有牛到根的总距离最小的根节点。解法调整sz[u]改为子树中牛的总数转移方程变为f[v] f[u] (total_cows - 2 * sz[v]) * w(u,v)5.2 洛谷P3047 [USACO12FEB] Nearby Cows题目特点对每个节点求距离不超过k的节点权值和。解法思路定义f[u][k]为以u为根距离不超过k的和第一次DFS计算子树贡献第二次DFS合并父亲节点的贡献注意去重处理5.3 实战技巧总结换根DP的通用思考步骤确定要计算的信息设计第一次DFS计算的子树信息推导换根时的转移方程实现第二次DFS完成信息传递常见错误忘记处理父节点与子节点的关系导致循环调用转移方程推导错误数据类型范围不足调试技巧先用小样例验证打印中间结果检查对比暴力解法的结果在实际编程竞赛中换根DP是一个强大的工具掌握它可以在处理树形问题时游刃有余。建议通过大量练习来熟悉各种变式和技巧。
