E换根 DP

距离和换根

深度和·带权距离和

本课摘要

距离和换根课程回答“换根时全树距离和为什么只需常数时间更新”。内容以深度和·带权距离和为主线，配合逐步推导、可编辑演示、例题与练习形成可复查的学习闭环。

  • 判断距离和换根的适用条件与状态边界
  • 围绕“深度和·带权距离和”推导转移与计算顺序
  • 用演示、复杂度分析和配套题目校验实现
本课目录 · 0 节

正在整理目录…

从「无权」到「带权」的距离和

上一节的「距离和」默认每条边长 1、每个点算 1。真实题目常常带两种权：点权（每个村庄住着不同人数 / 每个牧场有不同头数的牛）与边权（路的长短不一）。 目标变成：选一个集合点，使所有人赶来的总路程最小—— 也就是 ∑vcv⋅dis(u,v)\sum_v c_v\cdot \mathrm{dis}(u,v) 最小，其中 cvc_v 是点 vv 的人数、dis\mathrm{dis} 是带边权的树上距离。

1×22×53×14×35×4绿圈=当前最优集合点（带权距离和最小）×w = 该点人数/牛数
带点权的树：每个点标 ×w 表示人数/牛数。集合点要让「人数 × 距离」的加权总和最小。

朴素解还是「枚举每个点当集合点，各跑一遍带权 BFS/最短路累加」——O(n2)O(n^2)。 换根 DP 的思路完全不变，只是把「点数」换成「点权和」、把「1 步」换成「边权 ww 步」。

123以 1 为根：BFS123以 2 为根：再 BFS123以 3 为根：又 BFS…共 n 遍O(n²)
同样地，暴力对每个集合点各算一遍加权总距离——n 遍，O(n²)，大树上不可行。

换根系数：把「点数」升级成「点权和」

重新定义两个量：W=∑vcvW=\sum_v c_v 是总点权；sz[u]\mathrm{sz}[u] 改成 子树内点权之和（不再是节点数）。 第一遍后序：sz[u]=cu+∑c∈sonsz[c]\mathrm{sz}[u]=c_u+\sum_{c\in son}\mathrm{sz}[c]，并累加固定根的加权距离和 f[1]f[1]。

uv根 u→vv 的子树 · sz 个点每点 −1（更近）其余 n − sz 个点每点 +1（更远）Δ = +(n−sz) − sz = n − 2·sz　⇒　f[v] = f[u] + (n − 2·sz[v])
根 u→v 走一条长 w 的边：v 子树内的点权 sz[v] 各近 w，其余 W−sz[v] 各远 w。系数乘上边权 w。

根从 uu 挪到孩子 vv（这条边长 ww）时：vv 子树内那 sz[v]\mathrm{sz}[v] 的点权，每单位都近了 ww； 其余 W−sz[v]W-\mathrm{sz}[v] 的点权，每单位都远了 ww。于是带权换根方程：

f[v]=f[u]+w⋅( (W−sz[v])−sz[v] )=f[u]+w⋅(W−2 sz[v])f[v]=f[u]+w\cdot\big(\,(W-\mathrm{sz}[v])-\mathrm{sz}[v]\,\big)=f[u]+w\cdot\big(W-2\,\mathrm{sz}[v]\big)

无权是它的特例：cv≡1c_v\equiv1 时 W=nW=n、w≡1w\equiv1，方程退回 f[v]=f[u]+(n−2 sz[v])f[v]=f[u]+(n-2\,\mathrm{sz}[v])。

本质

距离和换根的通式是 f[v]=f[u]+w⋅(W−2 sz[v])f[v]=f[u]+w\cdot(W-2\,\mathrm{sz}[v])：WW 是「有多少东西要移动」（点权和），sz[v]\mathrm{sz}[v] 是「往 vv 那边挪时有多少东西变近」，ww 是「每样东西挪动的步长」。 把这三者填对，无权 / 点权 / 边权就是同一份代码。

跟着算一遍

