树链剖分

luckydrawbox · 2022-11-19 22:31:47 · 个人记录

重链剖分

宏定义

变量

函数

代码

#define pl p<<1
#define pr p<<1|1
#define pf a[p].fa
#define pde a[p].dep
#define psi a[p].sze
#define pte a[p].ted
#define pdf a[p].dfn
#define pso a[p].son
#define pt a[p].top
#define pc a[p].ced
#define TCP_T ll
const TCP_T inf=1e9;
struct Segment_Tree{
    struct Tree{
        int l,r;
        int tag;
        TCP_T val;
    }a[N*4];
    void pushup(int p){
        ;
    }
    void pushdown(int p){
        ;
    }
    void build(int p,int l,int r,int *rnk){
        a[p].l=l;
        a[p].r=r;
        if(l==r){
            ;
            return;
        }
        int mid=(l+r)>>1;
        build(pl,l,mid,rnk);
        build(pr,mid+1,r,rnk);
        pushup(p);
    }
    void change(int p,int l,int r,TCP_T v){
        if(l<=a[p].l&&a[p].r<=r){
            ;
            return;
        }
        pushdown(p);
        int mid=(a[p].l+a[p].r)>>1;
        if(l<=mid)
            change(pl,l,r,v);
        if(r>mid)
            change(pr,l,r,v);
        pushup(p);
    }
    TCP_T ask(int p,int l,int r){
        if(l<=a[p].l&&a[p].r<=r){
            ;
            return ;
        }
        pushdown(p);
        int mid=(a[p].l+a[p].r)>>1;
        TCP_T ans=0;
        if(l<=mid)
            ans+=ask(pl,l,r);
        if(r>mid)
            ans+=ask(pr,l,r);
        return ans;
    }
}tree;
struct TCP{
    struct Node{
        int fa,dep,dfn;//self
        int sze,ted;//tree
        int son,top,ced;//chain
    }a[N];
    int cnt,rnk[N];
    void dfs1(int p){
        pso=-1;
        psi=1;
        for(int i=head[p];i;i=nxt[i]){
            int y=ver[i];
            if(!a[y].dep){
                a[y].dep=pde+1;
                a[y].fa=p;
                dfs1(y);
                psi+=a[y].sze;
                if(pso==-1||a[y].sze>a[pso].sze)
                    pso=y;
            }
        }
    }
    int dfs2(int p,int q){
        pt=q;
        pdf=++cnt;
        rnk[cnt]=pte=p;
        if(pso==-1){
            int ted=pte;
            pc=cnt;
            while(p!=q){
                p=pf;
                pc=cnt;
            }
            return ted;
        }
        pte=dfs2(pso,q);
        for(int i=head[p];i;i=nxt[i]){
            int y=ver[i];
            if(y!=pso&&y!=pf)
                pte=dfs2(y,y);
        }
        return pte;
    }
    void init(int root,int n){
        cnt=0;
        a[root].dep=1;
        dfs1(root);
        dfs2(root,root);
        tree.build(1,1,n,rnk);
    }
    void change1(int u,int v,TCP_T z){
        int fu=a[u].top,fv=a[v].top;
        while(fu^fv){
            if(a[fu].dep>=a[fv].dep){
                tree.change(1,a[fu].dfn,a[u].dfn,z);
                u=a[fu].fa;
            }
            else{
                tree.change(1,a[fv].dfn,a[v].dfn,z);
                v=a[fv].fa;
            }
            fu=a[u].top;
            fv=a[v].top;
        }
        tree.change(1,min(a[u].dfn,a[v].dfn),max(a[u].dfn,a[v].dfn),z);
    }
    void change2(int p,TCP_T z){
        tree.change(1,pdf,a[pte].dfn,z);
    }
    TCP_T ask1(int u,int v){
        TCP_T ans=0;
        int fu=a[u].top,fv=a[v].top;
        while(fu^fv){
            if(a[fu].dep>=a[fv].dep){
                ans=ans+tree.ask(1,a[fu].dfn,a[u].dfn);
                u=a[fu].fa;
            }
            else{
                ans=ans+tree.ask(1,a[fv].dfn,a[v].dfn);
                v=a[fv].fa;
            }
            fu=a[u].top;
            fv=a[v].top;
        }
        ans=ans+tree.ask(1,min(a[u].dfn,a[v].dfn),max(a[u].dfn,a[v].dfn));
        return ans;
    }
    TCP_T ask2(int p){
        return tree.ask(1,pdf,a[pte].dfn);
    }
}tr;