树的直径

发表于 分类于 本文字数： 681 阅读时长 ≈ 2 分钟
本文系统介绍树的直径的两种经典求法：通过两次 DFS 找到直径端点 & 以及利用树形 DP 计算每个节点的最长与次长向下链从而得到全局直径。

树的直径

树的直径有两种求法，一种是两次dfs，一种是树形dp

两次dfs

从任意一点跑dfs找到最远点，这个点是直径的一段，再从这个点dfs到最远端，也就是直径的另外一端

这个oiwiki上讲的很细，但我更喜欢他的证明

证明

使用反证法。记出发节点为 $y$。设真实的直径是 $\delta(s,t)$，而从 $y$ 进行的第一次 DFS 到达的距离其最远的节点 $z$ 不为 $t$ 或 $s$。共分三种情况：

  • 若 $y$ 在 $\delta(s,t)$ 上：

y 在 st 上

有 $\delta(y,z) > \delta(y,t) \Longrightarrow \delta(x,z) > \delta(x,t) \Longrightarrow \delta(s,z) > \delta(s,t)$，与 $\delta(s,t)$ 为树上任意两节点之间最长的简单路径矛盾。

  • 若 $y$ 不在 $\delta(s,t)$ 上，且 $\delta(y,z)$ 与 $\delta(s,t)$ 存在重合路径：

有重合路径

有 $\delta(y,z) > \delta(y,t) \Longrightarrow \delta(x,z) > \delta(x,t) \Longrightarrow \delta(s,z) > \delta(s,t)$，与 $\delta(s,t)$ 为树上任意两节点之间最长的简单路径矛盾。

  • 若 $y$ 不在 $\delta(s,t)$ 上，且 $\delta(y,z)$ 与 $\delta(s,t)$ 不存在重合路径：

y 不在 st 上

有 $\delta(y,z) > \delta(y,t) \Longrightarrow \delta(x’,z) > \delta(x’,t) \Longrightarrow \delta(x,z) > \delta(x,t) \Longrightarrow \delta(s,z) > \delta(s,t)$，与 $\delta(s,t)$ 为树上任意两节点之间最长的简单路径矛盾。

综上，三种情况下假设均会产生矛盾，故原定理得证。

注意
上述证明过程建立在所有路径均不为负的前提下。如果树上存在负权边，则上述证明不成立。故若存在负权边，则无法使用两次 DFS 的方式求解直径

树形dp

在一个子树中，其直径即为包含子树根的最长链与次长链拼接而成

我们记录当 $1$ 为树的根时，每个节点作为子树的根向下，所能延伸的最长路径长度 $d_1$ 与次长路径（与最长路径无公共边）长度 $d_2$，那么直径就是对于每一个点，该点 $d_1 + d_2$ 能取到的值中的最大值。
$d$数组记子树最长链

实现

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
#include <iostream>
using namespace std;
const int N=1e5+5;
int head[N],nxt[2*N],vl[2*N],to[2*N],num=0;
void add(int x,int y,int z){
    num++;
    to[num]=y;
    vl[num]=z;
    nxt[num]=head[x];
    head[x]=num;
}
int ans=0;
int d[N];
void dfs(int u,int f){
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(v==f) continue;
        dfs(v,u);
        ans=max(ans,d[u]+d[v]+vl[i]);
        d[u]=max(d[u],d[v]+vl[i]);
    }
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        add(x,y,1);
        add(y,x,1);
    }
    dfs(1,0);
    cout<<ans;
    return 0;
}