NOIP 冲刺 模板:树的直径

题目描述
树的直径:树上两点之间的最大距离。

给出一个树,让你求树的直径。

输入

一个数n表示节点数,以下(n-1)行每行两个数x,y表示x与y间有边。

输出
一个整数,树的直径。

样例输入
10
2 8
7 2
2 1
1 10
2 3
3 4
4 9
3 5
3 6

样例输出
5

提示

40% n<=2000

100% n<=200000

#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
#define N 200005
using namespace std;
int n,tot;
int nex[N*2];
int to[N*2];
int head[N*2];
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
  if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
bool vis[N*2];
int dis[N*2];
inline void add(int x,int y){
    ++tot;
    nex[tot]=head[x];
    head[x]=tot;
    to[tot]=y;
}
inline int spfa(int u){
    queue<int> q;
    memset(dis,0x7f7f7f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    q.push(u);
    dis[u]=0;
    vis[u]=1;
    while(!q.empty()){
        int dmf=q.front();
        q.pop();
        for(int i=head[dmf];i;i=nex[i]){
            if(dis[to[i]]>dis[dmf]+1){
                dis[to[i]]=dis[dmf]+1;
                if(!vis[to[i]]){
                    vis[to[i]]=1;
                    q.push(to[i]);
                }
            }
        }
        vis[dmf]=0;
    }
    int maxn=0;
    int id;
    for(int i=1;i<=n;i++){
        if(i!=u){
            if(dis[i]>maxn){
                id=i;
                maxn=dis[i];
            }
        }
    }
    return id;
}
int main(){
    n=read();
    for(int i=1;i<n;i++){
        int x,y;
        x=read();
        y=read();
        add(x,y);
        add(y,x);
    }
    int ans=0;
    int id=spfa(1);
    ans+=dis[id];
    int ans1=ans;
    int id2=spfa(id);
    if(id==1) ans=max(ans,dis[id2]);
    else ans+=dis[id2];
    printf("%d",ans-ans1);
    return 0;
}

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
2022-12-23 19:49
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
01-07 18:24
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-29 23:08
浙江大学_2021
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议