AcWing 846. 树的重心
原题链接
简单
作者:
qgc123
,
2021-11-29 20:04:10
,
所有人可见
,
阅读 158
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
int ne[N], e[N], st[N], idx, h[N], n, m, ans = 0xffffffff;
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int dfs(int u){
st[u] = true;
int sum = 1, res = 0;
for(int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
if(!st[j]){
int s = dfs(j);
res = max(res, s);
sum += s;
}
}
res = max (res, n - sum);
ans = min (ans, res);
return sum;
}
signed main(){
cin >> n;
memset(h, -1, sizeof h);
for(int i = 0; i < n - 1; i++){
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
dfs(1);
cout << ans << endl;
return 0;
}