问题描述:
城里有一个黑手党组织。把黑手党的人员关系用一棵树来描述，教父是树的根，每个节点是一个组织成员。为了保密，每人只和他的父节点和他的子节点联系，警察知道哪些人互相来往，但是不知他们的关系。警察想找出谁是教父。
警察假设教父是一个聪明人：教父懂得制衡手下的权力，所以他直属的几个小头目每个人的属下的人数差不多。也就是说，删除根之后，剩下几棵互不连通的子树（连通块），其中最大的连通块应该尽可能小。请帮助警察找到哪些人可能是教父。
| 输入：第1行输入n，表示组织人数，2 ≤ n ≤ 50000。组织成员的编号为 1~ n。下面n ~ 1行中，每行输入两个整数，即有联系的两个人的编号 |
| 输出：输出疑似教父的节点编号，从小到大输出 |
| 输入样例 | 输出样例 |
| 6 1 2 2 3 2 5 3 4 3 6 | 2 3 |
树的重心
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 50005; //最大结点数
struct Edge{ int to, next;} edge[N<<1]; //两倍：u-v, v-u
int head[N], cnt = 0;
void init(){ //链式前向星：初始化
for(int i=0; i<N; ++i){
edge[i].next = -1;
head[i] = -1;
}
cnt = 0; //序号从0开始
}
void addedge(int u,int v){ //链式前向星：加边u-v
edge[cnt].to = v; //父节点或子节点
edge[cnt].next = head[u]; //指向上一个相同的节点记录
head[u] = cnt++; //更新节点记录
}
int n;
int d[N], ans[N], num=0, maxnum=1e9; //d[u]: 以u为根的子树的结点数量
void dfs(int u,int fa){
d[u] = 1; //递归到最底层时，结点数加1
int tmp = 0;
for(int i=head[u]; ~i; i=edge[i].next){ //遍历u的子结点。~i也可以写成i!=-1
int v = edge[i].to; //v是一个子结点
if(v == fa) continue; //不递归父亲
dfs(v,u); //递归子结点，计算v这个子树的结点数量
d[u] += d[v]; //计算以u为根的结点数量
tmp = max(tmp,d[v]); //记录u的最大子树的结点数量
}
tmp = max(tmp, n-d[u]); //tmp = u的最大连通块的结点数
//以上计算出了u的最大连通块
//下面统计疑似教父。如果一个结点的最大连通块比其他结点的都小，它是疑似教父
if(tmp < maxnum){ //一个疑似教父
maxnum = tmp; //更新“最小的”最大连通块
num = 0;
ans[++num] = u; //把教父记录在第1个位置
}
else if(tmp == maxnum) ans[++num] = u; //疑似教父有多个，记录在后面
}
int main(){
scanf("%d",&n);
init();
for(int i=1; i<n; i++){
int u, v; scanf("%d %d", &u, &v);
addedge(u,v); addedge(v,u);
}
dfs(1,0);
sort(ans+1, ans+1+num);
for(int i=1;i<=num;i++) printf("%d ",ans[i]);
}
笔记：树的重心是书的某一个节点，在删掉一个节点后，如果在各个连通分量里是最小的最大联通分量，此节点就是树的重心。重心可以存在多个，但是一定是相邻的。题意要求的教父就是剩余的最大连接组件的大小尽可能小，树的重心节点就是疑似教父