树形动态规划中的换根法与全源路径优化

核心逻辑与数学原理

树形动态规划（Tree DP）的进阶形态中，二次扫描与换根法（Re-rooting / Up-and-Down Tree DP）专用于解决“全源树路径拓扑问题”。

在普通树形 DP 中，我们通常假定一个固定的节点（如 $1$ 号节点）为根。此时状态只能沿着拓扑轴自底向上（从子节点向父节点）回溯贡献。如果题目要求计算以树中每一个节点各自作为根节点时的全局统计量（如：以节点 $i$ 为根时，所有节点到 $i$ 的距离之和），暴力对每个节点跑一次 $O(N)$ 的 DFS 会导致 $O(N^2)$ 的灾难性复杂度。

换根法通过两次扫描，在 $O(N)$ 的线性时间内，利用局部状态的拓扑平移，无损映射出全源状态。

1. 第一次扫描：自底向上（Down-to-Up）

• 几何映射：任选一个节点（通常为 $1$ 号节点）作为初相根。

• 物理语义：执行一次标准 DFS，计算出两个局部的核心拓扑贡献量：

  • $size[u]$：以 $u$ 为根的子树内的节点总数。
  • $f[u]$：以 $u$ 为根的子树内，所有节点到 $u$ 的距离之和。

• 回溯递推：当子节点 $v$ 状态固化后，向父节点 $u$ 传递贡献：

$$size[u] = 1 + \sum_{v \in \text{son}(u)} size[v]$$

$$f[u] = \sum_{v \in \text{son}(u)} (f[v] + size[v])$$

2. 第二次扫描：自顶向下（Up-to-Down / 换根演变）

• 几何映射：设当前已求得作为整棵树的根时，该节点的全局总距离为 $g[u]$（初相时，$g[1] = f[1]$）。现在，我们要将树的几何重心从父节点 $u$ 强行平移到它的直接子节点 $v$ 上。

• 状态差分拓扑演变：当根从 $u$ 换到 $v$ 时，整棵树的几何拓扑发生如下突变：

  • 原本属于 $v$ 的子树内的所有节点（共 $size[v]$ 个），由于根节点的靠近，它们到新根的距离全部减少了 1。
  • 原本在 $v$ 子树之外的所有节点（共 $N - size[v]$ 个），由于根节点的远离，它们到新根的距离全部增加了 1。

• 数学化归（换根方程）：

$$g[v] = g[u] - size[v] + (N - size[v]) = g[u] + N - 2 \cdot size[v]$$

通过这个 $O(1)$ 的代数差分方程，我们可以在第二次自顶向下的 DFS 推进中，顺着边直接秒杀出子节点 $v$ 作为全局根时的真实统计量。

状态设计与算法推导

1. 状态空间定义

• $size[u]$：以 $1$ 为全局根时，节点 $u$ 的子树节点规模。
• $f[u]$：以 $1$ 为全局根时，节点 $u$ 内部子树对其产生的局部距离贡献。
• $g[u]$：以 $u$ 节点作为整棵树的几何根时，全源所有节点到 $u$ 的最终距离总和（即最终的目标状态轴）。

2. 拓扑推进控制矩阵

• 第一轮 dfs_down(u, fa)：后序遍历。叶子触底反弹，利用 $f[v]$ 和 $size[v]$ 强刷 $f[u]$ 与 $size[u]$。
• 第二轮 dfs_up(u, fa)：前序遍历。在向下递推进入子节点之前，利用父节点已经成型的全局状态 $g[u]$，通过换根方程直接激活子节点的全局状态 $g[v]$，再递归进入 $v$。

C++ 标准源码（NOIP风格）

以下源码解决经典全源树路径和问题：“求树中哪个节点作为根时，所有节点到它的距离之和最小，并输出该最小值”，严格兼容 Linux g++ -O2 编译标准。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 200005;

int n;
vect...  // 省略中间部分

    cout << min_dist << "\n";

    return 0;
}

NOIP 实战避坑指南

1. 第二次扫描时前序与后序位置颠倒

• 现象：在第二轮 dfs_up 中，选手将换根方程写在了递归调用的后面：

  // 错误示范
  dfs_up(v, u);
  g[v] = g[u] + n - 2 * size_tree[v]; 

这会导致当前分支在向下递归时，子节点 $v$ 及其下属的所有后代节点使用的依然是初始未赋值的 0 或脏数据。当递归回溯回来时才去更新 $g[v]$，整张全源状态网格会全面崩溃。

• 规避手段：换根法第二轮扫描是标准的自顶向下（前序遍历位置）。必须先利用父节点状态算出当前子节点的全局解，然后再放行递归指令。

2. 换根乘法溢出与常数系数符号写反

• 现象：方程中的减耗项与增耗项弄反，误写成 g[v] = g[u] - (n - size_tree[v]) + size_tree[v]。或在节点总数 $N \ge 10^5$ 时，由于距离总和会突破 $2 \times 10^9$，中间计算使用了标准 int 导致整型溢出（Integer Overflow）变成负数。
• 规避手段：树形换根涉及大范围整型累加，所有存储距离、权值、子树大小的数组及局部变量，在考场上一律强制使用 long long 维护。

经典 NOIP/洛谷 真题

1. 洛谷 P3478 [STA-Station]

• 题意描述：给定一棵 $N$ 个节点的无根树，要求构造一个有根树，使得这棵树的所有节点的深度之和最大。这里的深度定义为该节点到根节点的简单路径上的边数。$N \le 10^6$。
• 问题本质与解题思路：教科书级的换根 DP 模板题。
• 核心思路：节点到根的边数即为距离。完全套用上文推导的换根模型。第一轮 DFS 求出以 $1$ 为根时所有节点的深度和，第二轮前序 DFS 通过 $g[v] = g[u] + N - 2 \cdot size[v]$ 线性刷出全源解。最后 $O(N)$ 扫描挑出最大值对应的节点编号。由于数据量达到 $10^6$，注意需要通过 ios_base::sync_with_stdio(false) 解除 I/O 锁优化效率。

2. 洛谷 P2986 [USACO10MAR] Great Cow Gathering G

• 题意描述：有 $N$ 个谷仓被 $N-1$ 条无向道路连接成一棵树。每个谷仓内存放着 $C_i$ 头奶牛。现在要把所有谷仓的奶牛集中到一个谷仓中开会。每条道路都有一个特定的长度 $L_i$。奶牛走过一条路产生的总走动成本 = 奶牛数量 $\times$ 道路长度。求将所有奶牛集中到哪一个谷仓时，总走动成本最小。
• 问题本质与解题思路：带点权与边权特化的树上全源重心换根。
• 核心思路：点权为奶牛数，边权为道路长度。
• 状态修正：
  1. 第一次扫描自底向上：$size[u]$ 变更为以 $u$ 为根的子树内的奶牛总数（即子树内的点权和）。$f[u] = \sum (f[v] + size[v] \cdot \text{len}(u, v))$。
  2. 第二次扫描自顶向下：设全局总奶牛数为 $\text{TotalCow}$。当会议地点从父节点 $u$ 转移到子节点 $v$ 时，连接它们的这条边权为 $W$。原本在 $v$ 子树内部的奶牛少走了 $W$ 的距离，外部的奶牛多走了 $W$ 的距离。
  3. 换根方程特化：

$$g[v] = g[u] - size[v] \cdot W + (\text{TotalCow} - size[v]) \cdot W$$

通过将简单的节点计数升维映射为权值计数，完美解决带权树上重心的全源快速定位。