换根DP:最远距离

1 问题

给定一棵无向无权树,对每个节点 uu,求它到全树节点的最远距离:

ans[u]=max⁡xdist(u,x). ans[u]=\max_x dist(u,x).

可用 CSES · Tree Distances I 检验实现,节点从 11 编号,n≤2⋅105n\le2\cdot10^5。单节点树的答案规定为 00。

在 换根DP:距离和 中,可以从总和里减去一棵子树的贡献;最大值没有这样的减法。给孩子传递信息时,需要另外解决排除这个孩子自身贡献的问题。

2 内外划分

先以 11 为根,定义:

状态 含义
down[u]down[u] uu 到其子树内部节点的最远距离
up[u]up[u] uu 到子树外节点或 uu 自身的最远距离

两个状态都允许停在 uu,距离为 00。因此叶子的 downdown 为 00,根没有子树外节点,up[root]=0up[root]=0。

任意目标节点都在子树内或子树外,所以:

ans[u]=max⁡(down[u],up[u]). ans[u]=\max(down[u],up[u]).

3 向下的距离

要走向 uu 的子树内部,或者停在 uu,或者先到某个孩子 vv,再沿它的子树向下走:

down[u]=max⁡(0,max⁡v∈C(u)(down[v]+1)). down[u]=\max\left(0,\max_{v\in C(u)}\bigl(down[v]+1\bigr)\right).

孩子先于父亲计算即可。这里一个孩子提供的贡献是 down[v]+1down[v]+1,其中 11 是边 (u,v)(u,v) 的长度。

4 向上的距离

对孩子 vv,若目标位于它的子树外,第一步必须走到 uu。到达 uu 后,有三种去向:

  1. 停在 uu,后续距离为 00。
  2. 继续往 uu 的父亲方向走,后续距离由 up[u]up[u] 提供。
  3. 进入另一个孩子 cc 的子树,后续距离为 down[c]+1down[c]+1,要求 c≠vc\ne v。

因此:

up[v]=1+max⁡(up[u],0,max⁡c∈C(u), c≠v(down[c]+1)). up[v]=1+\max\left(up[u],0,\max_{c\in C(u),\,c\ne v}\bigl(down[c]+1\bigr)\right).

不能直接使用 1+max⁡(up[u],down[u])1+\max(up[u],down[u])。 如果 down[u]down[u] 来自 vv,这会让路径走到 uu 后又回到 vv 子树,重复经过边 (u,v)(u,v),不再是简单路径。

计算节点 2 的向上距离时,应走 2-1-5-6,不能从 1 返回 2 的子树;需要保留来自孩子 5 的次大贡献

图中,down[1]=3down[1]=3 来自孩子 22,不能用于计算 up[2]up[2]。另一个孩子 55 提供距离 22,所以 up[2]=1+2=3up[2]=1+2=3。

5 最大与次大

若对每个孩子都重新扫描其他孩子,一颗星形树就会产生 O(n2)O(n^2) 的时间开销。只需保存:

信息 含义
down[u]down[u] 最大孩子贡献,与 00 取最大值
second[u]second[u] 排除一个最大贡献来源后,剩余孩子的最大贡献,与 00 取最大值
from[u]from[u] 提供当前最大贡献的孩子编号

给孩子 vv 传递时:

