树的直径

发表于2021-10-04更新于2021-10-08阅读次数

两次dfs/bfs 树形dp

树的直径

Roads in the North
模板

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
/*
* @Author: Marhoosh
* @Date:   2021-10-08 11:23:22
* @Last Modified by:   Marhoosh
* @Last Modified time: 2021-10-08 12:29:44
*/
#include<iostream>
#include<cstring>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
const ll maxn=2e5+11;
struct Edge{
    ll to,w,next;
}edge[maxn];
ll head[maxn],d[maxn],tmp=1,num,zj;
void add(ll u,ll v,ll w){
    edge[tmp]={v,w};edge[tmp].next=head[u];
    head[u]=tmp++;
}
void dfsf(ll x,ll fa){
    if(d[x]>zj){
        zj=d[x];
        num=x;
    }
    for(ll i=head[x];i;i=edge[i].next){
        ll y=edge[i].to;
        if(y==fa)continue;
        d[y]=d[x]+edge[i].w;
        dfsf(y,x);
    }
}
void dfss(ll x,ll fa){
    if(d[x]>zj){
        zj=d[x];
        num=x;
    }
    for(ll i=head[x];i;i=edge[i].next){
        ll y=edge[i].to;
        if(y==fa)continue;
        d[y]=d[x]+edge[i].w;
        dfss(y,x);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll u,v,w;
    while(cin>>u>>v>>w){
        add(u,v,w);add(v,u,w);
    }
    zj=0;
    dfsf(1,0);
    memset(d,0,sizeof(d));
    dfss(num,0);
    cout<<zj<<endl;
    return 0;
}

灵活运用+思维

P5536 【XR-3】核心城市

题解

  • 常规思路-树的直径

    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
    76
    77
    78
    79
    80
    81
    #include<iostream>
    #include<cstring>
    #include<cmath>
    #include<cstdio>
    #include<algorithm>
    #include<vector>
    using namespace std;
    #define N 100010
    int n,k,zj,num,ans_k;
    int cut,head[N],ver[2*N],next[2*N];
    int deep[N],f[N],maxdeep[N],ans[N];
    bool cmp(int a,int b){
        return a>b;
    }
    void add(int x,int y){
        ver[++cut]=y;next[cut]=head[x];head[x]=cut;
    }
    //求直径
    void dfs1(int x,int fa){
        if(deep[x]>zj){
            zj=deep[x];
            num=x;
        }
        for(int i=head[x];i;i=next[i]){
            int y=ver[i];
            if(y==fa)continue;
            deep[y]=deep[x]+1;
            dfs1(y,x);
        }
    }
    void dfs2(int x,int fa){
        if(deep[x]>zj){
            zj=deep[x];
            num=x;
        }
        for(int i=head[x];i;i=next[i]){
            int y=ver[i];
            if(y==fa)continue;
            deep[y]=deep[x]+1;
            f[y]=x;
            dfs2(y,x);
        }
    }
    //
    void dfs_k(int x,int fa){
        maxdeep[x]=deep[x];
        for(int i=head[x];i;i=next[i]){
            int y=ver[i];
            if(y==fa)continue;
            deep[y]=deep[x]+1;
            dfs_k(y,x);
            maxdeep[x]=max(maxdeep[x],maxdeep[y]);
        }
    }
    int main(){
        scanf("%d%d",&n,&k);
        for(int i=1;i<n;++i){
            int x,y;
            scanf("%d%d",&x,&y);
            add(x,y);
            add(y,x);
        }
        //直径
        dfs1(1,0);
        memset(deep,0,sizeof(deep));
        zj=0;
        dfs2(num,0);
        //
        int kkk=num;
        //找直径的中点
        for(int i=1;i<=(deep[num]+1)/2;++i)kkk=f[kkk];
        memset(deep,0,sizeof(deep));
        //再搜一次
        dfs_k(kkk,0);
        for(int i=1;i<=n;++i)ans[i]=maxdeep[i]-deep[i];
        sort(ans+1,ans+n+1,cmp);
        //QwQ结合图片不难想
        for(int i=k+1;i<=n;++i)ans_k=max(ans_k,ans[i]+1);
        printf("%d\n",ans_k);
        return 0;
    }

  • 逆向思维
    转载
    我们可以考虑放n-k个节点然后使深度最大的最小

一开始的时候可以反过来想：树里面长度最大的路径就是树的直径，它的两个端点的度都是1（也就是叶子节点）

我们可以从每个叶子结点开始，向中心包围。可以用队列的方式实现。

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
/*
* @Author: Marhoosh
* @Date:   2021-09-04 21:45:32
* @Last Modified by:   Marhoosh
* @Last Modified time: 2021-10-04 17:51:27
*/
#include<bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
const ll maxn=2e5+11;
struct Edge{
    ll to,next;
}edge[maxn];
ll head[maxn],c[maxn],d[maxn],n,k,tmp=1;
queue<ll> q;
void add(ll u,ll v){
    edge[tmp].to=v;edge[tmp].next=head[u];
    head[u]=tmp++;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(ll i=1,u,v;i<=n-1;i++){
        cin>>u>>v;
        add(u,v);add(v,u);c[u]++;c[v]++;
    }
    for(ll i=1;i<=n;i++)  if(c[i]==1)  {
        q.push(i);d[i]=1;
    }
    ll cnt=n-k;
    while(1){
        ll x=q.front();q.pop();
        if(--cnt==0){
            cout<<d[x]<<endl;
            return 0;
        }
        for(ll i=head[x];i;i=edge[i].next){
            ll v=edge[i].to;c[v]--;
            if(c[v]==1){
                q.push(v);d[v]=d[x]+1;
            }
        }
    }
    return 0;
}