题目描述
重心定义:重心是指树中的一个结点,如果将这个点删除后,剩余各个连通块中点数的最大值最小,那么这个节点被称为树的重心。
视频题解:
样例
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
4
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
const int N= 100010,M = N*2;
int h[N],e[M],ne[M],idx;
int n;
int ans = N;
bool st[N];
void add(int a,int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
int dfs(int u){
st[u] = true;
int size = 0,sum = 0;// sum储存他儿子一共有多少节点
for(int i = h[u];i != -1;i = ne[i]){
int j = e[i];
if(st[j]) continue;
int s = dfs(j); // s储存的是当前节点的儿子反回的子孙节点的数量
size = max(size,s);//当删除当前节点后,他的所有(左右)儿子节点相互对比,更新最大连通点的值
sum += s; // 统计他的子孙的数量
}
// 这一步每个点只会执行一次
size = max(size,n-sum-1);//当删除当前节点后,他儿子中的最大连通点 和 他的上右面连通节点比大小,保存最大连通点的值
ans = min(ans,size); // 更新答案
return sum + 1; // 返回给他父亲,他有多少子孙
/*
两个size的比较是核心点
*/
}
int main(){
cin>>n;
memset(h,-1,sizeof h);
for(int i = 0;i<n;i++){
int a,b;
cin>>a>>b;
add(a,b);
add(b,a);
}
dfs(1);
cout<<ans<<endl;
return 0;
}