AcWing 846. 树的重心
原题链接
简单
作者:
Misty.
,
2024-04-11 19:27:18
,
所有人可见
,
阅读 9
// h[N] : 表示 第 i 个节点的 第一条边的 idx
// ne[M] : 表示 与 第 idx 条边 同起点 的 下一条边 的 idx
// e[M] : 表示 第idx 条边的 终点
// N : 节点数量
// M:边的数量
// i : 节点的下标索引
// idx : 边的下标索引
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N =100010,M=2*N;
int n;
int h[N],e[M],ne[M],idx;
bool st[N];
int ans=N;
void add(int x,int y)
{
e[idx]=y,ne[idx]=h[x],h[x]=idx++;
}
int dfs(int u)
{
st[u]=true;
int sum=1,size=0; //sum是包括该节点在内的这颗子树所包含的结点个数,size删掉此结点后的最大连通块结点的数量
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i]; //j为i的联通节点
if(st[j]) continue; //如果当前结点已经被遍历过了 遍历下一个结点
int s=dfs(j); //该节点一个子树的节点数量,要用来更新删掉此结点后的最大连通块结点的数量
size=max(size,s);
sum+=s;
}
size=max(size,n-sum); //比较这颗子树删掉此结点后的最大连通块结点的数量和出了这颗子树以外的点的数量大小
ans=min(size,ans); //更新结果
return sum;
}
int main()
{
memset(h, -1, sizeof h);
cin>>n;
int a,b;
for(int i=0;i<n-1;i++) //n个结点就有n-1条边 //这里不能用while(n--)的形式,因为要用到n作为树的总节点数
{
cin>>a>>b;
add(a,b);
add(b,a);
}
dfs(1);
cout<<ans;
return 0;
}