1.定义
对于无根树上的每一个点，计算其所有子树中最大的子树节点数，这个值最小的点就是这棵树的重心。
具体解释一下，如图给出的一棵树中
若以1为根节点，则它的子树为{2,4,5}和{3,6,7}，最大子树的节点数为3；
若以2为根节点，则它的子树为{4}，{5}和{1,3,6,7}，最大子树的节点数为4；
若以3为根节点，则它的子树为{6}，{7}和{1,2,4,5}，最大子树的节点数为4；
若以4为根节点，则它的子树为{1,2,3,5,6,7}，最大子树的节点数为5；
若以5为根节点，则它的子树为{1,2,3,4,6,7}，最大子树的节点数为5；
若以6为根节点，则它的子树为{1,2,3,4,5,7}，最大子树的节点数为5；
若以7为根节点，则它的子树为{1,2,3,4,5,6}，最大子树的节点数为5；
综上所述， 每个节点最大子树节点数的最小值为3
所以树的重心为3
2.做法
（1）
首先讲暴力做法，就是根据定义的方法，在每个节点暴力搜索它的所有子树，一一比较得到结果
（2）
接下来是智力的做法，还是看定义里的树
假设这事一棵以1为根节点的有根数
我们可以dfs求出以每个节点为根的树的节点个数
如图
记总结点数为n，第i个节点为根的树的节点个数位a[i]
如图n=7,a[1]=7,a[2]=a[3]=3,a[4]=a[5]=a[6]=a[7]=1
然后每个节点的最大子树就可以算出来了
比如，2号节点的最大子树位max(a[4],a[5],n-a[2])=4
一般地，i号节点的最大子树为max(a[j],n-a[i]) (j节点为任意i节点的子节点)
这样的话，该算法的时间复杂度即为一次dfs的复杂度
3.代码
（极其丑陋，初学时写的）
1 #include <bits/stdc++.h> 2 using namespace std; 3 int n; 4 vector <int> v[50005]; 5 bool vis[50005],vis2[50005]; 6 int a[50005],ans=INT_MAX,fa[50005],s[50005]; 7 int dfs(int x) 8 { 9 int ss=0; 10 if(vis[x]) 11 return 0; 12 if(v[x].size()==1 && x!=1) 13 { 14 a[x]=1; 15 return 1; 16 } 17 vis[x]=1; 18 for(int i=0;i<v[x].size();i++) 19 a[x]+=dfs(v[x][i]); 20 vis[x]=0; 21 a[x]++; 22 return a[x]; 23 24 } 25 void sbdfs(int x,int la) 26 { 27 if(vis2[x]) 28 return; 29 vis2[x]=1; 30 fa[x]=la; 31 for(int i=0;i<v[x].size();i++) 32 sbdfs(v[x][i],x); 33 } 34 int main() 35 { 36 cin>>n; 37 for(int i=1;i<n;i++) 38 { 39 int x,y; 40 cin>>x>>y; 41 v[x].push_back(y); 42 v[y].push_back(x); 43 } 44 sbdfs(1,1); 45 a[1]=dfs(1); 46 for(int i=1;i<=n;i++) 47 { 48 s[i]=n-a[i]; 49 for(int j=0;j<v[i].size();j++) 50 if(v[i][j]!=fa[i]) 51 s[i]=max(s[i],a[v[i][j]]); 52 ans=min(ans,s[i]); 53 } 54 for(int i=1;i<=n;i++) 55 if(s[i]==ans) 56 cout<<i<<' '; 57 return 0; 68 }