1 条题解
-
0
C++ :
#include<bits/stdc++.h> using namespace std; int n,a[1010][1010],dep[1010],fa[1010],width[1010]; int maxw,maxd;//最大宽度和深度 int u,v; void dfs(int x,int fath){ fa[x] = fath; dep[x] = dep[fath] + 1; width[dep[x]]++; maxd = max(maxd,dep[x]);//最大宽度 maxw = max(maxw,width[dep[x]]);//最大深度 for(int i = 1;i <= n;i++){ if(a[x][i] && i != fath){ dfs(i,x); } } } int main() { cin>>n; int x,y; for(int i = 1;i <= n - 1;i++){ cin>>x>>y; a[x][y] = 1; a[y][x] = 1; } cin>>u>>v; dfs(1,0); cout<<maxd<<endl<<maxw<<endl; //找到u和v的最近公共祖先 int tu = u,tv = v; while(u != v){ if(dep[u] > dep[v]) u = fa[u]; else v = fa[v]; } cout<<(dep[tu] - dep[u])*1 + dep[tv] - dep[u]; return 0; }
- 1
信息
- ID
- 1091
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者