小例子：一条链 1−2−31-2-3，点权 c=[1,1,4]c=[1,1,4]（点 3 上住了 4 个人），边权都为 1。总点权 W=6W=6。固定根 1：

1
第一遍 sz（点权和）。sz[3]=4, sz[2]=4+1=5, sz[1]=6=W\mathrm{sz}[3]=4,\ \mathrm{sz}[2]=4+1=5,\ \mathrm{sz}[1]=6=W。
2
起点 f[1]。点 1、2、3 到根 1 的距离是 0,1,20,1,2，加权和 f[1]=1⋅0+1⋅1+4⋅2=9f[1]=1\cdot0+1\cdot1+4\cdot2=9。
2
换根 1→2。系数 W−2 sz[2]=6−2×5=−4W-2\,\mathrm{sz}[2]=6-2\times5=-4。f[2]=9+(−4)=5f[2]=9+(-4)=5。 （2 那侧点权 5 各近 1，只有点 1 的权 1 远 1，净 −4-4。）
3
换根 2→3。系数 6−2×4=−26-2\times4=-2。f[3]=5+(−2)=3f[3]=5+(-2)=3。 最小在点 3——人最多的地方，把会开在那儿最省，符合直觉。
下面切换「无权 / 点权」两种模式，点节点当集合点看加权距离和，并盯住每个孩子的换根系数正负——负号指向更优的方向。

点节点，看距离和实时变

模式
点任意节点，把它设成根——立刻显示它到所有其它点的距离和。 绿圈是使距离和最小的点（d = 10），也就是树的重心方向。
1d102d113d114d165d166d167d16
当前根 = 节点 1 的距离和
d[1] = 10
总点权 W （= 点数 n）
W = 7
最小距离和（重心）
节点 1 · d = 10
以 节点 1 为根，往它的每个孩子换根时的系数 W−2⋅szW-2\cdot \mathrm{sz}：
→ 子 2：子树内 3、外 4，系数 = 7 − 2×3 = 1→ 子 3：子树内 3、外 4，系数 = 7 − 2×3 = 1

系数为负（子树内点权 > 一半）→ 往那边挪根更优； 为正→ 挪过去更差。顺着「负系数」的方向一路走，就走到重心。

n 小时：拿暴力给换根「对拍」

像「医院设置」这种 n≤100n\le 100 的题，暴力 O(n2)O(n^2)（对每个点 BFS 累加）也能过。 这反而是好事：你可以先写暴力拿到分，再写换根 O(n)O(n)，两者输出必须完全一致—— 这是验证换根系数没写错的最省心办法。等题目把 nn 放大到 105,10610^5,10^6，暴力挂了，你手里的换根已经拍过、可靠。

「医院设置」输入按二叉树的左右儿子给出，但换根不关心二叉不二叉——照样建无向邻接表，当一般树跑两遍 DFS 即可。

易错点

带权时 sz[u]\mathrm{sz}[u] 是子树点权和而非节点数——初值要写 sz[u]=cu\mathrm{sz}[u]=c_u，不是 11。 换根系数别忘了乘边权 ww。加权距离和更容易爆 intint，全程 long long\text{long long}。

例题

P2986[USACO10MAR] Great Cow Gathering GUSACO 2010提高+/省选-
题意
nn 个牧场连成树，牧场 ii 有 cic_i 头牛，边有长度。选一个牧场聚会，使所有牛走的总路程最小。
为什么选它
距离和换根的完整形态：点权（牛数）与边权（路长）同时进入系数 w⋅(W−2 sz[v])w\cdot(W-2\,\mathrm{sz}[v])。把它吃透，无权 / 只带点权 / 只带边权都是它的简化。
转移 · 复杂度
sz[u]=cu+∑sz[son]\mathrm{sz}[u]=c_u+\sum \mathrm{sz}[son]，f[v]=f[u]+w(W−2 sz[v])f[v]=f[u]+w(W-2\,\mathrm{sz}[v])；两遍 DFS，O(n)O(n)，必开 long long\text{long long}。
参考代码（点权 + 边权换根）
C++
在洛谷打开 P2986 
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

