换根DP:距离和

1 问题

给定一棵无向无权树,对每个节点 uu,求它到所有节点的距离之和:

ans[u]=∑x=1ndist(u,x). ans[u]=\sum_{x=1}^n dist(u,x).

其中 dist(u,u)=0dist(u,u)=0,不影响总和。可用 CSES · Tree Distances II 检验实现,节点从 11 编号,n≤2⋅105n\le2\cdot10^5。

如果从每个节点出发,各遍历一次全树,时间复杂度为 O(n2)O(n^2)。换根DP先求一个节点的答案,再利用相邻节点之间的变化,在线性时间内求出全部答案。

2 固定一个根

先以 11 为根,定义:

信息 含义
sz[u]sz[u] 固定根下,uu 子树中的节点数
down[u]down[u] uu 到其子树中所有节点的距离之和

孩子先于父亲计算,有:

sz[u]=1+∑v∈C(u)sz[v],down[u]=∑v∈C(u)(down[v]+sz[v]). \begin{aligned} sz[u]&=1+\sum_{v\in C(u)}sz[v],\\ down[u]&=\sum_{v\in C(u)}\bigl(down[v]+sz[v]\bigr). \end{aligned}

从 uu 到孩子 vv 子树中的每个点,都比从 vv 出发多走一条边,所以额外加上 sz[v]sz[v]。

根的子树就是全树,因此 ans[1]=down[1]ans[1]=down[1]。其他节点的 downdown 只包含子树内部贡献,还不是它的全树答案。

3 沿边换根

考虑固定根下的一条父子边 (u,v)(u,v)。从节点 uu 出发改成从 vv 出发时,删除这条边后形成的两部分决定距离的变化:

  • vv 子树中的 sz[v]sz[v] 个点,距离都减少 11。
  • 其余 n−sz[v]n-sz[v] 个点,距离都增加 11。

从 1 移到相邻节点 3 时,右侧 3、4、5 的距离各减一,左侧 1、2 的距离各加一

所以:

ans[v]=ans[u]−sz[v]+(n−sz[v])=ans[u]+n−2sz[v]. \begin{aligned} ans[v]&=ans[u]-sz[v]+(n-sz[v])\\ &=ans[u]+n-2sz[v]. \end{aligned}

这里的 sz[v]sz[v] 始终按最初的根 11 计算。我们只是改变距离的出发点,不需要修改树的存储、父子关系或子树大小。第二遍始终沿最初的父子方向递推。

4 计算顺序

两遍计算分别满足不同的依赖关系:

  1. 孩子先于父亲:求 szsz、downdown,得到 ans[1]ans[1]。
  2. 父亲先于孩子:利用 ans[u]ans[u] 和 sz[v]sz[v],求 ans[v]ans[v]。

可以使用两次 DFS,也可以先记录父亲先于孩子的遍历顺序。倒序处理完成第一遍,正序处理完成第二遍。后者不依赖递归栈,适合很长的链。

5 手算示例

图中的树有边 (1,2),(1,3),(3,4),(3,5)(1,2),(1,3),(3,4),(3,5)。从 11 出发,距离分别为 0,1,1,2,20,1,1,2,2,所以 ans[1]=6ans[1]=6。

节点 vv sz[v]sz[v] down[v]down[v] 换根计算 ans[v]ans[v]
1 5 6 初始根 6
2 1 0 6+5−2×16+5-2\times1 9
3 3 2 6+5−2×36+5-2\times3 5
4 1 0 5+5−2×15+5-2\times1 8
5 1 0 5+5−2×15+5-2\times1 8

从 11 移到 33,有三个点变近、两个点变远,总和减少 11。从 33 移到叶子 44,只有一个点变近、四个点变远,总和增加 33。

6 正确性

第一遍的子树划分互不重叠,公式将每个孩子子树的内部距离整体增加一条边,故正确求出 szsz 与 downdown,初始答案 ans[1]ans[1] 正确。

对任意父子边,边的两侧恰好划分全树所有节点,每个节点的距离变化都已计入 n−2sz[v]n-2sz[v]。若父节点答案正确,递推得到的孩子答案也正确。

第二遍中父亲先于孩子,每个节点都能沿从初始根到它的唯一路径得到正确答案。

7 代码实现

下面的完整程序读入 nn 和 n−1n-1 条无向边,按编号输出每个节点的距离和,对应 CSES Tree Distances II。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 200000 + 5;

