树的重心也叫树的质心。找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡。换句话说，删除这个点后最大连通块（一定是树）的结点数最小。
#include<stdio.h> #include<stdlib.h> #define FORa(i,s,e) for(int i=s;i<=e;i++) #define FORs(i,s,e) for(int i=s;i>=e;i--) using namespace std; const int N=1000,INF=2147483647; int n,num_edge,ans_pos,ans_cnt=INF,head[N+1]; struct Edge{ int next,to; }edge[2*N]; inline void Add_edge(int from,int to) { edge[++num_edge]=(Edge){head[from],to},head[from]=num_edge; } inline int max(int fa,int fb){return fa>fb?fa:fb;} inline int Dfs(int u,int fa) { int max_tree=0,pre_tree=1,psize; for(int i=head[u];i;i=edge[i].next) if(edge[i].to!=fa) psize=Dfs(edge[i].to,u),pre_tree+=psize,max_tree=max(max_tree,psize); max_tree=max(max_tree,n-pre_tree); if(max_tree<ans_cnt) { ans_cnt=max_tree; ans_pos=u; } return pre_tree; } int main() { int from,to; scanf("%d",&n); FORa(i,2,n) { scanf("%d%d",&from,&to); Add_edge(from,to),Add_edge(to,from); } Dfs(1,0); printf("%d %d",ans_cnt,ans_pos); return 0; } /*6 1 2 1 3 2 5 3 4 5 6*/
原文：https://www.cnblogs.com/SeanOcean/p/11304946.html
