点分治 学习笔记

一种树上的分治,O(nlogn)统计点对之间长度

找重心:

inline void getrt(int u,int fa){
    size[u]=1; int Max=0;
    for(int i=head[u];i;i=nxt[i]){
        int v=go[i];
        if(v==fa)continue;
        size[u]+=size[v];
        Max=max(Max,size[v]);
    }
    Max=max(Max,sum-size[u]);
    if(Max<maxp)rt=u;
}

处理子树内到根的距离:

inline void getdis(int u,int fa){
    rem[++rem[0]]=dis[u];
    for(int i=head[u];i;i=nxt[i]){
        int v=go[i];
        if(v==fa||vis[v])continue;
        dis[v]=dis[u]+w[i];
        getdis(v,u);
    }
}

对树分治:

inline void solve(int u){
    vis[u]=judge[0]=1; calc(u);
    for(int i=head[u];i;i=nxt[i]){
        int v=go[i];
        if(vis[v])continue;
        sum=size[v]; maxp=inf; getrt(v,0); 
        solve(rt);
    }
}

统计答案:

inline void calc(int u){
    for(int i=head[u];i;i=nxt[i]){
        int v=go[i];
        if(vis[v])continue;
        rem[0]=0; dis[v]=w[i];
        getdis(v,u);
                /*
                    这里按照题目来
                    此时已经处理好这个子树到根的距离
                    可以做统计
                */
    }
}

调用：

maxp=sum=n; getrt(1,0); solve(rt);

点分治 学习笔记

原文：https://www.cnblogs.com/naruto-mzx/p/12118982.html