AcWing 846. 树的重心
原题链接
简单
作者:
sy123
,
2021-01-07 18:30:59
,
所有人可见
,
阅读 334
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
vector<vector<int> >g(N);
int n;
int ans=N;//记录答案
bool st[N];
//dfs(u)返回的是以u为根的子树节点个数
//dfs(u)这个函数的功能是求出删除u这个节点,
//剩下的连通块中节点个数最多连通块的节点数量
int dfs(int u){
st[u]=true;//被访问过
int sum=1;//根本身是一个节点;
int res=0;//记录删除这个点最大的连通块数量
for(int i=0;i<g[u].size();i++){
int e=g[u][i];
if(!st[e]){
int s=dfs(e); //递归求出以e为根节点的子树节点个数
res=max(res,s);
sum+=s;
}
}
res=max(res,n-sum);
ans=min(res,ans);
return sum;
}
int main(){
cin>>n;
for(int i=0;i<n-1;i++){
int a,b;
scanf("%d%d",&a,&b);
g[a].push_back(b); //无向图
g[b].push_back(a);
}
dfs(1);
cout<<ans<<endl;
return 0;
}