点分治模板

//每次到子树中找子树重心(即遍历一遍子树)O(n),而共需找log次,因为每次都把树分成了两段
//=>点分治复杂度O(nlogn)
struct pp
{
    int next,to,w;
}edge[_];
void getroot(rg int i,rg int dad)//找重心
{
    size[i]=1;//该点子树大小
    F[i]=0;//最大儿子子树大小
    for(rg int j=record[i];j;j=edge[j].next)
    {
        rg int to=edge[j].to;
        if(to!=dad&&!passed[to])//passed[]数组只标记找过的重心,因为要把树隔开
        {
            getroot(to,i);
            F[i]=max(F[i],size[to]);
            size[i]+=size[to];
        }
    }
    F[i]=max(F[i],s-size[i]);//别忘了该点父亲也算是其儿子,只不过(to!=dad)阻止了遍历回去,在这里用树的总大小(s)减去该点size->求出其父所在子树大小
    //加不加一没影响,反正能割成两半保证复杂度为log
    root=F[i]<F[root]?i:root;//找到重心,用root这个词是因为不知道重心的英文是什么
}
void dfs(rg int i)
{
    // FFF : 让火焰净化一切!!!
    passed[i]=1;//dfs函数是从重心出发的,为了隔开子树,把其标记为走过
    for(rg int j=record[root];j;j=edge[j].next)
    {
        rg int to=edge[j].to;
        if(!passed[to])
        {
            s=size[to];//初始化!!!
            root=0;//初始化!!!
            getroot(to,root);
            dfs(root);
        }
    }
}