树的直径
|
阅读次
|
564 字
|
2 分钟

树的直径

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

两次dfs

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

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

证明

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

  • 若 在 上：

y 在 st 上

有 ，与 为树上任意两节点之间最长的简单路径矛盾。

  • 若 不在 上，且 与 存在重合路径：

有重合路径

有 ，与 为树上任意两节点之间最长的简单路径矛盾。

  • 若 不在 上，且 与 不存在重合路径：

y 不在 st 上

有 ，与 为树上任意两节点之间最长的简单路径矛盾。

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

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

树形dp

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

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

实现

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;
}
下一篇