违规紫衫

求调

线段树似乎没问题

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int n,m,root,mod;
inline int ls(int x){
	return x << 1;
}
inline int rs(int x){
	return x << 1 | 1;
}
struct edge{
	int u,v;
}e[N];
int h[N],tot = 1;
int val[N];
inline void add(int u,int v){
	e[++tot].u = h[u],e[tot].v = v,h[u] = tot;
}
int fa[N],dep[N],son[N],sz[N],top[N],dfn[N],cnt = 0,rk[N];
void dfs1(int p,int f){
	sz[p] = 1,dep[p] = dep[f] + 1;
	fa[p] = f;
	for(int i = h[p];i;i = e[i].u){
		int v = e[i].v;
		if(v == f) continue; 
		dfs1(v,p);
		sz[p] += sz[v];
		if(sz[v] > sz[son[p]]) son[p] = v;
	}
}
void dfs2(int p,int f){
//	printf("p=%d f=%d\n",p,f);
	top[p] = f;
	dfn[p] = ++cnt;
	rk[cnt] = p;
	if(!son[p]) return;
	dfs2(son[p],f);
	for(int i = h[p];i;i = e[i].u){
		int v = e[i].v;
		if(v != son[p] && v != fa[p]) dfs2(v,v);
	}
}
struct node{
	int data;
	int l,r;
	int lazytag;
}tree[N << 2];
inline void pushup(int p){
	tree[p].data = (tree[ls(p)].data + tree[rs(p)].data) % mod;
}
void build(int p,int l,int r){
	tree[p].l = l;
	tree[p].r = r;
	if(l == r){
		tree[p].data = val[rk[l]];
		return;
	}
	int mid = (l + r) >> 1;
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
	tree[p].data = tree[ls(p)].data + tree[rs(p)].data;
}
void pushdown(int p){
	tree[ls(p)].lazytag += tree[p].lazytag;
	tree[ls(p)].data += (tree[ls(p)].r - tree[ls(p)].l + 1) * tree[p].lazytag;
	tree[rs(p)].lazytag += tree[p].lazytag;
	tree[rs(p)].data += (tree[rs(p)].r - tree[rs(p)].l + 1) * tree[p].lazytag;
	tree[p].lazytag = 0;
}
void change(int p,int l,int r,int x){
	if(tree[p].l > r || tree[p].r < l){
		return;
	}
	if(tree[p].l >= l && tree[p].r <= r){
		tree[p].lazytag += x;
		tree[p].data += (tree[p].r - tree[p].l + 1) * x;
		return; 
	}
	if(tree[p].lazytag > 0){
		pushdown(p);
	}
	change(ls(p),l,r,x);
	change(rs(p),l,r,x);
	tree[p].data = tree[ls(p)].data + tree[rs(p)].data; 
}
int query(int p,int l,int r){
	if(tree[p].l > r || tree[p].r < l) return 0;
	if(tree[p].l >= l && tree[p].r <= r) return tree[p].data;
	if(tree[p].lazytag > 0) pushdown(p);
	return query(ls(p),l,r) + query(rs(p),l,r);
}
int sum(int x,int y){
	int ans = 0;
	while(top[x] != top[y]){
		if(dep[top[x]] < dep[top[y]]) swap(x,y);
		ans = (ans + query(1,dfn[top[x]],dfn[x])) % mod;
		x = fa[top[x]];
	}
	if(dfn[x] > dfn[y]) swap(x,y);
	return (ans + query(1,dfn[x],dfn[y])) % mod;
}
void update(int x,int y,int k){
	while(top[x] != top[y]){
		if(dep[top[x]] < dep[top[y]]) swap(x,y);
		change(1,dfn[top[x]],dfn[x],k);
		x = fa[top[x]];
	}
	if(dfn[x] > dfn[y]) swap(x,y);
	change(1,dfn[x],dfn[y],k);
}
//void Debug(int k){
//	for(int i = 1;i <= n - 1;i++){
//		cout << i << "_" << tree[i].data << "_" << tree[i].tag << "_" << k << " " << ls(i) << "_" << tree[ls(i)].data << "_" << tree[i].tag << "_" << k << "\n";
//		cout << i << "_" << tree[i].data << "_" << tree[i].tag << "_" << k << " " << rs(i) << "_" << tree[rs(i)].data << "_" << tree[i].tag << "_" << k << "\n";
//	} 
//}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	cin >> n >> m >> root >> mod;
	for(int i = 1;i <= n;i++) cin >> val[i];
	for(int i = 1;i < m;i++){
		int u,v;cin >> u >> v;
		add(u,v),add(v,u);
	}
	
	dfs1(root,0);dfs2(root,root);
//	for(int i = 1;i <= n;i++){
//		cout << dfn[i] << " " << dep[i] << " " << son[i] << " " << rk[i] << " " << top[i] << '\n'; 
//	}
	build(1,1,n);
	for(int i = 1;i <= m;i++){
		int opt;
		cin >> opt;
		if(opt == 1){
			int x,y,z;
			cin >> x >> y >> z;update(x,y,z);
		}else if(opt == 2){
			int x,y;
			cin >> x >> y;
			cout << sum(x,y) % mod<< '\n';
		}else if(opt == 3){
			int x,y;
			cin >> x >> y;
			change(1,dfn[x],dfn[x] + sz[x] - 1,y);
		}else if(opt == 4){
			int x;
			cin >> x;
			cout << query(1,dfn[x],dfn[x] + sz[x] - 1) % mod << '\n';
		}
//		Debug(i);
	}
	
}