E换根 DP

换根基础模型

二次扫描骨架

本课摘要

换根基础模型课程回答“一次定根结果如何在线性时间转移到所有根”。内容以二次扫描骨架为主线，配合逐步推导、可编辑演示、例题与练习形成可复查的学习闭环。

  • 判断换根基础模型的适用条件与状态边界
  • 围绕“二次扫描骨架”推导转移与计算顺序
  • 用演示、复杂度分析和配套题目校验实现
本课目录 · 0 节

正在整理目录…

同一个量，要对「每个点」都算一遍

换根 DP 解决这样一类问题：给一棵无根树，要对每一个点，都算出「把它当根时的某个量」—— 比如「它到所有其它点的距离之和」「它的子树深度和」。注意关键词是每一个点：不是求一个全局最优，而是要 nn 个答案。

先看最朴素的想法：枚举每个点当根，各自跑一遍遍历。以某点为根做一次 BFS/DFS，就能得到它到全树的距离和，O(n)O(n)。 但要对 nn 个点都这么做，总共就是 O(n2)O(n^2)。

123以 1 为根：BFS123以 2 为根：再 BFS123以 3 为根：又 BFS…共 n 遍O(n²)
暴力：把每个点轮流当根，各自从头遍历一遍——同样的树被反复走了 n 遍，总计 O(n²)。

n≤106n\le 10^6 时 O(n2)O(n^2) 直接爆炸。可这 nn 遍遍历里藏着大量重复： 相邻两个点当根，绝大多数点到它们的距离只差了「一步」。换根 DP 正是要抓住这个「只差一步」， 让相邻根之间 O(1)O(1) 递推，把 O(n2)O(n^2) 压回 O(n)O(n)。

两遍 DFS：先立地基，再顺边换根

换根 DP 的骨架是两遍 DFS，以「深度和 / 距离和」为例（每条边长 1、每个点算 1）：

1234567第一遍后序求 sz第二遍前序换根合计 O(n)
第一遍后序（叶→根）求子树大小 sz[]，第二遍前序（根→叶）顺着边把根一路换下去——两遍合计 O(n)。

第一遍 · 后序，固定一个根（记作 1）。求出每个点的子树大小 sz[u]\mathrm{sz}[u]（= 它自己 + 各孩子子树大小之和）。因为父要用到子的结果，必须子先于父，所以是后序。 顺手把固定根的距离和 f[1]=∑idep(1,i)f[1]=\sum_i \mathrm{dep}(1,i) 也累加出来——这是唯一一个「老实一层层加」得到的答案，作为换根的起点。

第二遍 · 前序，从根出发把根「挪」给每个孩子。关键是想清楚：根从 uu 挪到相邻的孩子 vv 时，距离和怎么变？

uv根 u→vv 的子树 · sz 个点每点 −1（更近）其余 n − sz 个点每点 +1（更远）Δ = +(n−sz) − sz = n − 2·sz　⇒　f[v] = f[u] + (n − 2·sz[v])
根 u→v：v 的子树里 sz[v] 个点各近 1 步（−sz），其余 n−sz[v] 个点各远 1 步（+）。净变化 = n − 2·sz[v]。

把根从 uu 移到孩子 vv，相当于所有点相对根「整体挪了一条边」：落在 vv 子树里的 sz[v]\mathrm{sz}[v] 个点，离新根近了 1；其余 n−sz[v]n-\mathrm{sz}[v] 个点，离新根远了 1。于是

f[v]=f[u]+(n−sz[v])−sz[v]=f[u]+(n−2 sz[v])f[v]=f[u]+\big(n-\mathrm{sz}[v]\big)-\mathrm{sz}[v]=f[u]+\big(n-2\,\mathrm{sz}[v]\big)

一次加法就把 f[v]f[v] 算出来了。沿树前序递归，每条边做一次这样的 O(1)O(1) 更新，走完就得到所有点的答案。 边界：起点 f[1]f[1] 由第一遍给出。

本质

