跳转至

树的直径

定义：对于一棵树，其直径定义为所有简单路径中最长的一条。

性质 1：直径的中点 \(u\) 是 \(\max_{i\in V}{d(u,i)}\) 最小（距离的最大值最小）的一个点； 性质 2：对于树上的任意点，任意一条直径两端点中总有一个能成为离其最远的点； 性质 3（可合并性）：两个点集合并后的直径端点，一定在合并前各自直径对应的四个端点之中；

常见用法：从直径出发考虑问题，处理距离最值相关问题。

判断方法

两次 dfs

任意选择一个节点 \(u\) 作为起点遍历整棵树，找到距离 \(u\) 距离最远的节点，记为 \(z\)。再以 \(z\) 为起点遍历整棵树，找到距离 \(z\) 最远的一个节点 \(z'\)，根据性质 \(2\) 和直径的定义，\(z\rightarrow z'\) 的唯一路径就是树的一条直径。

注意负权边

性质依赖于所有边的边权非负。因此如果存在负权边，需要使用树上 DP 求解。

树上 DP

维护每个子树从根出发的最长路径和次长路径，考虑每个节点成为路径的 lca 时最长的路径。

例题

CF1632E2 Distance Tree (hard version)

题目大意

给定一棵 \(n\) 个点的树，定义 \(d(x)\) 为 \(1\) 到 \(x\) 的距离，定义 \(f(v)\) 为，在树上添加一条长为 \(v\) 的边后 \(\max_{x=1}^n d(x)\) 的最小值。对于 \(1\le v\le n\)，求出 \(f(v)\)。

\(n\le 3\times 10^5\)

首先容易发现加边的一端一定是 \(1\) 号节点，否则调整为 \(1\) 号节点后一定不劣。

考虑二分答案，假设当前要判断加一条长度为 \(v\) 的边能否使所有 \(d(i)\le lim\)。如果点 \(i\) 原先就满足 \(d(i)\le lim\)，则无需考虑。对于 \(d(i)>lim\)，需要满足 \(dis(u,i)+v\le lim\)。记 \(S=\{i\mid d(i)>lim\}\)，也即最小化 \(\max_{i\in S}\{dis(u,i)\}\)。

根据树的直径性质 1，\(u\) 应该选在点集 \(S\) 的一条直径的中点位置。记直径长度为 \(len\)，此时 \(\max_{i\in S}\{dis(u,i)\}=\lceil\frac{len}{2}\rceil\)。那应该如何求出这条直径的长度呢？

直径的两个端点有许多性质。记距离 \(1\) 号节点最远的节点为 \(mx\)，其总存在于 \(S\) 中。容易证明点集 \(S\) 必有一条直径，其一端为 \(mx\)。我们可以使用反证法，假设直径不经过 \(mx\)，然后会推出 \(mx\) 不是距离 \(1\) 节点最远的节点，矛盾。

这样，我们只需要先求出 \(mx\)，再预处理出 \(mx\) 到每个节点的距离，对每个 \(lim\) 求出 \(\max_{d(i)\ge lim}\{dis(mx,i)\}\)，即是直径的长度 \(len\)。

至此我们得到了一个 \(O(n\log n)\) 的做法。

注意到随着 \(v\) 的增大，答案 \(ans\) 也单调递增，并且始终满足 \(ans\in[1,n]\)（即增量为 \(O(n)\)）。因此我们可以倒序枚举 \(v\)，并保留上一次得到的 \(ans\)。只需要不断 check(ans-1)，如果合法则 --ans。这样就可以将时间复杂度均摊为 \(O(n)\)。

技巧

对于一个不等式形式的约束条件，可以将其转化为一个求最值的问题，然后判断求得的最值能否满足条件即可。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<iostream>
#include<cstring>
using namespace std;
const int N = 3E5 + 10;
const int INF = (int)0x3f3f3f3f3f3f3f3f;

struct Edge {
    int v;
    int next;
} pool[2 * N];
int nn, head[N];

void addEdge(int u, int v) {
    pool[++nn] = {v, head[u]};
    head[u] = nn;
}

int T, n;
int d[2][N], f[N], res[N];

void dfs(int u, int f, int o) {
    if(f) d[o][u] = d[o][f] + 1;
    for(int i = head[u]; i; i = pool[i].next) {
        int v = pool[i].v;
        if(v == f) continue;
        dfs(v, u, o);
    }
}

bool check(int lim, int v) {
    return (f[lim + 1] + 1) / 2 <= lim - v;
}

int main() {

    cin >> T;
    while(T--) {
        cin >> n;
        nn = 0;
        for(int i = 0; i <= n + 5; i++) {
            head[i] = 0;
            f[i] = -INF;
            d[0][i] = d[1][i] = 0;
        }
        for(int i = 1; i <= n - 1; i++) {
            int u, v;
            cin >> u >> v;
            addEdge(u, v);
            addEdge(v, u);
        }
        dfs(1, 0, 0);
        int mx = 1;
        for(int i = 2; i <= n; i++) {
            if(d[0][i] > d[0][mx]) mx = i;
        }
        dfs(mx, 0, 1);
        for(int i = 1; i <= n; i++) {
            f[d[0][i]] = max(f[d[0][i]], d[1][i]);
        }
        for(int i = n; i >= 2; i--) {
            f[i - 1] = max(f[i - 1], f[i]);
        }
        int ans = n;
        for(int i = n; i >= 1; i--) {
            while(ans > 1 && check(ans - 1, i)) --ans;
            res[i] = ans;
        }
        for(int i = 1; i <= n; i++) {
            cout << res[i] << ' ';
        }
        cout << '\n';
    }

    return 0;
}