树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！

练习情况:

P3384 【模板】轻重链剖分/树链剖分

P3178 [HAOI2015]树上操作

P2590 [ZJOI2008]树的统计

P3833 [SHOI2012]魔法树

P2146 [NOI2015] 软件包管理器

P4427 [BJOI2018]求和

P3258 [JLOI2014]松鼠的新家

P3128 [USACO15DEC]Max Flow P

P6098 [USACO19FEB]Cow Land G

以上都是维护节点的树剖，本质都是一个东西。

树剖

将整颗树，剖分成轻重链，再用数据结构维护。

操作主要是

• 1 x y z，表示将树从 \(x\) 到 \(y\) 结点最短路径上所有节点的值都加上 \(z\)。

• 2 x y，表示求树从 \(x\) 到 \(y\) 结点最短路径上所有节点的值之和。

• 3 x z，表示将以 \(x\) 为根节点的子树内所有节点值都加上 \(z\)。

• 4 x 表示求以 \(x\) 为根节点的子树内所有节点值之和。

数据结构维护的一般是节点的 dfs 序。

对于最短路径上的操作，我们要用类似 LCA 的方法跳链，对路径上的链进行操作。

对于子树的操作，因为 dfs 序是连续的，所以可以直接进行维护。

Code:

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define Ld long double
#define l(p) tree[p].l
#define r(p) tree[p].r
#define sum(p) tree[p].sum
#define add(p) tree[p].add
const int N = 100005,M=100005;

LL n,m,r,mod,a[N];
LL head[N],net[M*2],val[M*2],idx=1;
LL f[N],d[N],son[N],id[N],siz[N],rk[N],tp[N],cnt;
LL op,x,y,z;
struct Segment_tree{
    LL sum,add,l,r;
}tree[N*4];

inline char readc(){
    char ch=getchar();
    while(!((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z'))) ch=getchar();
    return ch;
}
inline LL read(){
    LL s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+ch-'0';ch=getchar();}
    return s*w;
}
inline void print(LL x){
    char F[200];LL cnt=0;
    if(x==0){putchar('0');putchar('\n');return ;}
    if(x<0){putchar('-');x=-x;}
    while(x){F[++cnt]=x%10;x/=10;}
    while(cnt) putchar(F[cnt--]+'0');
    putchar('\n');return ;
}

void add1(LL x,LL y){
    val[++idx]=y;
    net[idx]=head[x];
    head[x]=idx;
    return ;
}

void dfs1(LL u,LL fa){
    f[u]=fa,d[u]=d[fa]+1,siz[u]=1;
    for(int i=head[u];i;i=net[i]){
        LL v=val[i];
        if(v==fa) continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])
            son[u]=v;
    }
    return ;
}

void dfs2(LL u,LL top){
    tp[u]=top,id[u]=++cnt,rk[cnt]=u;
    if(son[u]) dfs2(son[u],top);
    for(int i=head[u];i;i=net[i]){
        LL v=val[i];
        if(v!=f[u]&&v!=son[u])
        dfs2(v,v);
    }
    return ;
}

void pushup(LL p){
    sum(p)=(sum(p<<1)+sum(p<<1|1))%mod;
    return ;
}

void pushdown(LL p){
    if(!add(p)) return ;
    add(p<<1)=(add(p<<1)+add(p))%mod;
    add(p<<1|1)=(add(p<<1|1)+add(p))%mod;
    sum(p<<1)=(sum(p<<1)+add(p)*(r(p<<1)-l(p<<1)+1))%mod;
    sum(p<<1|1)=(sum(p<<1|1)+add(p)*(r(p<<1|1)-l(p<<1|1)+1))%mod;
    add(p)=0;
    return ;

}

void build(LL p,LL l,LL r){
    l(p)=l,r(p)=r;
    if(l==r){
        sum(p)=a[rk[l]];
        return ;
    }
    LL mid=(l(p)+r(p))>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    pushup(p);
}

void change2(LL p,LL l,LL r,LL k){
    if(l(p)>=l&&r(p)<=r){
        add(p)=(add(p)+k)%mod;
        sum(p)=(sum(p)+k*(r(p)-l(p)+1))%mod;
        return ;
    }
    pushdown(p);
    LL mid=(l(p)+r(p))>>1;
    if(l<=mid) change2(p<<1,l,r,k);
    if(r>mid) change2(p<<1|1,l,r,k);
    pushup(p);
    return ;
}

void change1(LL p,LL l,LL r,LL k){
    while(tp[l]!=tp[r]){
        if(d[tp[l]]<d[tp[r]]) swap(l,r);
        change2(1,id[tp[l]],id[l],k);
        l=f[tp[l]];
    }
    if(id[l]>id[r]) swap(l,r);
    change2(1,id[l],id[r],k);
    return ;
}

LL query2(LL p,LL l,LL r){
    if(l(p)>=l&&r(p)<=r) return sum(p);
    pushdown(p);
    LL mid=(l(p)+r(p))>>1,val=0;
    if(l<=mid) val+=query2(p<<1,l,r);
    if(r>mid) val+=query2(p<<1|1,l,r);
    return val%mod;
}

LL query1(LL p,LL l,LL r){
    LL val=0;
    while(tp[l]!=tp[r]){
        if(d[tp[l]]<d[tp[r]]) swap(l,r);
        val=(val+query2(1,id[tp[l]],id[l]))%mod;
        l=f[tp[l]];
    }
    if(id[l]>id[r]) swap(l,r);
    return (val+query2(1,id[l],id[r]))%mod;
}

int main(){
    n=read(),m=read(),r=read(),mod=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(LL i=1,u,v;i<n;i++){
        u=read(),v=read();
        add1(u,v);
        add1(v,u);
    }
    dfs1(r,0);
    dfs2(r,r);
    build(1,1,n);
    for(int i=1;i<=m;i++){
        op=read(),x=read();
        if(op==1){
            y=read(),z=read();
            change1(1,x,y,z);
        }else
        if(op==2){
            y=read();
            print(query1(1,x,y));
        }else
        if(op==3){
            z=read();
            change2(1,id[x],id[x]+siz[x]-1,z);
        }else
        if(op==4){
            print(query2(1,id[x],id[x]+siz[x]-1));
        }
    }
    return 0;
}

P4114 Qtree1

P4315 月下“毛景树”

P3038 [USACO11DEC]Grass Planting G

以上是维护边的树剖。

这个相对于维护点的树剖只有一点点差别。

我们将每条边的权值赋给边两端深度较大的那个节点。

差别

在两点之间维护时

if(id[l]>id[r]) swap(l,r);
    return max(val,query2(1,id[l]+1,id[r]));

id[l] 为 LCA 这个节点的权值不包含在要维护的边内，所以要加 1 。

Code:

P4315

一天写了挺多树剖的，但这些都感觉长的差不多，只是把序列拍在树上，增加1kb码量。

那么将线段树的题目搞到树上是不是就是一道新的树剖。