点分治-luogu2634

题目链接

luogu2634

思路

经典的点分治算法，点分治是logn层，考虑O(n)处理路径问题，
核心代码是下面这部分

int calc(int u,int v){
    dis[u]=v%3;
    tmp[0]=tmp[1]=tmp[2]=0;
    getdis(u,0);
    return tmp[1]*tmp[2]*2+tmp[0]*tmp[0];
}
void divide(int u){
    //先统计所有答案
    ans+=calc(u,0);
    vis[u]=1;
    for(int i=head[u];~i;i=edges[i].nex){
        //对每个子树删除多于的答案
        // 实际删除那些不经过根节点的路径的边
        int v = edges[i].v;
        if(vis[v])continue;
        ans-=calc(v,edges[i].w);
        maxp[rt=0]=sum=siz[v];
        getrt(v,0);
        getrt(rt,0);
        divide(rt);
    }
}

首先计算经过当前节点的路径，然后再减去子树产生的贡献。注意的是，点分治的核心就是每次找的答案是仅仅处理完毕当前根节点以及它的儿子的答案，它的孙子(类比)的答案不着急统计。

完整代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e4+10;
struct edge{
    int v,w,nex;
    edge(){}
    edge(int v,int w,int nex):v(v),w(w),nex(nex){}
}edges[N<<1];
int siz[N],maxp[N];
int head[N],tot,vis[N],sum,rt,dis[N],tmp[4],cnt,ans;
int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}
void add(int u,int v,int w){
    edges[tot]=edge(v,w,head[u]);
    head[u]=tot++;
}
void getrt(int u,int fa){
    siz[u]=1,maxp[u]=0;
    for(int i=head[u];~i;i=edges[i].nex){
        int v = edges[i].v;
        if(vis[v]||v==fa)continue;
        getrt(v,u);
        siz[u]+=siz[v];
        if(maxp[u]<siz[v])maxp[u]=siz[v];
    }
    maxp[u]=max(maxp[u],sum-siz[u]);
    if(maxp[u]<maxp[rt])rt=u;
}
void getdis(int u,int fa){
    tmp[dis[u]]++;
    for(int i=head[u];~i;i=edges[i].nex){
        int v = edges[i].v;
        if(vis[v]||v==fa)continue;
        dis[v]=(dis[u]+edges[i].w)%3;
        getdis(v,u);
    }
}
int calc(int u,int v){
    dis[u]=v%3;
    tmp[0]=tmp[1]=tmp[2]=0;
    getdis(u,0);
    return tmp[1]*tmp[2]*2+tmp[0]*tmp[0];
}
void divide(int u){
    ans+=calc(u,0);
    vis[u]=1;
    for(int i=head[u];~i;i=edges[i].nex){
        int v = edges[i].v;
        if(vis[v])continue;
        ans-=calc(v,edges[i].w);
        maxp[rt=0]=sum=siz[v];
        getrt(v,0);
        getrt(rt,0);
        divide(rt);
    }
}
int main(){
    memset(head,-1,sizeof(head));
    int n;
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        w%=3;
        add(u,v,w);
        add(v,u,w);
    }
    maxp[0]=sum=n;
    getrt(1,0);
    getrt(rt,0);
    divide(rt);
    int gg = gcd(ans,n*n);
    printf("%d/%d",ans/gg,(n*n)/gg);
}