1 条题解
-
0Guest LV 0 MOD
-
0
#include<bits/stdc++.h> const int maxn=200001; inline const void read(int &a) { a=0; char c=getchar(); while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9') { a=(a<<1)+(a<<3)+c-'0'; c=getchar(); } } inline const void write(int a) { if(a>=10)write(a/10); putchar(a%10+'0'); } inline const int max(int a,int b) { if(a>b)return a; return b; } inline const int min(int a,int b) { if(a<b)return a; return b; } int point[maxn],n,d=0,ans=0,to[maxn],next[maxn],start,end,dis[maxn]; bool been[maxn],on_chain[maxn]; void dfs1(int p,int tt) { if(tt==1&&dis[p]>dis[start])start=p; if(tt==2&&dis[p]>dis[end])end=p; been[p]=true; int side=point[p]; while(side) { if(!been[to[side]]) { dis[to[side]]=dis[p]+1; dfs1(to[side],tt); } side=next[side]; } } bool dfs2(int p) { if(p==end){on_chain[p]=true;return true;} been[p]=true; int side=point[p]; while(side) { if(!been[to[side]])if(dfs2(to[side]))on_chain[p]=true; side=next[side]; } if(on_chain[p])return true; else return false; } void dfs3(int p) { if(on_chain[p])dis[p]=0; if(dis[p]>dis[ans])ans=p; been[p]=true; int side=point[p]; while(side) { if(!been[to[side]]) { dis[to[side]]=dis[p]+1; dfs3(to[side]); } side=next[side]; } } inline const void add(int a,int b) { next[++d]=point[a]; point[a]=d; to[d]=b; } inline const void init() { memset(dis,0,sizeof(dis)); memset(been,false,sizeof(been)); } int main() { //freopen("测试数据.txt","r",stdin); memset(on_chain,false,sizeof(on_chain)); memset(point,0,sizeof(point)); read(n); for(int i=1;i<=n-1;i++) { int a,b; read(a);read(b); add(a,b);add(b,a); } init(); dfs1(1,1); init(); dfs1(start,2); init(); dfs2(start); init(); dfs3(start); write(dis[ans]); return 0; }
- 1
信息
- 难度
- 9
- 分类
- (无)
- 标签
- (无)
- 递交数
- 9
- 已通过
- 1
- 通过率
- 11%
- 上传者