求条 必关!! 五颜六色的评测机

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+100,maxEdges = 1e5+100;
int w[maxn],dep[maxn],father[maxn],siz[maxn],son[maxn],tot,W[maxn],top[maxn],id[maxn],P,n;
long long tree[maxn*4],tag[maxn*4];
struct Edge{
	int nxt,to;
}e[maxEdges*2];
int hd[maxn],idx = 1;
void add(int x,int y){
	e[++idx].nxt = hd[x];
	e[idx].to = y;
	hd[x] = idx;
}
void addtag(int q,int L,int R,int k){
	tag[q] = ((tag[q]+k)%P+P)%P;
	tree[q] = (tree[q]+1LL*(R-L+1)*k%P)%P;
	return ;
}
void push_up(int q){
	tree[q] = (tree[q<<1]+tree[q<<1|1])%P;
	return ;
}
void push_down(int q,int L,int R){
	if(!tag[q])return ;
	int mid = L+R>>1;
	addtag(q>>1,L,mid,tag[q]);
	addtag(q>>1|1,mid+1,R,tag[q]);
	tag[q] = 0;
	return ;
}
void build(int q,int L,int R){
	if(L == R){
		tree[q] = W[L]%P;
		return ;
	}
	int mid = L+R>>1;
	build(q<<1,L,mid);
	build(q<<1|1,mid+1,R);
	push_up(q);
}
int query(int q,int L,int R,int l,int r){
	if(L>=l && R<=r)return tree[q]%P;
	push_down(q,L,R);
	int mid = L+R>>1,res = 0;
	if(l<=mid)res = (res+query(q>>1,L,mid,l,r))%P;
	if(r>mid)res = (res+query(q>>1|1,mid+1,R,l,r))%P;
	return res%P;
}
void update(int q,int L,int R,int l,int r,int k){
	if(L>=l && R<=r){
		addtag(q,L,R,k);
		return ;
	}
	push_down(q,L,R);
	int mid = L+R>>1;
	if(l<=mid)update(q>>1,L,mid,l,r,k);
	if(r>mid)update(q>>1|1,mid+1,R,l,r,k);
	push_up(q);
	return ;
}
void dfs1(int cur,int fa){
	dep[cur] = dep[fa]+1;
	father[cur] = fa;
	siz[cur] = 1;
	int cnt = 0,maxs = 0;
	for(int i = hd[cur];i;i = e[i].nxt){
		int nxt = e[i].to;
		if(nxt == fa)continue;
		cnt++;
		dfs1(nxt,cur);
		siz[cur]+=siz[nxt];
		if(siz[nxt]>maxs){
			son[cur] = nxt;
			maxs = siz[nxt];
		}
	}
	return ;
}
void dfs2(int cur,int topfa){
	id[cur] = ++tot;
	W[tot] = w[cur];
	top[cur] = topfa;
	if(!son[cur])return ;
	dfs2(son[cur],topfa);
	for(int i = hd[cur];i;i = e[i].nxt){
		int nxt = e[i].to;
		if(nxt == father[cur] || nxt == son[cur])continue;
		dfs2(nxt,nxt);
	}
	return ;
}
int QuerySum(int x,int y){
	long long ans = 0;
	while(top[x]!=top[y]){
		if(dep[x]<dep[y])swap(x,y);
		ans = (ans+query(1,1,n,id[top[x]],id[x]))%P;
		x = father[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	ans = (ans+query(1,1,n,id[x],id[y]))%P;
	return ans;
}
int QuerySon(int x){
	return query(1,1,n,id[x],id[x]+siz[x]-1)%P;
}
void UpdateSum(int x,int y,int k){
	while(top[x]!=top[y]){
		if(dep[x]<dep[y])swap(x,y);
		update(1,1,n,id[top[x]],id[x],k);
		x = father[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	update(1,1,n,id[x],id[y],k);
	return ;
}
void UpdateSon(int x,int k){
	update(1,1,n,id[x],id[x]+siz[x]-1,k);
	return ;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int m,root;
	cin>>n>>m>>root>>P;
	for(int i = 1;i<=n;i++){
		cin>>w[i];
		w[i]%=P;
	}
	for(int i = 1,x,y;i<n;i++){
		cin>>x>>y;
		add(x,y),add(y,x);
	}
	dfs1(root,0);
	dfs2(root,root);
	build(1,1,n);
	int op,x,y,z;
	while(m--){
		cin>>op;
		if(op == 1){
			cin>>x>>y>>z;
			z%=P;
			UpdateSum(x,y,z);
		}else if(op == 2){
			cin>>x>>y;
			cout<<QuerySum(x,y)<<'\n';
		}else if(op == 3){
			cin>>x>>z;
			z%=P;
			UpdateSon(x,z);
		}else{
			cin>>x;
			cout<<QuerySon(x)<<'\n';
		}
	}
	return 0;
}