题目链接：http://poj.org/problem?id=1655
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 19110 | Accepted: 8083 |
Description
Input
Output
Sample Input
1 7 2 6 1 2 1 4 4 5 3 7 3 1
Sample Output
1 2
Source
树的重心：
找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡。
树的重心的性质：
1.树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么他们的距离和一样。
2.把两个树通过一条边相连得到一个新的树，那么新的树的重心在连接原来两个树的重心的路径上。
3.把一个树添加或删除一个叶子，那么它的重心最多只移动一条边的距离。
题目大意：给定一棵树,求树的重心的编号以及重心删除后得到的最大子树的节点个数size,如果size相同就选取编号最小的.
看代码：
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> using namespace std; const int maxn=2e4+5; const int INF=1e9+7; int head[maxn<<1]; int sonnum[maxn<<1],sonmax[maxn]; int cnt; int N; struct Edge { int next,to;//next表示同起点的下一条边的下标 to表示这条边的终点 }e[maxn<<1]; void add_edge(int u,int v) { e[++cnt].to=v; e[cnt].next=head[u]; head[u]=cnt; } void dfs(int root,int pre) { sonnum[root]=1; for(int i=head[root];i!=-1;i=e[i].next) { int v=e[i].to; if(v==pre) continue; dfs(v,root); sonnum[root]+=sonnum[v];//总个数 sonmax[root]=max(sonmax[root],sonnum[v]);//最大子节点 } } int main() { int T;scanf("%d",&T); while(T--) { cnt=0; memset(head,-1,sizeof(head)); memset(sonmax,0,sizeof(sonmax)); memset(sonnum,0,sizeof(sonnum)); scanf("%d",&N); for(int i=1;i<N;i++) { int u,v;scanf("%d%d",&u,&v); add_edge(u,v); add_edge(v,u); } dfs(1,0); int mi=INF,pos; for(int i=1;i<=N;i++) { int ma=max(sonmax[i],N-sonnum[i]); if(ma<mi) { mi=ma; pos=i; } } printf("%d %d\n",pos,mi); } return 0; }
原文：https://www.cnblogs.com/caijiaming/p/11552771.html