AcWing 846. 树的重心
原题链接
简单
作者:
gkb
,
2024-03-13 21:19:00
,
所有人可见
,
阅读 7
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+10;
//对于树来说,N个顶点,N-1条无向边,N-1条无向边要视为2(N-1)条有向边来存储
int n,head[N],e[2*N],ne[2*N],idx;
int ans=N;//求最小值,ans要初始化无穷大
bool vis[N];//用于表示这个结点是否被访问过
//增加一条a指向b的一条边
void add(int a,int b)
{
e[idx]=b,ne[idx]=head[a],head[a]=idx++;
}
int dfs(int u)
{
vis[u]=true;//标记当前结点被访问
//sum记录以u为根的树的结点数
//size记录u的最大子树的结点数
int sum=1,size=0;
//for循环枚举访问u的各个子树,即出边
for(int i=head[u];i!=-1;i=ne[i])
{
int v=e[i];
if(vis[v]) continue;
int s=dfs(v);//对于子结点返回的s,都是当前结点u的子树,我们需要取最大值
size=max(size,s);
sum+=s;//子结点返回的s都是以u为根的树的一部分,需要求和相加
}
ans=min(ans,max(n-sum,size));
return sum;//子节点的sum就是父结点的size,离开子结点时,将sum带给父结点
}
int main()
{
memset(head,-1,sizeof head);
cin>>n;
//边数,和有向边无向边无关
for(int i=1;i<n;i++)
{
int a,b;
cin>>a>>b;
//一条无向边当做两条有向边
add(a,b),add(b,a);
}
dfs(1);
cout<<ans<<endl;
return 0;
}