换根 DP = 「固定根的一份答案」+「相邻根之间的 O(1)O(1) 增量」。第一遍 DFS 花 O(n)O(n) 立好地基（sz[]\mathrm{sz}[] 与起点 f[root]f[\text{root}]）， 第二遍 DFS 用 f[v]=f[u]+Δf[v]=f[u]+\Delta 把答案沿边「传染」出去。把 nn 次独立遍历，换成一次遍历里 nn 个相互推导的增量。

跟着算一遍

用一条 5 个点的链 1−2−3−4−51-2-3-4-5 手推（无权，求每点距离和）。固定根取 1：

1
第一遍求 sz。从叶子 5 往上：sz[5]=1, sz[4]=2, sz[3]=3, sz[2]=4, sz[1]=5\mathrm{sz}[5]=1,\ \mathrm{sz}[4]=2,\ \mathrm{sz}[3]=3,\ \mathrm{sz}[2]=4,\ \mathrm{sz}[1]=5。
2
起点 f[1]。以 1 为根，深度为 0,1,2,3,40,1,2,3,4，距离和 f[1]=0+1+2+3+4=10f[1]=0+1+2+3+4=10。
3
换根 1→2。n=5, sz[2]=4n=5,\ \mathrm{sz}[2]=4，系数 5−2×4=−35-2\times4=-3。f[2]=f[1]+(−3)=10−3=7f[2]=f[1]+(-3)=10-3=7。 （2 那侧 4 个点各近 1，只有点 1 远 1，净 −3-3，合理。）
4
继续换到底。f[3]=f[2]+(5−2×3)=7−1=6f[3]=f[2]+(5-2\times3)=7-1=6；f[4]=f[3]+(5−2×2)=6+1=7f[4]=f[3]+(5-2\times2)=6+1=7；f[5]=f[4]+(5−2×1)=7+3=10f[5]=f[4]+(5-2\times1)=7+3=10。 最小在中点 3（f[3]=6f[3]=6）——正是链的重心，符合直觉。
下面的演示把这两遍扫描逐帧放给你看：先看 sz[] 自底向上点亮，再看根顺着边一步步换、每步只做一次加法。换棵树试试。

看两遍扫描跑起来

选一棵树
准备
已暂停，第 1 步，共 16 步，1 倍速
1234567
先固定节点 1 为根：第一遍后序求子树，第二遍沿边 O(1) 换根。
暴力 · 每点各跑一遍 BFS
O(n²) · 共访问 49 次
换根 · 两遍 DFS 合计
O(n) · 约 14 步
第一遍点亮 = sz[] 已求第二遍点亮 = 该点距离和已求当前处理 / 当前根

暴力的 O(n2)O(n^2) 是「每个点都从头 BFS 一遍」；换根只走两遍 DFS 就把全部 nn 个点的答案填满。

写法要点：无根树、任取一根、别回头

换根题的输入几乎都是无根树（只给 n−1n-1 条无向边）。实现时统一套路： 用 vector<int> g[N]\text{vector<int> g[N]} 存双向邻接表，DFS 时传一个 fa\text{fa}（父亲）参数， 遇到 v==fav==\text{fa} 就跳过——这样就把无向图当有根树遍历，不会走回头路。

两遍 DFS 都从固定根 1 出发：dfs1\text{dfs1} 后序累加 sz\mathrm{sz}（递归返回后再 +=+= 子树），dfs2\text{dfs2} 前序换根（先算 f[v]f[v] 再递归进 vv，保证父答案已就绪）。n≤106n\le 10^6 时递归可能栈深较大——洛谷默认栈够用，实在担心可手写栈迭代。

易错点

换根的增量必须用「相对固定根 1」算出的 sz[v]\mathrm{sz}[v]（第一遍那套）， 而不是「相对当前根」。第二遍前序时每个 sz[v]\mathrm{sz}[v] 都是固定值，别在换根途中去改它。 另外距离和常常爆 intint（n=106n=10^6 时和可达 101210^{12}），全程开 long long\text{long long}。

想直接上手？到 E 部分页的「换根巡礼」点节点当根，实时看距离和，再点「看 DP 最优」一次算出全部点、找出重心。

例题

