今天我刷题了吗
搜索文档…
树链剖分
1
#include <bits/stdc++.h>
2
3
using namespace std;
4
using ll = long long;
5
using p = pair<int, int>;
6
const int maxn(1e5 + 10);
7
const int maxm(2e5 + 10);
8
int mod, ecnt, v[maxn], head[maxn];
9
int dep[maxn], siz[maxn], fa[maxn], son[maxn];
10
int tim, dfn[maxn], top[maxn], w[maxn];
11
12
struct edge {
13
int to, nxt;
14
} edges[maxm];
15
16
struct node {
17
int l, r;
18
int sum, lz;
19
} tree[maxn << 2];
20
21
template<typename T = int>
22
inline const T read()
23
{
24
T x = 0, f = 1;
25
char ch = getchar();
26
while (ch < '0' || ch > '9') {
27
if (ch == '-') f = -1;
28
ch = getchar();
29
}
30
while (ch >= '0' && ch <= '9') {
31
x = (x << 3) + (x << 1) + ch - '0';
32
ch = getchar();
33
}
34
return x * f;
35
}
36
37
template<typename T>
38
inline void write(T x, bool ln)
39
{
40
if (x < 0) {
41
putchar('-');
42
x = -x;
43
}
44
if (x > 9) write(x / 10, false);
45
putchar(x % 10 + '0');
46
if (ln) putchar(10);
47
}
48
49
inline void addEdge(int u, int v)
50
{
51
edges[ecnt].to = v;
52
edges[ecnt].nxt = head[u];
53
head[u] = ecnt++;
54
}
55
56
inline int ls(int cur)
57
{
58
return cur << 1;
59
}
60
61
inline int rs(int cur)
62
{
63
return cur << 1 bitor 1;
64
}
65
66
inline void push_up(int cur)
67
{
68
tree[cur].sum = tree[ls(cur)].sum + tree[rs(cur)].sum;
69
}
70
71
inline void push_down(int cur)
72
{
73
if (tree[cur].lz) {
74
tree[ls(cur)].lz = (tree[ls(cur)].lz + tree[cur].lz) % mod;
75
tree[rs(cur)].lz = (tree[rs(cur)].lz + tree[cur].lz) % mod;
76
tree[ls(cur)].sum = (tree[ls(cur)].sum + (tree[ls(cur)].r - tree[ls(cur)].l + 1) * tree[cur].lz) % mod;
77
tree[rs(cur)].sum = (tree[rs(cur)].sum + (tree[rs(cur)].r - tree[rs(cur)].l + 1) * tree[cur].lz) % mod;
78
tree[cur].lz = false;
79
}
80
}
81
82
void build(int cur, int l, int r)
83
{
84
tree[cur].l = l;
85
tree[cur].r = r;
86
if (l == r) {
87
tree[cur].sum = w[l];
88
return;
89
}
90
int mid = (l + r) >> 1;
91
build(ls(cur), l, mid);
92
build(rs(cur), mid + 1, r);
93
push_up(cur);
94
}
95
96
void update(int cur, int l, int r, int v)
97
{
98
if (tree[cur].l == l and tree[cur].r == r) {
99
tree[cur].sum = (tree[cur].sum + (r - l + 1) * v) % mod;
100
tree[cur].lz = (tree[cur].lz + v) % mod;
101
return;
102
}
103
push_down(cur);
104
int mid = (tree[cur].l + tree[cur].r) >> 1;
105
if (r <= mid) {
106
update(ls(cur), l, r, v);
107
} else if (l > mid) {
108
update(rs(cur), l, r, v);
109
} else {
110
update(ls(cur), l, mid, v);
111
update(rs(cur), mid + 1, r, v);
112
}
113
push_up(cur);
114
}
115
116
int query(int cur, int l, int r)
117
{
118
if (tree[cur].l == l and tree[cur].r == r) {
119
return tree[cur].sum;
120
}
121
push_down(cur);
122
int mid = (tree[cur].l + tree[cur].r) >> 1;
123
if (r <= mid) {
124
return query(ls(cur), l, r);
125
}
126
if (l > mid) {
127
return query(rs(cur), l, r);
128
}
129
return (query(ls(cur), l, mid) + query(rs(cur), mid + 1, r)) % mod;
130
}
131
132
void dfs1(int cur, int pre)
133
{
134
fa[cur] = pre;
135
dep[cur] = dep[pre] + 1;
136
siz[cur] = 1;
137
int maxsize = -1;
138
for (int i = head[cur]; compl i; i = edges[i].nxt) {
139
int nxt = edges[i].to;
140
if (nxt == pre) continue;
141
dfs1(nxt, cur);
142
siz[cur] += siz[nxt];
143
if (siz[nxt] > maxsize) {
144
maxsize = siz[nxt];
145
son[cur] = nxt;
146
}
147
}
148
}
149
150
void dfs2(int cur, int tp)
151
{
152
dfn[cur] = ++tim;
153
w[tim] = v[cur];
154
top[cur] = tp;
155
if (not son[cur]) return;
156
dfs2(son[cur], tp);
157
for (int i = head[cur]; compl i; i = edges[i].nxt) {
158
int nxt = edges[i].to;
159
if (nxt not_eq fa[cur] and nxt not_eq son[cur]) {
160
dfs2(nxt, nxt);
161
}
162
}
163
}
164
165
void update_chain(int u, int v, int val)
166
{
167
val %= mod;
168
while (top[u] not_eq top[v]) {
169
if (dep[top[u]] < dep[top[v]]) {
170
swap(u, v);
171
}
172
update(1, dfn[top[u]], dfn[u], val);
173
u = fa[top[u]];
174
}
175
if (dep[u] > dep[v]) {
176
swap(u, v);
177
}
178
update(1, dfn[u], dfn[v], val);
179
}
180
181
int query_chain(int u, int v)
182
{
183
int res = 0;
184
while (top[u] not_eq top[v]) {
185
if (dep[top[u]] < dep[top[v]]) {
186
swap(u, v);
187
}
188
res += query(1, dfn[top[u]], dfn[u]);
189
u = fa[top[u]];
190
}
191
if (dep[u] > dep[v]) {
192
swap(u, v);
193
}
194
res += query(1, dfn[u], dfn[v]);
195
return res % mod;
196
}
197
198
inline void update_son(int cur, int val)
199
{
200
update(1, dfn[cur], dfn[cur] + siz[cur] - 1, val);
201
}
202
203
inline int query_son(int cur)
204
{
205
return query(1, dfn[cur], dfn[cur] + siz[cur] - 1);
206
}
207
208
int main()
209
{
210
#ifndef ONLINE_JUDGE
211
freopen("input.txt", "r", stdin);
212
#endif
213
memset(head, -1, sizeof head);
214
int n = read(), m = read(), r = read();
215
mod = read();
216
for (int i = 1; i <= n; ++i) {
217
v[i] = read();
218
}
219
for (int i = 1; i <= n - 1; ++i) {
220
int u = read(), v = read();
221
addEdge(u, v);
222
addEdge(v, u);
223
}
224
dfs1(r, r);
225
dfs2(r, r);
226
build(1, 1, n);
227
while (m--) {
228
int op = read();
229
if (op == 1) {
230
int x = read(), y = read(), z = read();
231
update_chain(x, y, z);
232
} else if (op == 2) {
233
int x = read(), y = read();
234
write(query_chain(x, y), true);
235
} else if (op == 3) {
236
int x = read(), z = read();
237
update_son(x, z);
238
} else {
239
int x = read();
240
write(query_son(x), true);
241
}
242
}
243
return 0;
244
}
Copied!
最近更新 1yr ago
复制链接