37pts 求助

# include <iostream>
# include <cmath>
# include <cstring>
# include <string>
# include <algorithm>
# include <stack>
# include <queue>
# include <vector>
# include <set>
# include <map>
using namespace std;

int n,m,r,p,u,v;

int head[1000005],num=0;
struct pnode {
	int to,next;
}edge[1000005];
void add(int u,int v){
	edge[++num].next=head[u];
	edge[num].to=v;
	head[u]=num;
}

int dep[1000005],fa[1000005],siz[1000005];
int wson[1000005];
void dfs1(int father,int x){
	dep[x]=dep[father]+1;
	fa[x]=father;
	siz[x]=1;
	int mson=-1;
	for(int i=head[x];i;i=edge[i].next){
		if (father==edge[i].to) continue;
		dfs1(x,edge[i].to);
		siz[x]+=siz[edge[i].to];
		if (siz[edge[i].to]>mson) {
			wson[x]=edge[i].to;
			mson=siz[edge[i].to];
		}
	}
}

int cnt=0;
int id[1000005],top[1000005];
int w[1000005],wt[1000005];
void dfs2(int x,int topf){
	id[x]=++cnt;
	wt[cnt]=w[x];
	top[x]=topf;
	if (wson[x]==0) return;
	dfs2(wson[x],topf);
	for (int i=head[x];i;i=edge[i].next){
		if (edge[i].to==fa[x]||edge[i].to==wson[x]) continue;
		dfs2(edge[i].to,edge[i].to);
	}
}

struct node {
	long long val,mark;
}tree[1000005];
void build (int st,int ed,int root){
	if (st==ed){
		tree[root].val=wt[st];
		tree[root].val%=p;
		return ;
	}
	int mid=(st+ed)/2;
	build(st,mid,root*2);
	build(mid+1,ed,root*2+1);
	tree[root].val=(tree[root*2].val+tree[root*2+1].val)%p;
}
void pushdown (int root,int l,int r){
	if (tree[root].mark!=0){
		int mid=(l+r)/2;
		tree[root*2].mark+=tree[root].mark;
		tree[root*2+1].mark+=tree[root].mark;
		tree[root*2].val+=tree[root].mark*(mid-l+1);
		tree[root*2+1].val+=tree[root].mark*(r-mid);
		tree[root*2].val%=p;
		tree[root*2+1].val%=p;
		tree[root].mark=0;
	}
}
long long quary (int root,int st,int ed,int qst,int qed){
	if (qed<st||ed<qst) return 0;
	if (qst<=st&&ed<=qed) return tree[root].val%p;
	pushdown(root,st,ed);
	int mid=(st+ed)/2;
	long long ans=0;
	if (qst<=mid) ans+=quary(root*2,st,mid,qst,qed);
	if (qed>mid) ans+=quary(root*2+1,mid+1,ed,qst,qed);
	return ans;
}
void update (int root,int st,int ed,int qst,int qed,long long val){
	if (qed<st||ed<qst) return ;
	if (qst<=st&&ed<=qed) {
		tree[root].mark+=val;
		tree[root].val+=val*(ed-st+1);
		return ;
	}
	pushdown(root,st,ed);
	int mid=(st+ed)/2;
	if (qst<=mid) update (root*2,st,mid,qst,qed,val);
	if (qed>mid) update (root*2+1,mid+1,ed,qst,qed,val);
	tree[root].val=(tree[root*2].val+tree[root*2+1].val)%p;
}

void update_range (int x,int y,int k){
	k%=p;
	while (top[x]!=top[y]){
		if (dep[top[x]]<dep[top[y]]) swap(x,y);
		update(1,1,n,id[top[x]],id[x],k);
		x=fa[top[x]];
	}
	if (dep[x]>dep[y]) swap(x,y);
	update(1,1,n,id[x],id[y],k);
	return ;
}
int ask_range (int x,int y){
	int ans=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        ans=(ans+quary(1,1,n,id[top[x]],id[x]))%p;
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    return (ans+quary(1,1,n,id[x],id[y]))%p;
}
int ask_son (int x){
    return quary(1,1,n,id[x],id[x]+siz[x]-1);
}
void update_son (int x,int k){
	update(1,1,n,id[x],id[x]+siz[x]-1,k);
}
int main(){
	//freopen("P3384_4.in","r",stdin);
	//freopen("P3384.out","w",stdout);
	ios::sync_with_stdio (false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >>n>>m>>r>>p;
    for (int i=1;i<=n;i++)
    	cin >>w[i];
    for (int i=1;i<n;i++){
		cin >>u>>v;
		add(u,v);
		add(v,u);
	}
	dfs1(0,r);
	dfs2(r,r);
	build(1,n,1);
	for (int i=1;i<=m;i++){
		int opt,x,y,z;
		cin >>opt;
		if (opt==1){
			cin >>x>>y>>z;
			update_range(x,y,z);
		}
		if (opt==2){
			cin >>x>>y;
			cout <<ask_range(x,y)<<endl;
		}
		if (opt==3){
			cin >>x>>y;
			update_son(x,y);
		}
		if (opt==4){
			cin >>x;
			cout <<ask_son(x)<<endl;
		}
	}
    return 0;
}