other={second[u],from[u]=v,down[u],from[u]≠v,up[v]=1+max⁡(up[u],other). other=\begin{cases} second[u],&from[u]=v,\\ down[u],&from[u]\ne v, \end{cases} \qquad up[v]=1+\max(up[u],other).

second 表示不同孩子提供的第二份贡献,不是严格小于最大值的下一个数值。如果两个孩子都贡献 44,最大与次大都应为 44;排除其中一个,另一个仍然可用。

代码按孩子编号记录最大值来源。遇到与最大值相等的新贡献时,仍然可以更新次大值。没有其他孩子时,次大值保留为 00,表示到达父节点后停下。

如果只存最大值,排除其来源后直接退回 00,也会出错:图中会漏掉孩子 55 的贡献,把 up[2]up[2] 从 33 算成 11,进一步把 ans[2]ans[2] 从 33 算成 22。

6 手算示例

沿用图中的六节点树:边为 (1,2),(2,3),(3,4),(1,5),(5,6)(1,2),(2,3),(3,4),(1,5),(5,6)。

节点 downdown secondsecond 最大来源 fromfrom upup ansans
1 3 2 2 0 3
2 2 0 3 3 3
3 1 0 4 4 4
4 0 0 无 5 5
5 1 0 6 4 4
6 0 0 无 5 5

例如,给 55 传递时,节点 11 的最大贡献来自另一个孩子 22,所以 up[5]=1+3=4up[5]=1+3=4;给 66 传递时,没有兄弟子树,使用 up[5]up[5],得到 up[6]=1+4=5up[6]=1+4=5。

7 正确性

第一遍按后序计算。任何向子树内部的路径,都唯一属于停在本点或进入某个孩子的情况,取最大值便得到正确的 downdown;同时保留的前两份贡献,足以回答排除任意一个孩子后的最大值。

第二遍中,孩子子树外的目标节点,按路径从父节点出发的下一方向,分为父节点自身、父亲方向和其他孩子方向。转移完整覆盖了这三类,并排除了重新进入当前孩子的非法路径,因此得到正确的 upup。

父亲先于孩子处理,所有外部状态都能依次求出。最后将内部与外部取最大值,就是全树最远距离。

8 代码实现

与上一篇相同,先记录父亲先于孩子的顺序,倒序计算向下信息,再正序计算向上信息,避免长链递归。

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

const int maxn = 200000 + 5;

vector<int> g[maxn];
int fa[maxn], order[maxn];
int down[maxn], second[maxn], from[maxn], up[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];
        for (int v : g[u]) {
            if (v == fa[u]) continue;
            int value = down[v] + 1;
            if (value > down[u]) {
                second[u] = down[u];
                down[u] = value;
                from[u] = v;
            } else if (value > second[u]) {
                second[u] = value;
            }
        }
    }

    // 第二遍:向孩子传递不经过它自身子树的最远距离。
    for (int i = 1; i <= total; ++i) {
        int u = order[i];
        ans[u] = max(down[u], up[u]);
        for (int v : g[u]) {
            if (v == fa[u]) continue;
            int other = (from[u] == v ? second[u] : down[u]);
            up[v] = 1 + max(up[u], other);  // 先到 u,再向父亲方向或兄弟子树走
        }
    }

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

每个节点只扫描邻接表常数次,时间复杂度为 O(n)O(n),空间复杂度为 O(n)O(n)。无权树的最远距离不超过 n−1n-1,使用 int 即可。

9 非负边权

若边长非负,将孩子的贡献改为 down[v]+ℓuvdown[v]+\ell_{uv},向上转移改为:

up[v]=ℓuv+max⁡(up[u],other). up[v]=\ell_{uv}+\max(up[u],other).

最大、次大、向上距离和答案都要使用足够大的类型,通常为 long long。排除孩子的逻辑保持不变,仍按贡献来源区分。上述以 00 为基准的写法允许路径只含一个节点;不能直接拿去求“含负边且必须经过边”的最长路径。

10 直径与中心

ans[u]ans[u] 也称节点 uu 的偏心距。所有 ans[u]ans[u] 的最大值是树的直径长度,最小值是半径,达到最小值的节点是树的中心。

无权树上也可以先求 树的直径 的两个端点 A,BA,B,再用 ans[u]=max⁡(dist(u,A),dist(u,B))ans[u]=\max(dist(u,A),dist(u,B)) 求解。本篇的内外划分适用于更一般的树上信息传递,关键是明确每个方向提供什么,以及如何排除接收方自身的贡献。

树的中心最小化最远距离;树的重心 控制删除节点后各连通块的大小,二者定义不同。

11 相关题解

暂无相关题解