@[Tangent233](/user/264548) 说实话真的没有看太懂，有兴趣的话可以看一下我的
```cpp
# include <iostream>
# include <cstdio>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
typedef struct {
int x , y , next;
}Edge;
Edge edge[N];
int E = 0 , elast[N];
void add(int x , int y ) {
E ++;
edge[E].x = x;
edge[E].y = y;
edge[E].next = elast[x];
elast[x] = E;
}
int f[N] , dep[N] , son[N] , siz[N];
void dfs1(int x , int fa) {
dep[x] = dep[fa] + 1;
f[x] = fa;
siz[x] = 1;
int maxv = -1;
for (int i = elast[x] ; i ; i = edge[i].next) {
int y = edge[i].y;
if (y != fa) {
dfs1(y , x);
siz[x] += siz[y];
if (siz[y] > maxv) son[x] = y , maxv = siz[y];
}
}
}
int top[N] , id[N] , w[N] , W[N] , Cnt = 0;
int n , m , root , mod;
void dfs2(int x , int Top) {
id[x] = ++ Cnt;
w[Cnt] = W[x];
top[x] = Top;
if (!son[x]) return ;
dfs2(son[x] , Top);
for (int i = elast[x] ; i ; i = edge[i].next) {
int y = edge[i].y;
if (y != f[x] && y != son[x]) dfs2(y , y);
}
}
typedef struct {
int l , r , lazy;
ll sum;
}Node;
Node tr[N];
void pushup(int p) {
tr[p].sum = tr[p << 1].sum + tr[p << 1 | 1].sum;
tr[p].sum %= mod;
}
void pushdown(int p) {
if (tr[p].lazy) {
tr[p << 1].lazy += tr[p].lazy;
tr[p << 1 | 1].lazy += tr[p].lazy;
tr[p << 1].sum += (ll)(tr[p << 1].r - tr[p << 1].l + 1) * (tr[p].lazy);
tr[p << 1 | 1].sum += (ll)(tr[p << 1 | 1].r - tr[p << 1 | 1].l + 1) * (tr[p].lazy);
tr[p << 1].sum %= mod;
tr[p << 1 | 1].sum %= mod;
tr[p].lazy = 0;
}
return ;
}
void modify(int p , int x , int y , int d) {
if (x > y) swap(x , y);
if (x <= tr[p].l && tr[p].r <= y) {
tr[p].lazy += d;
tr[p].sum = (tr[p].sum + (ll)(tr[p].r - tr[p].l + 1) * d % mod) % mod;
return ;
} else {
pushdown(p);
int mid = (tr[p].l + tr[p].r) >> 1;
if (x <= mid) modify(p << 1 , x , y , d);
if (y > mid) modify(p << 1 | 1 , x , y , d);
pushup(p);
}
}
ll query(int p , int x , int y) {
if (x > y) swap(x , y);
if (x <= tr[p].l && tr[p].r <= y) return tr[p].sum % mod;
else {
pushdown(p);
int mid = (tr[p].l + tr[p].r) >> 1;
ll ans = 0;
if (x <= mid) ans += query(p << 1 , x , y);
if (y > mid) ans += query(p << 1 | 1 , x , y);
return ans % mod;
}
}
void build(int p , int x , int y) {
tr[p].l = x;
tr[p].r = y;
if (x == y) {
tr[p].sum = (ll)w[x];
return ;
} else {
int mid = (x + y) >> 1;
build(p << 1 , x , mid) , build(p << 1 | 1 , mid + 1 , y);
pushup(p);
}
}
ll Query(int x , int y) {
ll ans = 0;
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x , y);
ans = (ans + query(1 , id[top[x]] , id[x])) % mod;
x = f[top[x]];
}
if (dep[x] > dep[y]) swap(x , y);
ans = (ans + query(1 , id[x] , id[y])) % mod;
return ans % mod;
}
void Add(int x , int y , int d) {
d %= mod;
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x , y);
modify(1 , id[top[x]] , id[x] , d);
x = f[top[x]];
}
if (dep[x] > dep[y]) swap(x , y);
modify(1 , id[x] , id[y] , d);
}
int main() {
cin >> n >> m >> root >> mod;
for (int i = 1 ; i <= n ; i ++) {
scanf("%d" , &W[i]);
}
for (int i = 1 ; i <= n - 1 ; i ++) {
int x , y;
scanf("%d%d" , &x , &y);
add(x , y) , add(y , x);
}
dfs1(root , 0);
dfs2(root , root);
build(1 , 1 , n);
while (m --) {
int x , y , z , opt;
scanf("%d%d" , &opt , &x);
if (opt == 1) {
scanf("%d%d" , &y , &z);
Add(x , y , z);
}
if (opt == 2) {
scanf("%d" , &y);
printf("%lld\n" , Query(x , y) % mod);
}
if (opt == 3) {
scanf("%d" , &y);
modify(1 , id[x] , id[x] + siz[x] - 1 , y);
}
if (opt == 4) {
printf("%lld\n" , query(1 , id[x] , id[x] + siz[x] - 1) % mod);
}
}
}
```
by ker_xyxyxyx_xxs @ 2021-08-22 14:37:59
@[ker_xyxyxyx_xxs](/user/335477) 主要是因为我是平衡树维护来着（
后面树剖的代码也没看懂吗
by Tangent233 @ 2021-08-22 14:42:13
@[Tangent233](/user/264548) 哦哦哦，那就是了
dfs我感觉没有问题
by ker_xyxyxyx_xxs @ 2021-08-22 14:46:22
@[ker_xyxyxyx_xxs](/user/335477) 平衡树锅了？
by Tangent233 @ 2021-08-22 15:23:05
@[Tangent233](/user/264548) 我不会平衡树，我看起来感觉dfs没问题，也不能保证
by ker_xyxyxyx_xxs @ 2021-08-22 16:15:22