AcWing 846. 树的重心
原题链接
简单
作者:
尼古拉斯小布丁
,
2021-08-27 16:46:15
,
所有人可见
,
阅读 235
题目描述
/*
1. 这个题的做法就是 求出每个点在删除某个点之后, 其余所有连通块的最大值
只要求出每个点这样的最大值,最后在所有点里找个最小的
2. 这里使用dfs, dfs可以算出每一个子树的大小
3. 树和图的遍历, 时间复杂度都是O(n+m)
*/
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 100010;
int h[N], e[2*N], ne[2*N], idx;
int n;
bool st[N]; //用于标记下标对应的点是否被遍历过, bfs和dfs对每个点都只遍历一次
int ans = N; //用于存储删除点之后最小的最大连通块大小
void add(int a, int b){
e[idx] = b, ne[idx]=h[a], h[a]=idx++;
}
int dfs(int u){
int res = 0; //删去根节点u之后, 最大的连通块大小
st[u] = true; //标记该点被遍历过
int sum = 1;
// cout<<u<<endl;
for(int i = h[u];i!=-1;i=ne[i]){
int j = e[i];
if(!st[j]){
int s =dfs(j);
// cout<<s<<endl;
res = max(res, s);
// cout<<res<<endl<<endl;
sum+=s;
}
}
res = max(res, n-sum);
// cout<<res<<endl<<endl;
ans= min(res, ans);
return sum;
}
int main(){
memset(h, -1, sizeof h);
cin>>n;
int a,b;
for(int i=0;i<n-1;i++){
cin>>a>>b;
add(a, b);
add(b, a);
}
dfs(1);
// cout<<endl;
cout<<ans<<endl;
return 0;
}