树的直径模板

Posted on | In ,

树的直径即树上最长的一段路径，寻找它可以在O（n）内完成。

首先以任意一点为根做bfs，找到离根最远的点，它一定是直径的两点之一，再以它为根找最远的点，即直径的另一点。证明过程反证法即可。

https://ac.nowcoder.com/acm/contest/884/A

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
#include<bits/stdc++.h>
using namespace std;

//树直径模板
const int maxn=1e5+2;
struct edge{
    int to,next;
}es[maxn<<1];
int cnt,head[maxn];
inline void add(int x,int y){
    es[++cnt]=(edge){y,head[x]};
    head[x]=cnt;
}

int s[maxn];
int n,k;
int main(){
    cin>>n>>k;
    for(int i=1,x,y;i<=n-1;i++){
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=k;i++)
        cin>>s[i];
    int dis[maxn];
    memset(dis,0,sizeof(dis));
    queue<int> q;
    q.push(1);
    dis[1]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=es[i].next){
            int v=es[i].to;
            if(dis[v])
                continue;
            dis[v]=dis[u]+1;
            q.push(v);
        }
    }
    int a=1;
    for(int i=2;i<=k;i++){
        if(dis[s[i]]>dis[s[a]]){
            a=i;
        }
    }
    memset(dis,0,sizeof(dis));
    q.push(s[a]);
    dis[s[a]]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=es[i].next){
            int v=es[i].to;
            if(dis[v])
                continue;
            dis[v]=dis[u]+1;
            q.push(v);
        }
    }
    int b=1;
    for(int i=2;i<=k;i++){
        if(dis[s[i]]>dis[s[b]])
            b=i;
    }
    int ans=dis[s[b]]/2;
    cout<<ans<<endl;
}