const int N = 100005;
int n;
struct E { int to; ll w; };
vector<E> g[N];
ll c[N];                      // c[u]：点 u 的牛数（点权）
ll sz[N];                     // sz[u]：子树内牛数之和（不是节点数！）
ll W;                         // 总牛数
ll f[N];                      // f[u]：把 u 当集合点时的带权距离和

// 第一遍：sz[u] = 子树牛数和；f[1] 顺带累加（子树 c 走 w 到 1）
void dfs1(int u, int fa, ll dep)
{
    sz[u] = c[u];
    f[1] += c[u] * dep;       // 以 1 为根：u 的牛各走 dep 到 1
    for (E e : g[u])
    {
        if (e.to == fa) continue;
        dfs1(e.to, u, dep + e.w);
        sz[u] += sz[e.to];
    }
}

// 第二遍：换根 f[v] = f[u] + w*(W - 2*sz[v])
void dfs2(int u, int fa)
{
    for (E e : g[u])
    {
        if (e.to == fa) continue;
        // 子树 v 的 sz[v] 头牛各近 w，其余 W - sz[v] 头牛各远 w
        f[e.to] = f[u] + e.w * (W - 2 * sz[e.to]);
        dfs2(e.to, u);
    }
}

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

    dfs1(1, 0, 0);
    dfs2(1, 0);

    ll ans = f[1];
    for (int i = 2; i <= n; i++) ans = min(ans, f[i]);
    cout << ans << endl;
    return 0;
}
P1364医院设置洛谷原生普及/提高-
题意
带居民数的二叉树，选一点设医院，使所有居民到医院的距离 × 人数之和最小。
换个视角
n≤100n\le100，是「暴力 ↔ 换根」对照的最佳载体：既能 O(n2)O(n^2) 每点 BFS，也能 O(n)O(n) 换根， 两法对拍验证。输入是左右儿子，但建成无向邻接表后当一般带点权树处理即可（边权恒 1）。
参考代码（换根 · 边权 1）
C++
在洛谷打开 P1364 
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

const int N = 105;
int n;
ll c[N];                      // 该点居民数
vector<int> g[N];
ll sz[N], f[N], W;

void dfs1(int u, int fa, ll dep)
{
    sz[u] = c[u];
    f[1] += c[u] * dep;
    for (int v : g[u])
    {
        if (v == fa) continue;
        dfs1(v, u, dep + 1);   // 医院设置边权=1
        sz[u] += sz[v];
    }
}

void dfs2(int u, int fa)
{
    for (int v : g[u])
    {
        if (v == fa) continue;
        f[v] = f[u] + (W - 2 * sz[v]);   // 无边权，系数即 W - 2*sz[v]
        dfs2(v, u);
    }
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int l, r;
        cin >> c[i] >> l >> r;   // 居民数、左儿子、右儿子（0 表示无）
        W += c[i];
        if (l) { g[i].push_back(l); g[l].push_back(i); }
        if (r) { g[i].push_back(r); g[r].push_back(i); }
    }

    dfs1(1, 0, 0);
    dfs2(1, 0);

    ll ans = f[1];
    for (int i = 2; i <= n; i++) ans = min(ans, f[i]);
    cout << ans << endl;
    return 0;
}

练习

P1395会议无权距离和求最小——本节通式里令 c≡1、w≡1 的最简特例，先拿它热身。在洛谷打开
P3478[POI2008] STA-Station深度和求最大：同一 f[]，把 min 换成 max。n≤10⁶ 提醒你 long long 与两遍 DFS 的常数。在洛谷打开
P2986[USACO10MAR] Great Cow Gathering G自测变形：试着把边权全设为 1 再跑，验证结果与『只带点权』的手算一致。在洛谷打开

已进入 距离和换根 · 换根 DP · DP大师