点分树

luckydrawbox · 2024-02-27 15:00:55 · 算法·理论

变量

函数

代码

struct DFTree{
    int rt;
    int fat[N],sz[N],mx[N],vis[N];
    void findroot(int x,int fa,int S){
        sz[x]=1;mx[x]=0;
        for(int i=head[x];i;i=nxt[i]){
            int y=ver[i];
            if(y==fa||vis[y])continue;
            findroot(y,x,S);
            sz[x]+=sz[y];
            mx[x]=max(mx[x],sz[y]);
        }
        mx[x]=max(mx[x],S-sz[x]);
        if(!rt||mx[x]<mx[rt])rt=x;
    }
    void divide(int x,int S){
        vis[x]=1;int S_;
        tree.make(segrt1[x]);tree.make(segrt2[x]);
        for(int i=head[x];i;i=nxt[i]){
            int y=ver[i];
            if(vis[y])continue;
            rt=0;S_=(sz[x]<sz[y]?S-sz[x]:sz[y]);
            findroot(y,x,S_);fat[rt]=x;
            divide(rt,S_);
        }
    }
    void build(int n){
        rt=0;findroot(1,0,n);divide(rt,n);
    }
    void change(int x,int v){
        for(int y=x;y;y=fat[y]){
            tree.change(segrt1[y],dist(x,y),v);
            if(fat[y])
                tree.change(segrt2[y],dist(x,fat[y]),v);
        }
    }
    int ask(int x,int k){
        int ans=0;
        for(int y=x,z=0,d;y;y=fat[z=y]){
            if(dist(x,y)>k)continue;
            d=k-dist(x,y);
            ans+=tree.ask(segrt1[y],0,d);
            if(z)ans-=tree.ask(segrt2[z],0,d);
        }
        return ans;
    }
}dft;