【题解】直径

题意概述

给你一棵树,求出树的直径长度并找到树上所有直径都经过的边有多少条。

解题思路

本题求树的直径就只需要用DP或DFS都可以(注意DP可以求出负权边而若DFS求则很困难)。这里没有负权所以用DFS可以简化过程。

首先我们先求一遍树的直径,设这条直径的两端是a和b。

然后以a为根DFS找到离a最远的点的个数,并且让b在a的树上向父节点跳,一直跳到b子树下最远点的个数等于a子树下最远点的个数。

最后以b为根DFS做同样操作即可。

Q:b在往父节点跳的时候会不会最远点的个数等于离a最远点的个数却不是最远点?
A: 不会,因为b即a的最远点,所以b的最远点一定也是a的最远点

Q: 如何往父节点跳?
A: 当每次DFS时就把每个节点的父亲节点记录下来即可。

代码

#include<bits/stdc++.h>
using namespace std;
int head[200005];
int n;
struct e{
    int nxt,to,sum;
}edge[400005];
int tot;
void add_edge(int u,int v,int w){
    tot++;
    edge[tot].nxt=head[u];
    edge[tot].to=v;
    edge[tot].sum=w;
    head[u]=tot;
}
int S,T;
long long d[200005];
// long long sum[200005];
int cnt[200005];
long long maxn,maxpos;
void DFS(int now,int father,long long depth){//普通DFS
    if(maxn<depth)maxn=depth,maxpos=now;
    for(int i=head[now];i;i=edge[i].nxt){
        if(edge[i].to==father)continue;
        DFS(edge[i].to,now,depth+edge[i].sum);
    }
}
int fa[200005];
void dfs(int now,int father,long long depth){//用于缩小范围DFS
    if(maxn<depth)maxn=depth,maxpos=now;
    cnt[now]=1,d[now]=0,fa[now]=father;
    for(int i=head[now];i;i=edge[i].nxt){
        if(father==edge[i].to)continue;
        dfs(edge[i].to,now,depth+edge[i].sum);
        if(d[now]<d[edge[i].to]+edge[i].sum)d[now]=d[edge[i].to]+edge[i].sum,cnt[now]=cnt[edge[i].to];
        else if(d[now]==d[edge[i].to]+edge[i].sum)cnt[now]+=cnt[edge[i].to];
    }
}
int main(){
    scanf("%d",&n);
    int a,b,c;
    for(int i=1;i<=n-1;i++){
        scanf("%d%d%d",&a,&b,&c);
        add_edge(a,b,c);
        add_edge(b,a,c);
    }
    DFS(1,0,0);
    maxn=0;
    a=maxpos;
    long long ans=0;
    dfs(maxpos,0,0);//两次DFS合并在了一起,因为反正搜索的是用一件东西。
    ans=maxn;
    b=maxpos;
    while(cnt[b]!=cnt[a])b=fa[b];
    maxn=0;
    dfs(b,0,0);
    while(cnt[a]!=cnt[b])a=fa[a];
    int anss=0;
    while(a!=b)a=fa[a],anss++;
    printf("%lld\n%d\n",ans,anss);
    return 0;
}

本文链接:http://kaispace.com.cn/index.php/archives/662/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者