定义
对于树上的每一个点，计算其所有子树中最大的子树节点数，这个值最小的点就是这棵树的重心。
性质
-
以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。
-
树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。
-
把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。
-
在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。
（上述内容均来自oiwiki）
- 当节点数为偶数时，总是有且仅有两个重心；当节点数为奇数时，总是有且仅有一个重心。
求法
通过性质1可以发现“某节点的最大子树大小不超过整棵树大小的一半”和“该节点是树的重心”互为充要条件，因此我们可以以任意一点为根进行 DFS 记录每个子树的大小和其父亲的最大子树，再与 \(\left\lfloor\dfrac{n}{2}\right\rfloor\) 比较大小即可。
void Getcentroid(int u,int fa){
for(int i=head[u];i;i=e[i].Next){
int v=e[i].to;
if(v==fa)continue;
Getcentroid(u,v);
siz[u]+=siz[v];
wei[u]=max(wei[u],siz[v]);
}
wei[u]=max(wei[u],n-siz[u]);
if(wei[u]>=n/2)
cen[cen[0]!=0]=y;
}