1 条题解
-
2赵青海 (huhe) LV 7 SU @ 2023-7-15 8:59:46
/***************************************** Note: ******************************************/ #include <queue> #include <math.h> #include <stack> #include <stdio.h> #include <iostream> #include <vector> #include <iomanip> #include <string.h> #include <algorithm> using namespace std; #define LL long long const int N = 1e6 + 10; const int INF = 0x3f3f3f3f; int head[N] , to[N] , ne[N] , id; int f[N] , s[N] , maxx; void add(int x, int y) { to[++id] = y , ne[id] = head[x] , head[x] = id; to[++id] = x , ne[id] = head[y] , head[y] = id; } void dfs1(int u , int fa) { f[u] = 1 , s[u] = 0; int ans = 0; for(int i = head[u] ; i ; i = ne[i]) { int v = to[i]; if(v == fa) continue; dfs1(v , u); if(f[v] + 1 > f[u]) { s[u] = f[u]; f[u] = f[v] + 1; } else if(f[v] + 1 > s[u]) s[u] = f[v] + 1 ; } } void dfs2(int u , int fa , int dis) { for(int i = head[u] ; i ;i = ne[i]) { int v = to[i]; if(v == fa) continue; if(f[u] == f[v]+1) dfs2(v,u,max(dis+1,s[u] + 1)); else dfs2(v,u,max(dis+1,f[u] + 1)); } if(dis > f[u]) s[u] = f[u] , f[u] = dis; else if(dis > s[u]) s[u] = dis; maxx = max(f[u] + s[u] , maxx); } int main() { int n; cin >> n; for(int i = 1; i < n ; i++) { int x,y; cin >> x >> y; add(x + 1, y + 1); } dfs1(1,0); dfs2(1,0 ,0); for(int i = 1; i <= n ; i++) { if(f[i] + s[i] == maxx) cout << i - 1<< endl; } return 0; }
- 1
信息
- ID
- 476
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 4
- 标签
- 递交数
- 58
- 已通过
- 28
- 上传者