AcWing 846. 树的重心
原题链接
简单
作者:
梦都会空
,
2021-12-06 18:06:38
,
所有人可见
,
阅读 142
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int a[N*2];//储存结点值
int net[N*2];//储存next值
int tou[N];//储存头结点
int id;//指针
bool b[N];//做标记
int ans=N;
void cc(int x,int y)
{
a[id] = y;
net[id] = tou[x];
tou[x] = id++;
}
int bfs(int x)
{
int sum=0;//储存最大子结点数
b[x]=true;
int res=0;//储存结点数
for(int i=tou[x];i!=-1;i=net[i])
{
int y=a[i];
if(b[y]) continue;
int sen=bfs(y);
sum = max(sum,sen);
res+=sen;
}
sum=max(sum,n-res-1);
ans=min(sum,ans);
return res+1;
}
int main()
{
scanf("%d",&n);
memset(tou, -1, sizeof tou);
for(int i=0;i<n-1;i++)
{
int x,y;
scanf("%d%d",&x,&y);
cc(x,y);
cc(y,x);
}
bfs(1);
printf("%d",ans);
return 0;
}