水了好几道直径的蓝题然后发现板子题过来提交居然挂了
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int maxn = 10100;
int n, siz[maxn], f[maxn];
vector<int> G[maxn];
// 求以 u 为根结点的子树大小
// 以及 u 的最大子树的结点数量
// f[u] = max{siz[v], n-siz[u]}
int dfs(int u, int fa) {
siz[u] = 1;
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (v != fa) {
siz[u] += dfs(v, u);
// 更新 f[u] = max{siz[v]}
f[u] = max(f[u], siz[v]);
}
}
// 更新 f[u] = max{f[u], n-siz[u]}
f[u] = max(f[u], n - siz[u]);
return siz[u];
}
int main() {
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1, 1);
int center = 1;
for (int i = 1; i <= n; i++) {
// 找到 f[i] 最小的结点 center
if (f[i] < f[center]) {
center = i;
}
}
cout << center << endl;
return 0;
}