题目描述
树的直径:树上两点之间的最大距离。
给出一个树,让你求树的直径。
输入
一个数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;
}