vector<int> g[maxn];
int fa[maxn], order[maxn], sz[maxn];
ll down[maxn], ans[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    order[1] = 1;
    int total = 1;
    for (int i = 1; i <= total; ++i) {
        int u = order[i];
        for (int v : g[u]) {
            if (v == fa[u]) continue;
            fa[v] = u;
            order[++total] = v;
        }
    }

    // 第一遍:孩子先于父亲,统计子树大小与子树内部距离和。
    for (int i = total; i >= 1; --i) {
        int u = order[i];
        sz[u] = 1;
        for (int v : g[u]) {
            if (v == fa[u]) continue;
            sz[u] += sz[v];
            down[u] += down[v] + sz[v];  // 孩子子树中每个点都要多走一条边
        }
    }

    ans[1] = down[1];
    // 第二遍:父亲先于孩子,沿父子边推导全树答案。
    for (int i = 2; i <= total; ++i) {
        int v = order[i], u = fa[v];
        ans[v] = ans[u] + n - 2LL * sz[v];
    }

    for (int u = 1; u <= n; ++u) {
        cout << ans[u] << (u == n ? '\n' : ' ');
    }
    return 0;
}

时间复杂度为 O(n)O(n),空间复杂度为 O(n)O(n)。链的端点距离和为 n(n−1)/2n(n-1)/2,在本题范围内会超过 int,所以距离和使用 long long。

8 点权与边权

若节点 xx 有权值 axa_x,目标改为:

D[u]=∑xax dist(u,x). D[u]=\sum_x a_x\,dist(u,x).

记全树点权和为 WW,固定根下子树点权和为 S[v]S[v]。若边 (u,v)(u,v) 长度为 ℓ\ell,两侧点的距离分别变化 −ℓ-\ell、+ℓ+\ell,于是:

D[v]=D[u]+(W−2S[v])ℓ. D[v]=D[u]+\bigl(W-2S[v]\bigr)\ell.

第一遍相应改为:

S[u]=au+∑vS[v],down[u]=∑v(down[v]+S[v]ℓuv). S[u]=a_u+\sum_v S[v],\qquad down[u]=\sum_v\bigl(down[v]+S[v]\ell_{uv}\bigr).

点权控制一份距离贡献的倍数,边权控制一次移动的长度,两者作用不同。将点权和边长都设为 11,就回到无权公式。

带权完整代码

下面采用通用输入格式:第一行 nn,第二行 nn 个点权,之后 n−1n-1 行为 u v 长度。输出每个节点的加权距离和。它与具体例题的输入格式不同,使用时需要对应调整。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 200000 + 5;

struct Edge {
    int to;
    ll w;
};

vector<Edge> g[maxn];
int fa[maxn], order[maxn];
ll weight[maxn], sub[maxn], down[maxn], ans[maxn], parent_len[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    for (int u = 1; u <= n; ++u) cin >> weight[u];
    for (int i = 1; i < n; ++i) {
        int u, v;
        ll len;
        cin >> u >> v >> len;
        g[u].push_back({v, len});
        g[v].push_back({u, len});
    }

    order[1] = 1;
    int total = 1;
    for (int i = 1; i <= total; ++i) {
        int u = order[i];
        for (auto [v, len] : g[u]) {
            if (v == fa[u]) continue;
            fa[v] = u;
            parent_len[v] = len;
            order[++total] = v;
        }
    }

    for (int i = total; i >= 1; --i) {
        int u = order[i];
        sub[u] = weight[u];
        for (auto [v, len] : g[u]) {
            if (v == fa[u]) continue;
            sub[u] += sub[v];
            down[u] += down[v] + sub[v] * len;
        }
    }

    ans[1] = down[1];
    ll total_weight = sub[1];
    for (int i = 2; i <= total; ++i) {
        int v = order[i], u = fa[v];
        ans[v] = ans[u] + (total_weight - 2 * sub[v]) * parent_len[v];
    }

    for (int u = 1; u <= n; ++u) {
        cout << ans[u] << (u == n ? '\n' : ' ');
    }
    return 0;
}

模板使用 long long 保存点权和、乘积与答案。需要按数据范围检查这些量,例如 n≤2⋅105n\le2\cdot10^5、点权和边长均在 0∼10000\sim1000 时,答案不超过 4⋅10164\cdot10^{16},可以安全保存。

9 应用

  • luogu P1364: 医院设置:点权是居民人数,边长为 11,求所有 D[u]D[u] 的最小值;输入为每个节点的人数与两个孩子编号。
  • luogu P3478: [POI 2008] STA-Station:所有点权、边长均为 11,求距离和最大的节点,输出编号。原题 n≤106n\le10^6,需要相应扩大数组。

无权树上,使距离和最小的节点与 树的重心 有关;换根DP则直接求出了每个候选节点的完整目标值。

10 相关题解

暂无相关题解