P3478[POI2008] STA-StationPOI 2008提高+/省选-
题意
给一棵 nn 个点的树，找一个点作根，使所有点的深度之和最大，输出这个点。
为什么选它
换根 DP 的官方模板题：深度和 = 距离和，转移就是最干净的 f[v]=f[u]+(n−2 sz[v])f[v]=f[u]+(n-2\,\mathrm{sz}[v])。本题求最大（越浅的点当根、越多点被拉深）， 正好和「会议」求最小对照——同一个 f[]f[]，一个取 max、一个取 min。
转移 · 复杂度
f[1]=∑dep(1,i)f[1]=\sum \mathrm{dep}(1,i) 起步，f[v]=f[u]+(n−2 sz[v])f[v]=f[u]+(n-2\,\mathrm{sz}[v]) 换根；两遍 DFS，O(n)O(n)。n≤106n\le 10^6 必开 long long\text{long long}。
参考代码（两遍 DFS · 求最大）
C++
在洛谷打开 P3478 
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

const int N = 1000005;
int n;
vector<int> g[N];             // 邻接表
ll sz[N];                     // sz[u]：以 1 为根时 u 的子树节点数
ll f[N];                      // f[u]：以 u 为根时的深度和（距离和）
ll dep[N];                    // dep[u]：以 1 为根时 u 的深度

// 第一遍：后序求子树大小 sz[]，顺带累加 f[1] = Σ dep[i]
void dfs1(int u, int fa)
{
    sz[u] = 1;
    for (int v : g[u])
    {
        if (v == fa) continue;
        dep[v] = dep[u] + 1;
        dfs1(v, u);
        sz[u] += sz[v];       // 子必先算好——所以后序
    }
}

// 第二遍：前序换根 f[v] = f[u] + (n - 2*sz[v])
void dfs2(int u, int fa)
{
    for (int v : g[u])
    {
        if (v == fa) continue;
        f[v] = f[u] + (n - 2 * sz[v]);   // ★O(1) 换根：子树内 sz 个近 1，其余远 1
        dfs2(v, u);
    }
}

int main()
{
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    dep[1] = 0;
    dfs1(1, 0);
    for (int i = 1; i <= n; i++)
        f[1] += dep[i];        // 以 1 为根的深度和 = 起点

    dfs2(1, 0);

    int best = 1;
    for (int i = 1; i <= n; i++)
        if (f[i] > f[best]) best = i;   // 本题求深度和最大的点

    cout << best << endl;
    return 0;
}
P1395会议洛谷原生普及+/提高
题意
树上 nn 个点，选一个点开会，使所有点到它的距离和最小，输出该点与最小距离和。
对应关系
无权距离和 = 深度和，与 P3478 是同一个 f[]f[]，只是这里取 min⁡\min。n≤5×104n\le 5\times10^4——足以卡掉 O(n2)O(n^2) 的每点重算，是「从暴力过渡到换根」最好的一题。
参考代码（换 max 为 min）
C++
在洛谷打开 P1395 
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

const int N = 50005;
int n;
vector<int> g[N];
ll sz[N], f[N], dep[N];

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

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

int main()
{
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    dfs1(1, 0);
    for (int i = 1; i <= n; i++) f[1] += dep[i];
    dfs2(1, 0);

    int best = 1;
    for (int i = 1; i <= n; i++)
        if (f[i] < f[best]) best = i;   // 会议：求距离和最小的点
    cout << best << " " << f[best] << endl;
    return 0;
}

练习

P2986[USACO10MAR] Great Cow Gathering G带权 + 带边权距离和：换根系数升级为 w·(W − 2·sz)，sz 改成子树『牛数』之和。见下一类型精讲。在洛谷打开
P3047[USACO12FEB] Nearby Cows G距离 ≤ k 的点权和：状态多一维 dp[u][j]，换根要『父贡献减去自身子树贡献』。见『子树内外合并』。在洛谷打开
P1364医院设置n≤100，可先写 O(n²) 暴力对拍，再用换根 O(n) 验证——最适合亲手体会两种复杂度的落差。在洛谷打开

已进入 换根基础模型 · 换根 DP · DP大师