AcWing 846. 树的重心
原题链接
简单
作者:
陌白KING
,
2023-11-16 18:41:51
,
所有人可见
,
阅读 44
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
int n;
const int N = 100010, M = 2 * N;
int e[M], h[M],ne[M],idx = 0;
int ans = N;
bool st[N];
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);
sum += s;
res = max(s,res);
}
}
res = max(res,n - sum);
ans = min(res,ans);
return sum;
}
int 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;
}