[模板] 树的重心

定义

找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡。

在接下来介绍的点分治中，从树的重心开始进行分治可以有效的避免出现链的极端情况，使得复杂度变为 $O(n^3)$

实现过程

使用一个 $\mathrm{son}$ 数组，记录以 $v$ 为根节点的子树中节点数目，在 dfs 时依次记录以 $v$ 为根节点下的各个子树的最大节点树（其父亲可以使用 $n-son[v]$ 得到），如果小于当前最大值，更新答案。

不要忘记将初始时 $\mathrm{root}$ (不要赋值为 $-1$，否则会下标越界，建议为 $0$ )对应的 $f$ 设置为无穷大，否则在更新子树时将无法更新！

代码

void getroot(int index,int father){
    son[index] = 1; //计录子树大小
    f[index] = 0; //初始化各子树最大节点数

    for(int i=0;i<map[index].size();i++){
        int v = map[index][i].to;

        if(v!=father && !vis[v]){
            getroot(v,index);
            son[index] += son[v];
            f[index] = max(f[index],son[v]);
        }
    }

    f[index] = max(f[index],size-son[index]);

    if(f[index] < f[root])
        root = index; //更新
}