1498. 最深的根
作者:
logos--
,
2023-03-03 15:00:53
,
所有人可见
,
阅读 210
#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N = 1e4 + 7;
constexpr int inf = 1E18, mod = 1e9 + 7;
int n, p[N];
vector<int> G[N];
inline int find(int x) {
return x == p[x] ? x : p[x] = find(p[x]);
}
inline int dfs(int u, int fa) {
int de = 0;
for (auto v : G[u]) {
if(v == fa) continue;
de = max(de, dfs(v, u) + 1);
}
return de;
}
inline void Solve() {
cin >> n;
for (int i = 1; i <= n; i ++) {
p[i] = i;
}
int cnt = n;
for (int i = 0; i < n - 1; i ++) {
int a, b; cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
if(find(a) != find(b)) {
p[find(a)] = find(b);
-- cnt;
}
}
if(cnt > 1) cout << "Error: " << cnt << " components" << '\n';
else {
vector<int> res(n + 1);
int mx = 0;
for (int i = 1; i <= n; i ++) {
int d = dfs(i, 0);
res[i] = d;
mx = max(mx, d);
}
for (int i = 1; i <= n; i ++) {
if(mx == res[i]) {
cout << i << '\n';
}
}
}
}
signed main() {
cin.tie(nullptr) -> sync_with_stdio(false);
int T = 1;
for (; T; T --) Solve();
return 0;
}