AcWing 846. 树的重心
原题链接
简单
作者:
HUE菜鸡联盟
,
2021-12-05 21:29:08
,
所有人可见
,
阅读 153
#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<string.h>
#define for0(x,n) for(int x=0;x<n;x++)
#define for1(x,n) for(int x=1;x<=n;x++)
const int tt=1e5+10,mod=1e6+7,INF=0x7f7f7f7f7f7f7f7f;
int n,m,t;
using namespace std;
typedef pair<int,int> PII;
vector<int>G[tt];
int ans=INF;
int vis[tt];
int dfs(int x)
{
int res=0;
vis[x]=1;
int sum=1;
for0(i,G[x].size())
{
int to=G[x][i];
if(vis[to]==0)
{
int s=dfs(to);
res=max(res,s);
sum+=s;
}
}
res=max(res,n-sum);
ans=min(ans,res);
return sum;
}
int main()
{
cin>>n;
for0(i,n)
{
int x,y;
cin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1);
cout<<ans<<endl;
return 0;
}