树剖

发表于 | 更新于 | 阅读次数：

例题

题目描述

如题，已知一棵包含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为根节点的子树内所有节点值之和

输入输出格式

输入格式：

第一行包含4个正整数N、M、R、P，分别表示树的结点个数、操作个数、根节点序号和取模数（即所有的输出结果均对此取模）。

接下来一行包含N个非负整数，分别依次表示各个节点上初始的数值。

接下来N-1行每行包含两个整数x、y，表示点x和点y之间连有一条边（保证无环且连通）

接下来M行每行包含若干个正整数，每行表示一个操作，格式如下：

操作1： 1 x y z

操作2： 2 x y

操作3： 3 x z

操作4： 4 x

输出格式：

输出包含若干行，分别依次表示每个操作2或操作4所得的结果（对P取模）

sample input

1
2
3
4
5
6
7
8
9
10
11
5 5 2 24
7 3 7 8 0 
1 2
1 5
3 1
4 1
3 4 2
3 2 2
4 5
1 5 1 3
2 1 3

sample out

1
2
2
21

1.一些定义

重儿子：父亲节点的所有儿子中子树结点数目最多（size最大）的结点；

轻儿子：父亲节点中除了重儿子以外的儿子；

重边：父亲结点和重儿子连成的边；

轻边：父亲节点和轻儿子连成的边；

重链：由多条重边连接而成的路径；

轻链：由多条轻边连接而成的路径；

2.操作

1.用两个dfs分别处理

dfs1处理子树大小，深度以及重儿子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void dfs1(int x,int fa)
{
    sz[x]=1;
    int maxs=-1;
    if(h[x])
    for(register int i=h[x];i;i=e[i].nt)
    {
        int u=e[i].end;
        if(u==fa)continue;
        deep[u]=deep[x]+1;
        faa[u]=x;
        dfs1(u,x);
        sz[x]+=sz[u];
        if(sz[u]>maxs)
        {
            son[x]=u;
            maxs=sz[u];
        }
    }
}

dfs2处理出树链,并重新编号，这样树链上的点的编号就是连续的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void dfs1(int x,int fa)
{
    sz[x]=1;
    int maxs=-1;
    if(h[x])
    for(register int i=h[x];i;i=e[i].nt)
    {
        int u=e[i].end;
        if(u==fa)continue;
        deep[u]=deep[x]+1;
        faa[u]=x;
        dfs1(u,x);
        sz[x]+=sz[u];
        if(sz[u]>maxs)
        {
            son[x]=u;
            maxs=sz[u];
        }
    }
}

2.处理子树和查询子树是处理自己的编号+size的一段区间，直接线段树上修改即可

修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void change (int k,int l,int r,int p,int q,int v)
{
    
    if(l>=p&&r<=q)
    {
        f[k]=(v*(r-l+1)+f[k])%mod;
        add[k]=(v+add[k])%mod;
        return;
    }
    int mid=(l+r)>>1;
	if(add[k])
    push_down(k,l,r,add[k]);
    if(p<=mid)
    {
        change(k<<1,l,mid,p,q,v);
    }
    if(q>mid)
    {
        change(k<<1|1,mid+1,r,p,q,v);
    }
    f[k]=(f[k<<1]+f[k<<1|1])%mod;
}

查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int query(int k,int l,int r,int p,int q)
{
    
    if(l>=p&&r<=q)
    {
        return f[k]%mod;
    }
    int mid=(l+r)>>1;
    if(add[k])
    push_down(k,l,r,add[k]);
    int ans=0;
    if(p<=mid)
    {
        ans=query(k<<1,l,mid,p,q);
    }
    if(q>mid)
    {
        ans=(query(k<<1|1,mid+1,r,p,q)+ans)%mod;
    }
    return ans%mod;
}

3.对于树链，点的编号是连续的，所以可以用线段树来进行维护，那么我们就可以维护一条路径。

1
2
3
4
5
6
7
8
9
10
11
12
void build(int k,int l,int r)
{
    if(l==r)
    {
        f[k]=wh[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    f[k]=(f[k<<1]+f[k<<1|1])%mod;
}

4.对于一条路径可以转化成两个节点跳到它们的LCA并不断修改路径上点的过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void changeroad(int x,int y,int v)
{
    int fx=top[x],fy=top[y];
    while(fx!=fy)
    {
        if(deep[fx]<deep[fy])
        {
            swap(x,y);
            swap(fx,fy);
        }
        change (1,1,cnt,id[fx],id[x],v);
        x=faa[fx];
        fx=top[x];
    }
    if(id[x]>id[y])
    {
        swap(x,y);
    }
    change (1,1,cnt,id[x],id[y],v);

}

5.查询就是跳LCA的时候查询区间，基本与修改路径相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int queryroad(int x,int y)
{
    int ans=0;
    int fx=top[x],fy=top[y];
    while(fx!=fy)
    {
        if(deep[fx]<deep[fy])
        {
            swap(x,y);
            swap(fx,fy);
        }
        ans=(query(1,1,cnt,id[fx],id[x])+ans)%mod;
        x=faa[fx];
        fx=top[x];
    }
    if(id[x]>id[y])swap(x,y);
    ans+=query(1,1,cnt,id[x],id[y]);
    return ans%mod;
}

3.完整代码

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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
#include<bits/stdc++.h>
#define swap mswap
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define int long long 
//#pragma GCC optimize(3)
using namespace std;

void swap(int &x,int &y)
{
    x^=y^=x^=y;
}
void read(int &x)
{
    x=0;
    char ch=getchar();
    int pd=1;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            pd=-pd;
        }
        ch=getchar();
    }
    while(ch<='9'&&ch>='0')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    x*=pd;
}
void write(const int &x)
{
    char f[100001];
    int s=0;
    int tmp=x;
    if(tmp==0)
    {
        putchar('0');
        return;
    }
    if(tmp<0)
    {
        tmp=-tmp;
        putchar('-');
    }
    while(tmp>0)
    {
        f[s++]=tmp%10+'0';
        tmp/=10;
    }
    while(s>0)
    {
        putchar(f[--s]);
    }
}

