1 条题解
-
0
C++ :
#include <bits/stdc++.h> using namespace std; const int N = 100010; /* fa:每个元素的父元素 dep:每个元素的深度 pre:每个点的最后一条边 k:边的数量 */ int fa[N],dep[N],pre[N],k; struct node { int from,to,next; } a[N*2]; int x,y,t1,t2,n; //加边 void add(int u,int v) { k++; a[k].from = u; a[k].to = v; a[k].next = pre[u]; pre[u] = k; } //深搜求元素的父和深度 void dfs(int x,int fath) { fa[x] = fath; dep[x] = dep[fath] + 1; for(int i = pre[x]; i != 0; i = a[i].next) { if(a[i].to != fath) { dfs(a[i].to,x); } } } int main() { cin>>n; //读入关系 for(int i = 1; i <= n - 1; i++) { cin>>x>>y; add(x,y); add(y,x); } dfs(1,0);//求每个点的父及深度 x = 1; for(int i = 2; i <= n; i++) { if(dep[i] > dep[x]) x = i; } dfs(x,0); y = 1; int ans = 0;//直径 for(int i = 2; i <= n; i++) { if(dep[i] > dep[y]) y = i; } // cout<<x<<" "<<y<<endl<<dep[y] - 1<<endl; //从y开始向上爬到一半的深度,就是直径 //中点只有1个,爬一半的距离就是中点 int d = dep[y]; if(d%2 != 0) { for(int i = 1; i <= d / 2; i++) { y = fa[y]; } cout<<y; } else { //中点有2个,爬一半的距离,以及一半距离+1 for(int i = 1; i <= d / 2 - 1; i++) y = fa[y]; if(y < fa[y]) cout<<y<<" "<<fa[y]; else cout<<fa[y]<<" "<<y; } return 0; }
- 1
信息
- ID
- 1092
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者