GGAutomaton's Blog
0%

树链剖分模板

发表于 分类于 ，

原理：http://www.cnblogs.com/zwfymqz/p/8094500.html
模板题：https://www.luogu.org/problemnew/show/P3384
操作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
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long LL;
int head[100005],vet[200005],nxt[200005],num;
int fa[100005],son[100005],sz[100005];//son是重儿子
int depth[100005],top[100005];//均为原编号，top是x所在重链的顶点
int idx[100005],cnt;//idx是x的新编号
int a[100005],b[100005];//a是原编号的值，val是新编号的值
LL sum[400005],tag[400005];//均为新编号
int n,m,root,P;
inline void addedge(int x,int y) {
	num++;vet[num]=y;nxt[num]=head[x];head[x]=num;
	num++;vet[num]=x;nxt[num]=head[y];head[y]=num;
} 
void dfs1(int x,int ff,int dep) {
	depth[x]=dep;fa[x]=ff;sz[x]=1;
	int mx=0;
	for (int e=head[x];e;e=nxt[e]) {
		int v=vet[e];
		if (ff==v) continue;
		dfs1(v,x,dep+1);
		sz[x]+=sz[v];
		if (sz[v]>mx) mx=sz[v],son[x]=v;
	}
}
void dfs2(int x,int tp) {
	idx[x]=++cnt;
	b[cnt]=a[x]%P;
	top[x]=tp;
	if (!son[x]) return;//别忘了这句
	dfs2(son[x],tp);
	for (int e=head[x];e;e=nxt[e])
		if (!idx[vet[e]]) dfs2(vet[e],vet[e]);
}
void build(int l,int r,int pp) {
	if (l==r) {
		sum[pp]=b[l];
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,pp<<1);
	build(mid+1,r,pp<<1|1);
	sum[pp]=(sum[pp<<1]+sum[pp<<1|1])%P;
}
inline void pushdown(int l,int r,int pp) {
	if (!tag[pp]) return;
	if (l==r) {tag[pp]=0;return;}
	int mid=(l+r)>>1;
	sum[pp<<1]=(sum[pp<<1]+tag[pp]*(mid-l+1))%P;
	tag[pp<<1]=(tag[pp<<1]+tag[pp])%P;
	sum[pp<<1|1]=(sum[pp<<1|1]+tag[pp]*(r-mid))%P;
	tag[pp<<1|1]=(tag[pp<<1|1]+tag[pp])%P;
	tag[pp]=0;
}
LL query(int l,int r,int pp,int ll,int rr) {
	if (l==ll && r==rr) return sum[pp];
	pushdown(l,r,pp);
	int mid=(l+r)>>1;
	if (mid>=rr) return query(l,mid,pp<<1,ll,rr);
	else if (mid<ll) return query(mid+1,r,pp<<1|1,ll,rr);
	else return (query(l,mid,pp<<1,ll,mid)+query(mid+1,r,pp<<1|1,mid+1,rr))%P;
}
void update(int l,int r,int pp,int ll,int rr,int v) {
	if (l==ll && r==rr) {
		sum[pp]=(sum[pp]+(LL)(r-l+1)*v)%P;
		tag[pp]=(tag[pp]+v)%P;
		return;
	}
	pushdown(l,r,pp);
	int mid=(l+r)>>1;
	if (mid>=rr) update(l,mid,pp<<1,ll,rr,v);
	else if (mid<ll) update(mid+1,r,pp<<1|1,ll,rr,v);
	else update(l,mid,pp<<1,ll,mid,v),update(mid+1,r,pp<<1|1,mid+1,rr,v);
	sum[pp]=(sum[pp<<1]+sum[pp<<1|1])%P;
}
inline LL pathsum(int x,int y) {
	LL ans=0;
	while (top[x]!=top[y]) {
		if (depth[top[x]]<depth[top[y]]) swap(x,y);
		ans=(ans+query(1,n,1,idx[top[x]],idx[x]))%P;
		x=fa[top[x]];
	}
	if (depth[x]>depth[y]) swap(x,y);
	ans=(ans+query(1,n,1,idx[x],idx[y]))%P;
	return ans;
}
inline void pathadd(int x,int y,int v) {
	while (top[x]!=top[y]) {
		if (depth[top[x]]<depth[top[y]]) swap(x,y);
		update(1,n,1,idx[top[x]],idx[x],v);
		x=fa[top[x]];
	}
	if (depth[x]>depth[y]) swap(x,y);
	update(1,n,1,idx[x],idx[y],v);
}
int main() {
	cin >> n >> m >> root >> P;
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=1;i<n;i++) {
		int x,y;
		scanf("%d%d",&x,&y);
		addedge(x,y);
	}
	dfs1(root,0,1);
	dfs2(root,root);
	build(1,n,1);
	while (m--) {
		int op,x,y,z;
		scanf("%d",&op);
		if (op==1) {
			scanf("%d%d%d",&x,&y,&z);
			pathadd(x,y,z);
		}
		if (op==2) {
			scanf("%d%d",&x,&y);
			printf("%lld\n",pathsum(x,y));
		}
		if (op==3) {
			scanf("%d%d",&x,&z);
			update(1,n,1,idx[x],idx[x]+sz[x]-1,z%P);
		}
		if (op==4) {
			scanf("%d",&x);
			printf("%lld\n",query(1,n,1,idx[x],idx[x]+sz[x]-1));
		}
	}
	return 0;
}

据说n特别大的时候，需要使用bfs防爆栈