const int N=4e5+10;
int t,h[N],son[N],id[N],w[N],wh[N],mod,f[N],add[N],sz[N],deep[N],cnt,top[N],faa[N];
struct dd
{
    int end,nt;
}e[400010];
void ad(int begin,int end)
{
    ++t;
    e[t].end=end;
    e[t].nt=h[begin];
    h[begin]=t;
}


void push_down(int k,int l,int r,int v)
{
    int mid=(l+r)>>1;
    add[k<<1]=(add[k<<1]+v)%mod;
    add[k<<1|1]=(add[k<<1|1]+v)%mod;
    f[k<<1]=(f[k<<1]+v*(mid-l+1)%mod)%mod;
    f[k<<1|1]=(f[k<<1|1]+v*(r-mid)%mod)%mod;
    add[k]=0; 
}

void build(int k,int l,int r)
{
    if(l==r)
    {
        f[k]=wh[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    f[k]=(f[k<<1]+f[k<<1|1])%mod;
}


void change (int k,int l,int r,int p,int q,int v)
{
    
    if(l>=p&&r<=q)
    {
        f[k]=(v*(r-l+1)+f[k])%mod;
        add[k]=(v+add[k])%mod;
        return;
    }
    int mid=(l+r)>>1;
	if(add[k])
    push_down(k,l,r,add[k]);
    if(p<=mid)
    {
        change(k<<1,l,mid,p,q,v);
    }
    if(q>mid)
    {
        change(k<<1|1,mid+1,r,p,q,v);
    }
    f[k]=(f[k<<1]+f[k<<1|1])%mod;
}


int query(int k,int l,int r,int p,int q)
{
    
    if(l>=p&&r<=q)
    {
        return f[k]%mod;
    }
    int mid=(l+r)>>1;
    if(add[k])
    push_down(k,l,r,add[k]);
    int ans=0;
    if(p<=mid)
    {
        ans=query(k<<1,l,mid,p,q);
    }
    if(q>mid)
    {
        ans=(query(k<<1|1,mid+1,r,p,q)+ans)%mod;
    }
    return ans%mod;
}


void dfs1(int x,int fa)
{
    sz[x]=1;
    int maxs=-1;
    if(h[x])
    for(register int i=h[x];i;i=e[i].nt)
    {
        int u=e[i].end;
        if(u==fa)continue;
        deep[u]=deep[x]+1;
        faa[u]=x;
        dfs1(u,x);
        sz[x]+=sz[u];
        if(sz[u]>maxs)
        {
            son[x]=u;
            maxs=sz[u];
        }
    }
}

void dfs2(int x,int topf)
{
    id[x]=++cnt;
    top[x]=topf;
    wh[cnt]=w[x];
    if(!son[x])return;
    dfs2(son[x],topf);
    for(register int i=h[x];i;i=e[i].nt)
    {
        int u=e[i].end;
        if(u==faa[x]||u==son[x])continue;
        dfs2(u,u);
    }
}

int queryroad(int x,int y)
{
    int ans=0;
    int fx=top[x],fy=top[y];
    while(fx!=fy)
    {
        if(deep[fx]<deep[fy])
        {
            swap(x,y);
            swap(fx,fy);
        }
        ans=(query(1,1,cnt,id[fx],id[x])+ans)%mod;
        x=faa[fx];
        fx=top[x];
    }
    if(id[x]>id[y])swap(x,y);
    ans+=query(1,1,cnt,id[x],id[y]);
    return ans%mod;
}

void changeroad(int x,int y,int v)
{
    int fx=top[x],fy=top[y];
    while(fx!=fy)
    {
        if(deep[fx]<deep[fy])
        {
            swap(x,y);
            swap(fx,fy);
        }
        change (1,1,cnt,id[fx],id[x],v);
        x=faa[fx];
        fx=top[x];
    }
    if(id[x]>id[y])
    {
        swap(x,y);
    }
    change (1,1,cnt,id[x],id[y],v);

}

int n,m,rt;
signed main()
{
    read(n);
    read(m);
    read(rt);
    read(mod);
    for(register int i=1;i<=n;++i)
    {
        read(w[i]);
    }
    for(register int i=1;i<=n-1;++i)
    {
        int kk,aa;
        read(kk);
        read(aa);
        ad(kk,aa);
        ad(aa,kk);
    }
    
    faa[rt]=rt;
    deep[rt]=1;
    dfs1(rt,0);
    dfs2(rt,rt);build(1,1,cnt);
    for(register int i=1;i<=m;++i)
    {
        int aa;
        read(aa);
        if(aa==1)
        {
            int ll,rr,zz;
            read(ll);
            read(rr);
            read(zz);
            changeroad(ll,rr,zz%mod);
        }
        if(aa==2)
        {
            int ll,rr;
            read(ll);
            read(rr);
            write(queryroad(ll,rr)%mod);
            puts("");
        }
        if(aa==3)
        {
            int xx,zz;
            read(xx);
            read(zz);
            change (1,1,cnt,id[xx],id[xx]+sz[xx]-1,zz%mod);
        }
        if(aa==4)
        {
            int xx;
            read(xx);
            write(query(1,1,cnt,id[xx],id[xx]+sz[xx]-1)%mod);
            puts("");
        }
    }
}