树链剖分

发表于 | 更新于: | 分类于 | | 阅读数

最为经典的树链剖分就是对于树删一条链进行同时加或者减操作，然后每次询问。

洛谷P3348

题意：最为经典的模板题。

已知一棵包含$N$个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：

操作1： 格式： $1$ $x$ $y$ $z$ 表示将树从$x$到$y$结点最短路径上所有节点的值都加上$z$

操作2： 格式： $2$ $x$ $y$ 表示求树从$x$到$y$结点最短路径上所有节点的值之和

操作3： 格式： $3$ $x$ $z$ 表示将以$x$为根节点的子树内所有节点值都加上$z$

操作4： 格式： $4$ $x$ 表示求以$x$为根节点的子树内所有节点值之和

思路：模板接好（树链剖分+线段树）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll maxn=1e5+10;
struct edge{
    ll next,to;
}e[maxn<<1];
struct node{
    ll l,r,ls,rs,sum,lazy;
}a[maxn<<1];
ll n,m,r,rt,mod,v[maxn],head[maxn],cnt,f[maxn],d[maxn],son[maxn],size[maxn],top[maxn],id[maxn],rk[maxn];
void add(ll x,ll y){
    e[++cnt].next=head[x];
    e[cnt].to=y;
    head[x]=cnt;
}
void dfs1(ll x){
    size[x]=1,d[x]=d[f[x]]+1;
    for(ll v,i=head[x];i;i=e[i].next)
        if((v=e[i].to)!=f[x]){
            f[v]=x,dfs1(v),size[x]+=size[v];
            if(size[son[x]]<size[v])
                son[x]=v;
        }
}
void dfs2(ll x,ll tp){
    top[x]=tp,id[x]=++cnt,rk[cnt]=x;
    if(son[x])
        dfs2(son[x],tp);
    for(ll v,i=head[x];i;i=e[i].next)
        if((v=e[i].to)!=f[x]&&v!=son[x])
            dfs2(v,v);
}
inline void pushup(ll x){
    a[x].sum=(a[a[x].ls].sum+a[a[x].rs].sum)%mod;
}
void build(ll l,ll r,ll x){
    if(l==r){
        a[x].sum=v[rk[l]],a[x].l=a[x].r=l;
        return;
    }
    ll mid=(l+r)>>1;
    a[x].ls=cnt++,a[x].rs=cnt++;
    build(l,mid,a[x].ls),build(mid+1,r,a[x].rs);
    a[x].l=a[a[x].ls].l,a[x].r=a[a[x].rs].r;
    pushup(x);
}
inline ll len(ll x){
    return a[x].r-a[x].l+1;
}
inline void pushdown(ll x){
    if(a[x].lazy){
        ll ls=a[x].ls,rs=a[x].rs,lz=a[x].lazy;
        (a[ls].lazy+=lz)%=mod,(a[rs].lazy+=lz)%=mod;
        (a[ls].sum+=lz*len(ls))%=mod,(a[rs].sum+=lz*len(rs))%=mod;
        a[x].lazy=0;
    }
}
void update(ll l,ll r,ll c,ll x){
    if(a[x].l>=l&&a[x].r<=r){
        (a[x].lazy+=c)%=mod,(a[x].sum+=len(x)*c)%=mod;
        return;
    }
    pushdown(x);
    ll mid=(a[x].l+a[x].r)>>1;
    if(mid>=l)
        update(l,r,c,a[x].ls);
    if(mid<r)
        update(l,r,c,a[x].rs);
    pushup(x);
}
ll query(ll l,ll r,ll x){
    if(a[x].l>=l&&a[x].r<=r)
        return a[x].sum;
    pushdown(x);
    ll mid=(a[x].l+a[x].r)>>1,tot=0;
    if(mid>=l)
        tot+=query(l,r,a[x].ls);
    if(mid<r)
        tot+=query(l,r,a[x].rs);
    return tot%mod;
}
inline ll sum(ll x,ll y){
    ll ret=0;
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]])
            swap(x,y);
        (ret+=query(id[top[x]],id[x],rt))%=mod;
        x=f[top[x]];
    }
    if(id[x]>id[y])
        swap(x,y);
    return (ret+query(id[x],id[y],rt))%mod;
}
inline void updates(ll x,ll y,ll c){
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]])
            swap(x,y);
        update(id[top[x]],id[x],c,rt);
        x=f[top[x]];
    }
    if(id[x]>id[y])
        swap(x,y);
    update(id[x],id[y],c,rt);
}
int main(){
    scanf("%lld %lld %lld %lld",&n,&m,&r,&mod);
    for(ll i=1;i<=n;i++)
        scanf("%lld",&v[i]);
    for(ll x,y,i=1;i<n;i++){
        scanf("%lld %lld",&x,&y);
        add(x,y),add(y,x);
    }
    cnt=0,dfs1(r),dfs2(r,r);
    cnt=0,build(1,n,rt=cnt++);
    for(ll op,x,y,k,i=1;i<=m;i++){
        scanf("%lld",&op);
        if(op==1){
            scanf("%lld %lld %lld",&x,&y,&k);
            updates(x,y,k);
        }
        else if(op==2){
            scanf("%lld %lld",&x,&y);
            printf("%lld\n",sum(x,y));
        }
        else if(op==3){
            scanf("%lld %lld",&x,&y);
            update(id[x],id[x]+size[x]-1,y,rt);
        }
        else{
            scanf("%lld",&x);
            printf("%lld\n",query(id[x],id[x]+size[x]-1,rt));
        }
    }
    return 0;
}
thanks!