厌氧

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int n , m , r , mod , tp;
vector<int> q[N];
int fa[N] , dep[N] , sz[N] , son[N] , hd[N] , id[N] , a[N] , tree[N << 2] , tg[N << 2];
void dfs1(int x , int y){
	fa[x] = y;
	dep[x] = dep[y] + 1;
	sz[x] = 1;
	for(int i = 0; i < q[x].size(); i ++){
		int v = q[x][i];
		if(v == y) continue;
		dfs1(v , x);
		sz[x] += sz[v];
		if(sz[v] > sz[son[x]]) son[x] = v; 
	}
	return;
}
void dfs2(int x , int h){
	hd[x] = h;
	id[x] = ++ tp;
	if(son[x] != 0) dfs2(son[x] , h);
	for(int i = 0; i < q[x].size(); i ++){
		int v = q[x][i];
		if(v == son[x] || v == fa[x]) continue;
		dfs2(v , v);
	}
	return;
}
void down(int p , int l , int r){
	if (tg[p]) {
		int mid = l + r >> 1;
		tree[p << 1] = (tree[p << 1] + tg[p] * (mid - l + 1) % mod) % mod;
		tree[p << 1 | 1] = (tree[p << 1 | 1] + tg[p] * (r - mid) % mod) % mod;
		tg[p << 1] = (tg[p << 1] + tg[p]) % mod;
		tg[p << 1 | 1] = (tg[p << 1 | 1] + tg[p]) % mod;
		tg[p] = 0;
	}
}
void update(int p , int l , int r , int x , int y , int z){
	if (x > y) return;
	if(x <= l && r <= y){
		tg[p] += z;
		tree[p] += z * (r - l + 1);
		tree[p] %= mod;
		return ;
	}
	int mid = l + r >> 1;
	down(p, l, r);
	if (mid >= x) update(p << 1 , l , mid , x , y , z);
	if (mid < y) update(p << 1 | 1 , mid + 1 , r , x , y , z);
	tree[p] = (tree[p << 1] + tree[p << 1 | 1]) % mod;
}
int query(int p , int l , int r , int x , int y){
//	if(l > y || r < x) return 0;
	if (x > y) return 0; 
	if(x <= l && r <= y) return tree[p];
    int mid = l + r >> 1;
    int res = 0;
    down(p, l, r);
    if (mid >= x) res = (res + query(p << 1, l, mid, x, y)) % mod;
	if (mid < y) res = (res + query(p << 1 | 1, mid + 1, r, x, y)) % mod; 
    tree[p] = (tree[p << 1] + tree[p << 1 | 1]) % mod;
	return res;
}
int d1(int x , int y){
	int ans = 0;
	while(hd[x] != hd[y]){
		if(dep[hd[x]] < dep[hd[y]]) swap(x , y);
		ans = (ans + query(1 , 1 , n , id[hd[x]], id[x])) % mod;
		x = fa[hd[x]];
	}
	if(dep[x] < dep[y]) swap(x , y);
	ans = (ans + query(1 , 1 , n , id[y] , id[x])) % mod;
	return ans;
}
int d2(int x , int y , int z){
	while(hd[x] != hd[y]){
		if(dep[hd[x]] < dep[hd[y]]) swap(x , y);
		update(1 , 1 , n , id[hd[x]], id[x] , z);
		x = fa[hd[x]];
	}
	if(dep[x] < dep[y]) swap(x , y);
	update(1 , 1 , n , id[y] , id[x] , z);
}
signed main(){
	cin >> n >> m >> r >> mod;
	for(int i = 1; i <= n; i ++)
	    cin >> a[i];
	for(int i = 1; i < n; i ++){
		int x , y;
		cin >> x >> y;
		q[x].push_back(y);
		q[y].push_back(x); 
	}
	dfs1(r , 0);
    dfs2(r , r);
    for(int i = 1; i <= n; i ++)
    	update(1 , 1 , n , id[i] , id[i] , a[i]);
	while(m --){
		int op , x , y , z;
		cin >> op >> x;
		if(op == 1) cin >> y >> z , d2(x , y , z);
	    if(op == 2) cin >> y , cout << d1(x , y) % mod << '\n';
	    if(op == 3) cin >> z , update(1 , 1 , n , id[x] , id[x] + sz[x] - 1 , z); 
	    if(op == 4) cout << query(1 , 1 , n , id[x] , id[x] + sz[x] - 1) % mod << '\n';
	}
	return 0;
}