好久不写树剖了，昨天刚好xry提起，今天洛谷智推又有这题....于是就想写一写.....然后果然出现了很多很多的错误2333
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 200010;
int n, m, r, mod, x, y, z, k;
int num, from[MAXN], next[MAXN], to[MAXN], w[MAXN];
int w1[MAXN], a[MAXN << 2], lazy[MAXN << 2];
int son[MAXN], id[MAXN], father[MAXN];
int cnt;
int depth[MAXN];
int size[MAXN], top[MAXN];
int res;
inline int read() {
char ch; bool f = false; int res = 0;
while (((ch = getchar()) < '0' || ch > '9') && ch != '-');
if (ch == '-') f = true; else res = ch - '0';
while ((ch = getchar()) >= '0' && ch <= '9') res = (res << 3) + (res << 1) + ch - '0';
return f? ~res + 1 : res;
}
inline void add(int x, int y) { // build tree
to[++ num] = y, next[num] = from[x], from[x] = num;
to[++ num] = x, next[num] = from[y], from[y] = num;
}
void dfs1(int x, int fa, int deep) {
depth[x] = deep;
father[x] = fa;
size[x] = 1;
int maxx = -1; // son 's max
for (int i = from[x]; i; i = next[i]) {
int y = to[i];
if (y == fa) // father
continue;
dfs1(y, x, deep + 1);
size[x] += size[y];
if (size[y] > maxx) {
son[x] = y;
maxx = size[y];
}
}
}
void dfs2(int x, int Top) { // tree link top
id[x] = ++ cnt; // new number
w1[cnt] = w[x]; // new value
top[x] = Top;
if (! son[x]) // no son
return;
dfs2(son[x], Top);
for (int i = from[x]; i; i = next[i]) {
int y = to[i];
if (y == father[x] || y == son[x])
continue;
dfs2(y, y); // light son -> link top
}
}
//segment tree
inline void pushdown(int x, int y) {
int t = x << 1, w = x << 1 | 1, z = y >> 1;
lazy[t] += lazy[x], lazy[w] += lazy[x];
a[t] += lazy[x] * (y - z), a[w] += lazy[x] * z;
a[t] %= mod, a[w] %= mod, lazy[x] = 0;
}
void build (int x, int t, int w) {
if (t == w) {
a[x] = w1[t];
if (a[x] > mod)
a[x] %= mod;
return;
}
build(x << 1, t, t + w >> 1); // left son
build(x << 1 | 1, (t + w >> 1) + 1, w); // right son
a[x] = (a[x << 1] + a[x << 1 | 1] % mod);
}
void query(int x, int l, int r, int t, int w) {
if (t <= l && w >= r) {
res = (res + a[x]) % mod;
return;
}
else {
int mid = l + r >> 1;
if (lazy[x])
pushdown(x, r - l + 1);
if (t <= mid)
query(x << 1, l, mid, t, w);
if (w > mid)
query(x << 1 | 1, mid + 1, r, t, w);
}
}
void update(int x, int l, int r, int t, int w, int k) {
if (t <= l && w >= r)
lazy[x] += k, a[x] += k * (r - l + 1);
else {
int mid = l + r >> 1;
if (lazy[x])
pushdown(x, r - l + 1);
if (t <= mid)
update(x << 1, l, mid, t, w, k);
if (w > mid)
update(x << 1 | 1, mid + 1, r, t, w, k);
a[x] = (a[x << 1] + a[x << 1 | 1]) % mod;
}
}
//
inline void addroad(int x, int y, int k) {
k %= mod;
while (top[x] != top[y]) {
if (depth[top[x]] < depth[top[y]])
swap(x, y);
update(1, 1, n, id[top[x]], id[x], k);
x = father[top[x]];
}
if (depth[x] > depth[y])
swap(x, y);
update(1, 1, n, id[x], id[y], k);
}
inline int sumroad(int x, int y) {
int ans = 0;
while (top[x] != top[y]) {
if (depth[top[x]] < depth[top[y]])
swap(x, y);
res = 0;
query(1, 1, n, id[top[x]], id[x]);
ans = (ans + res) % mod;
x = father[top[x]];
}
if (depth[x] > depth[y])
swap(x, y);
res = 0;
query(1, 1, n, id[x], id[y]);
ans = ans + res;
return ans % mod;
}
inline int sumson(int x) {
res = 0;
query(1, 1, n, id[x], id[x] + size[x] - 1);
return res;
}
inline void addson(int x,int k) {
update(1, 1, n, id[x], id[x] + size[x] - 1, k);
}
int main() {
n = read(), m = read(), r = read(), mod = read();
for (int i = 1; i <= n; i ++)
w[i]=read();
for (int i = 1; i < n; i ++)
add(read(), read());
dfs1(r, 0, 1);
dfs2(r, r);
build(1, 1, n);
while (m --) {
k = read(), x = read();
if (k == 1) {
y = read(), z=read();
addroad(x, y, z);
}
else if (k == 2) {
y = read();
printf("%d
", sumroad(x, y));
}
else if (k == 3) {
y = read();
addson(x, y);
}
else printf("%d
", sumson(x));
}
return 0;
}