引言
树形动态规划（Tree DP）是处理树上问题的利器。然而，许多问题要求以树中每个节点作为”根”来计算答案，如果对每个节点都重新跑一次DP，时间复杂度将达到O(n²)。换根DP（Re-rooting DP 或 Rerooting Technique）通过两次DFS遍历，巧妙地利用父子节点之间的状态转移关系，在O(n)时间内求出所有节点作为根时的答案。本文将以”树的重心与最大子树”和”节点到其他所有节点的距离和”两个经典问题为例，深入讲解换根DP的核心思想。
核心算法概述
1. 第一次DFS：自底向上收集信息
从任意节点（通常是1号节点）出发，通过DFS计算每个节点作为子树根时的状态。这一阶段只考虑子树内的信息，不考虑父节点方向。
2. 第二次DFS：自顶向下传递信息
利用父节点已经计算出的全局信息，推导子节点作为整棵树根时的答案。关键在于建立父子状态之间的转移方程。
3. 状态转移的核心
假设我们已经知道以u为根的答案dp[u]，现在要求以v（u的子节点）为根的答案dp[v]。需要：
1. 从u的状态中”去掉”v子树的贡献
2. 将u的剩余部分作为v的一个”新子树”
3. 重新计算v作为整棵树根时的状态
Java完整实现
import java.util.*;
/**
* 换根DP完整实现
* 解决：每个节点作为根时的最优值计算
*/
public class RerootingDP {
private int n;
private ArrayList<Integer>[] tree;
public RerootingDP(int n) {
this.n = n;
tree = new ArrayList[n + 1];
for (int i = 0; i <= n; i++) {
tree[i] = new ArrayList<>();
}
}
public void addEdge(int u, int v) {
tree[u].add(v);
tree[v].add(u);
}
/**
* 问题1：计算每个节点作为根时，最大子树的大小
* 子树大小 = 该子树中包含的节点数
* 对于根节点，最大子树 = max(各子节点的子树大小, n - 根所在子树)
*
* 应用场景：找树的重心（最大子树最小的节点）
*/
public int[] solveMaxSubtreeSize() {
// 第一次DFS：计算每个节点的子树大小
int[] subtreeSize = new int[n + 1];
Arrays.fill(subtreeSize, 1); // 每个节点至少包含自己
// 记录父节点，避免回到父节点
int[] parent = new int[n + 1];
Arrays.fill(parent, -1);
// 后序遍历计算子树大小
dfs1(1, parent, subtreeSize);
// 第二次DFS：换根计算每个节点作为根时的最大子树
int[] maxSubtree = new int[n + 1];
dfs2(1, parent, subtreeSize, maxSubtree, n);
return maxSubtree;
}
/**
* 第一次DFS：自底向上计算子树大小
*/
private void dfs1(int u, int[] parent, int[] subtreeSize) {
for (int v : tree[u]) {
if (v == parent[u]) continue;
parent[v] = u;
dfs1(v, parent, subtreeSize);
subtreeSize[u] += subtreeSize[v];
}
}
/**
* 第二次DFS：自顶向下换根
* 核心思想：当根从u换到子节点v时
* - v原来的子树还是v的子树
* - u的其余部分（整棵树 - v的子树）变成了v的一个新子树
*/
private void dfs2(int u, int[] parent, int[] subtreeSize, int[] maxSubtree, int n) {
// 计算u作为根时的最大子树大小
int max = n - subtreeSize[u]; // u向上连接的部分（如果u不是原根）
for (int v : tree[u]) {
if (v == parent[u]) continue;
max = Math.max(max, subtreeSize[v]); // 各子节点的子树
}
maxSubtree[u] = max;
// 向子节点传递信息
for (int v : tree[u]) {
if (v == parent[u]) continue;
// 关键：在递归v之前，临时调整subtreeSize
// 因为v要把u的其余部分看作自己的一个子树
int oldSizeU = subtreeSize[u];
int oldSizeV = subtreeSize[v];
// u失去了v子树，v获得了u的其余部分
subtreeSize[u] -= subtreeSize[v];
subtreeSize[v] += subtreeSize[u];
dfs2(v, parent, subtreeSize, maxSubtree, n);
// 恢复（回溯）
subtreeSize[u] = oldSizeU;
subtreeSize[v] = oldSizeV;
}
}
/**
* 问题2：计算每个节点到其他所有节点的距离之和
* 即：对每个节点u，求 sum(dist(u, v)) for all v
*
* 换根公式：
* 设dp[u] = u到其他所有节点的距离和
* 当根从u换到子节点v时：
* dp[v] = dp[u] + (n - 2 * subtreeSize[v])
* 解释：v比u更接近其subtreeSize[v]个节点（距离-1），
* 但比u远离其余 n - subtreeSize[v] 个节点（距离+1）
*/
public long[] solveDistanceSum() {
int[] parent = new int[n + 1];
Arrays.fill(parent, -1);
int[] subtreeSize = new int[n + 1];
Arrays.fill(subtreeSize, 1);
long[] dp = new long[n + 1];
// 第一次DFS：计算子树大小和根节点(1)的距离和
dfsDistance1(1, parent, subtreeSize, dp);
// 第二次DFS：换根计算所有节点的距离和
dfsDistance2(1, parent, subtreeSize, dp);
return dp;
}
private void dfsDistance1(int u, int[] parent, int[] subtreeSize, long[] dp) {
for (int v : tree[u]) {
if (v == parent[u]) continue;
parent[v] = u;
dfsDistance1(v, parent, subtreeSize, dp);
subtreeSize[u] += subtreeSize[v];
dp[u] += dp[v] + subtreeSize[v]; // v子树中所有节点到u的距离 = 到v的距离 + 1
}
}
private void dfsDistance2(int u, int[] parent, int[] subtreeSize, long[] dp) {
for (int v : tree[u]) {
if (v == parent[u]) continue;
// 换根公式推导：
// dp[u] 包含：v子树中subtreeSize[v]个节点，它们到u的距离 = 到v的距离 + 1
// 其余 n - subtreeSize[v] 个节点，它们到u的距离 = 到v的距离 - 1（当v为根时）
// 所以 dp[v] = dp[u] - subtreeSize[v] + (n - subtreeSize[v])
// = dp[u] + n - 2 * subtreeSize[v]
dp[v] = dp[u] + n - 2L * subtreeSize[v];
dfsDistance2(v, parent, subtreeSize, dp);
}
}
/**
* 问题3：每个节点作为根时的树高度（树的最长链）
* 需要维护每个节点的最长链和次长链
*/
public int[] solveTreeHeight() {
int[] parent = new int[n + 1];
Arrays.fill(parent, -1);
// 第一次DFS：计算每个节点的最长下行链
int[] down1 = new int[n + 1]; // 最长下行链
int[] down2 = new int[n + 1]; // 次长下行链
dfsHeight1(1, parent, down1, down2);
// 第二次DFS：计算每个节点作为根时的树高度
int[] height = new int[n + 1];
dfsHeight2(1, parent, down1, down2, height, 0);
return height;
}
private void dfsHeight1(int u, int[] parent, int[] down1, int[] down2) {
for (int v : tree[u]) {
if (v == parent[u]) continue;
parent[v] = u;
dfsHeight1(v, parent, down1, down2);
int candidate = down1[v] + 1;
if (candidate > down1[u]) {
down2[u] = down1[u];
down1[u] = candidate;
} else if (candidate > down2[u]) {
down2[u] = candidate;
}
}
}
private void dfsHeight2(int u, int[] parent, int[] down1, int[] down2, int[] height, int up) {
// up表示从u向上走的最长链长度
height[u] = Math.max(down1[u], up);
for (int v : tree[u]) {
if (v == parent[u]) continue;
// 计算v向上走的最长链
// 如果v在u的最长链路径上，则v只能用次长链
int use = (down1[u] == down1[v] + 1) ? down2[u] : down1[u];
int newUp = Math.max(up, use) + 1;
dfsHeight2(v, parent, down1, down2, height, newUp);
}
}
/**
* 问题4：通用换根DP模板
* 适用于：节点值与子树信息有关，需要求每个节点作为根时的值
*
* 示例：每个节点作为根时，所有节点值乘以深度的和
*/
public long[] solveGeneric(long[] nodeValues) {
int[] parent = new int[n + 1];
Arrays.fill(parent, -1);
int[] subtreeSize = new int[n + 1];
long[] subtreeSum = new long[n + 1]; // 子树节点值之和
long[] dp = new long[n + 1]; // dp[u] = 以u为根时的目标值
// 第一次DFS
dfsGeneric1(1, parent, subtreeSize, subtreeSum, nodeValues, dp);
// 第二次DFS
dfsGeneric2(1, parent, subtreeSize, subtreeSum, nodeValues, dp);
return dp;
}
private void dfsGeneric1(int u, int[] parent, int[] subtreeSize,
long[] subtreeSum, long[] nodeValues, long[] dp) {
subtreeSize[u] = 1;
subtreeSum[u] = nodeValues[u];
for (int v : tree[u]) {
if (v == parent[u]) continue;
parent[v] = u;
dfsGeneric1(v, parent, subtreeSize, subtreeSum, nodeValues, dp);
subtreeSize[u] += subtreeSize[v];
subtreeSum[u] += subtreeSum[v];
dp[u] += dp[v] + subtreeSum[v]; // v子树的贡献整体+1层深度
}
}
private void dfsGeneric2(int u, int[] parent, int[] subtreeSize,
long[] subtreeSum, long[] nodeValues, long[] dp) {
for (int v : tree[u]) {
if (v == parent[u]) continue;
// 换根：v获得u的其余部分
// v子树原本贡献为 dp[v]（深度以v为0计算）
// 以u为根时，v子树贡献为 dp[v] + subtreeSum[v]（深度+1）
// u的其余部分贡献为 dp[u] - (dp[v] + subtreeSum[v])
// 以v为根时，u的其余部分深度+1，贡献增加 (totalSum - subtreeSum[v])
long totalSum = subtreeSum[u]; // 注意：这里subtreeSum[u]应该是整棵树的总和
dp[v] = dp[u] + (totalSum - 2 * subtreeSum[v]);
// 调整subtreeSum用于后续递归
long oldSumU = subtreeSum[u];
long oldSumV = subtreeSum[v];
subtreeSum[u] -= subtreeSum[v];
subtreeSum[v] = totalSum;
dfsGeneric2(v, parent, subtreeSize, subtreeSum, nodeValues, dp);
subtreeSum[u] = oldSumU;
subtreeSum[v] = oldSumV;
}
}
public static void main(String[] args) {
// 构建测试树
// 1
// / | \
// 2 3 4
// / \ \
// 5 6 7
RerootingDP solver = new RerootingDP(7);
solver.addEdge(1, 2);
solver.addEdge(1, 3);
solver.addEdge(1, 4);
solver.addEdge(2, 5);
solver.addEdge(2, 6);
solver.addEdge(4, 7);
// 测试1：最大子树大小
System.out.println("=== 问题1：每个节点作为根时的最大子树大小 ===");
int[] maxSubtree = solver.solveMaxSubtreeSize();
for (int i = 1; i <= 7; i++) {
System.out.printf("节点 %d: 最大子树 = %d%n", i, maxSubtree[i]);
}
// 找重心
int minMax = Integer.MAX_VALUE, centroid = -1;
for (int i = 1; i <= 7; i++) {
if (maxSubtree[i] < minMax) {
minMax = maxSubtree[i];
centroid = i;
}
}
System.out.println("树的重心: 节点 " + centroid + " (最大子树=" + minMax + ")");
// 测试2：距离和
System.out.println("\n=== 问题2：每个节点到其他所有节点的距离和 ===");
long[] distanceSum = solver.solveDistanceSum();
for (int i = 1; i <= 7; i++) {
System.out.printf("节点 %d: 距离和 = %d%n", i, distanceSum[i]);
}
// 测试3：树高度
System.out.println("\n=== 问题3：每个节点作为根时的树高度 ===");
int[] height = solver.solveTreeHeight();
for (int i = 1; i <= 7; i++) {
System.out.printf("节点 %d: 树高度 = %d%n", i, height[i]);
}
// 验证：手动计算节点1的高度
// 1为根时：最长链 1->2->5 或 1->2->6 或 1->4->7，长度都是2（边数）
// 但height[]存储的是节点数还是边数？这里存储的是最长链的边数
System.out.println("\n节点1的高度应为2（边数）: " + height[1]);
}
}
/**
* 进阶应用：树上最大独立集（换根版本）
* 计算每个节点作为根时的最大独立集大小
*/
class TreeMaximumIndependentSet {
private int n;
private ArrayList<Integer>[] tree;
// dp0[u] = 不选u时，u子树的最大独立集
// dp1[u] = 选u时，u子树的最大独立集
private int[] dp0, dp1;
private int[] parent;
public TreeMaximumIndependentSet(int n) {
this.n = n;
tree = new ArrayList[n + 1];
for (int i = 0; i <= n; i++) tree[i] = new ArrayList<>();
dp0 = new int[n + 1];
dp1 = new int[n + 1];
parent = new int[n + 1];
Arrays.fill(parent, -1);
}
public void addEdge(int u, int v) {
tree[u].add(v);
tree[v].add(u);
}
/**
* 第一次DFS：自底向上计算DP
*/
public void dfs1(int u) {
dp0[u] = 0;
dp1[u] = 1; // 选u，初始贡献1
for (int v : tree[u]) {
if (v == parent[u]) continue;
parent[v] = u;
dfs1(v);
dp0[u] += Math.max(dp0[v], dp1[v]); // 不选u，子节点可选可不选
dp1[u] += dp0[v]; // 选u，子节点不能选
}
}
/**
* 第二次DFS：换根
* f0[u] = 不选u时，整棵树的最大独立集
* f1[u] = 选u时，整棵树的最大独立集
*
* 换根公式推导：
* 以u为根时，f0[u] = dp0[u]（子树已包含全部信息）
*
* 当换到子节点v时：
* v原来计算dp时，认为u是它的父节点，dp0[v] += max(dp0[u_child], dp1[u_child])
* 现在v成为根，u变成了v的一个子节点
* 需要"去掉"原来u作为父节点的贡献，重新加入u作为子节点的贡献
*/
public void dfs2(int u, int[] f0, int[] f1) {
f0[u] = dp0[u];
f1[u] = dp1[u];
for (int v : tree[u]) {
if (v == parent[u]) continue;
// 保存原始值
int oldDp0U = dp0[u];
int oldDp1U = dp1[u];
int oldDp0V = dp0[v];
int oldDp1V = dp1[v];
// 重新计算u作为v的子节点时的dp值
// 先去掉v对u的贡献
dp0[u] -= Math.max(dp0[v], dp1[v]);
dp1[u] -= dp0[v];
// 然后以u为子节点，计算v的新dp值
// v原来的dp0[v]和dp1[v]是基于u作为父节点计算的
// 现在需要基于u作为子节点重新计算
// 实际上dp0[v]和dp1[v]的公式只依赖子节点，u不是v的子节点
// 所以v的dp值不变！只需要给v添加u作为新子节点的贡献
int newDp0V = dp0[v] + Math.max(dp0[u], dp1[u]);
int newDp1V = dp1[v] + dp0[u];
dp0[v] = newDp0V;
dp1[v] = newDp1V;
// 递归
dfs2(v, f0, f1);
// 恢复
dp0[u] = oldDp0U;
dp1[u] = oldDp1U;
dp0[v] = oldDp0V;
dp1[v] = oldDp1V;
}
}
public int[] solve() {
dfs1(1);
int[] f0 = new int[n + 1];
int[] f1 = new int[n + 1];
dfs2(1, f0, f1);
int[] ans = new int[n + 1];
for (int i = 1; i <= n; i++) {
ans[i] = Math.max(f0[i], f1[i]);
}
return ans;
}
public static void main(String[] args) {
// 测试：链状树 1-2-3-4-5
TreeMaximumIndependentSet solver = new TreeMaximumIndependentSet(5);
solver.addEdge(1, 2);
solver.addEdge(2, 3);
solver.addEdge(3, 4);
solver.addEdge(4, 5);
int[] ans = solver.solve();
System.out.println("=== 树上最大独立集（换根） ===");
for (int i = 1; i <= 5; i++) {
System.out.printf("节点 %d 为根: 最大独立集 = %d%n", i, ans[i]);
}
// 链状树的最大独立集：隔一个选一个，5个节点的链应为3
System.out.println("期望所有结果都是3");
}
}
算法复杂度分析
| 问题 | 预处理 | 每次查询 | 总复杂度 | 空间复杂度 |
|---|---|---|---|---|
| 子树大小 | O(n) | O(1) | O(n) | O(n) |
| 距离和 | O(n) | O(1) | O(n) | O(n) |
| 树高度 | O(n) | O(1) | O(n) | O(n) |
| 最大独立集 | O(n) | O(1) | O(n) | O(n) |
关键知识点总结
-
两次遍历的哲学：换根DP的本质是”收集-传递”。第一次DFS自底向上收集子树信息，第二次DFS自顶向下将父节点的全局信息传递给子节点。
-
换根公式的推导：从u换到v时，关键是识别”v子树”和”u的其余部分”这两个互补集合。状态转移通常形如
dp[v] = dp[u] + f(n, subtreeSize[v])。 -
距离和的经典公式：
dp[v] = dp[u] + n - 2 * size[v]，这个公式在树形DP中极为常用。其本质是：v比u更接近size[v]个节点，但远离n - size[v]个节点。 -
回溯恢复技巧：在递归子节点前临时修改父节点的状态，递归结束后再恢复。这种方法避免了为每个节点单独存储额外信息，使代码更加简洁。
-
应用场景：换根DP广泛应用于树的重心、节点距离和、树的最长路径、子树合并问题、树形背包等场景，是竞赛编程和面试中的高频考点。
