重心的定义: 一颗无根树，选择某一个结点，该结点相对于其它未被选择的结点来说，拥有的最大子树的节点数是最少的。
性质: 1.以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。 2.树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。 3.把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。 4.在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。
在这里插入代码片 #include <bits/stdc++.h> #define ll long long using namespace std; //存储图 链式前向星法 int head[10000]; int to[10000]; int next[10000]; int cnt=0; int siz[10000];//子节点个数 (儿子个数) // 2(1) // | // 5(2) // / \ // 6(3) 7(4) // siz[2]=2 int vis[10000]; int n; int ans=10000; //以重心为根节点的最大子树的子节点个数 int temp;//重心点 void add(int u,int v) { next[++cnt]=head[u]; //记录前一条边 head[u]=cnt; //记录当前第几条边 to[cnt]=v; } void dfs(int x) { vis[x]=1; siz[x]=1;//本身自己一个结点 for (int i=head[x];~i;i=next[i]) { int v=to[i]; if(!vis[v]) { dfs(v); siz[x]+=siz[v]; //加上每一个孩子的子节点数 ret=max(ret,siz[v]); //找出最大的子节点个数 } } ret=max(ret,n-siz[x]); //总共n个结点-以x为根的下方的结点数得到上方的结点总数 //ret最终为以x为根节点的最大子树的子节点个数 if(ret<ans||(ret<=ans&&x<temp)) { ans=ret; temp=x; } } int main() { int t; cin>>t; while(t--) { memset(vis,0,sizeof(Vis)); memset(siz,0,sizeof(siz)); cin>>n; for (int i=0;i<n-1;i++) { int a,b; cin>>a>>b; add(a,b); } dfs(1); cout<<"重心为: "<<temp<<" shu以重心为根节点的最大子树的子节点个数: "<<ans<<endl; } }