37分求条

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,r,p,father[100005],SIZE[100005],son[100005],top[100005],deep[100005],c[100005],id[100005],dfscnt,HASH[100005];
struct node{
	int sum,lazy;
}tree[400005];
vector<int>e[100005];
void dfs_1(int u,int fa){
	SIZE[u]=1;
	id[u]=++dfscnt;
	HASH[dfscnt]=u;
	father[u]=fa;
	deep[u]=deep[fa]+1;
	for(size_t i=0;i<e[u].size();i++){
		int v=e[u][i];
		if(v==fa)continue;
		dfs_1(v,u);
		SIZE[u]+=SIZE[v];
		if(SIZE[v]>SIZE[son[u]])
		son[u]=v;
	}
}
void dfs_2(int u,int topx){
	top[u]=topx;
	if(SIZE[u]==1)return;
	dfs_2(son[u],topx);
	for(size_t i=0;i<e[u].size();i++){
		int v=e[u][i];
		if(v!=father[u]&&v!=son[u])
		dfs_2(v,v);
	}
}
void push_up(int k){
	tree[k].sum=(tree[2*k].sum+tree[2*k+1].sum)%p;
}
void push_down(int l,int r,int k){
	if(!tree[k].lazy)return;
	int mid=(l+r)/2;
	tree[2*k].sum=(tree[2*k].sum+(mid-l+1)*tree[k].lazy)%p;
	tree[2*k].lazy=(tree[2*k].lazy+tree[k].lazy)%p;
	tree[2*k+1].sum=(tree[2*k+1].sum+(r-mid)*tree[k].lazy)%p;
	tree[2*k+1].lazy=(tree[2*k+1].lazy+tree[k].lazy)%p;
	tree[k].lazy=0;
}
void build(int l,int r,int k){
	if(l==r){
		tree[k].sum=c[HASH[l]]%p;
		return;
	}
	int mid=(l+r)/2;
	build(l,mid,2*k);
	build(mid+1,r,2*k+1);
	push_up(k);
}
void add(int L,int R,int x,int l,int r,int k){
	if(L<=l&&r<=R){
		tree[k].sum=(tree[k].sum+(r-l+1)*x)%p;
		tree[k].lazy=(tree[k].lazy+x)%p;
		return;
	}
	push_down(l,r,k);
	int mid=(l+r)/2;
	if(L<=mid)add(L,R,x,l,mid,2*k);
	if(R>=mid+1)add(L,R,x,mid+1,r,2*k+1);
	push_up(k);
}
int find(int L,int R,int l,int r,int k){
	if(L<=l&&r<=R)return tree[k].sum;
	push_down(l,r,k);
	int mid=(l+r)/2,res=0;
	if(L<=mid)res=(res+find(L,R,l,mid,2*k))%p;
	if(R>=mid+1)res=(res+find(L,R,mid+1,r,2*k+1))%p;
	return res;
}
void add_road(int x,int y,int z){
	while(top[x]!=top[y]){
		if(deep[top[x]]<deep[top[y]])swap(x,y);
		add(id[top[x]],id[x],z,1,n,1);
		x=father[top[x]];
	}
	if(deep[x]<deep[y])swap(x,y);
	add(id[y],id[x],z,1,n,1);
}
int find_sum_road(int x,int y){
	int res=0;
	while(top[x]!=top[y]){
		if(deep[top[x]]<deep[top[y]])swap(x,y);
		res=(res+find(id[top[x]],id[x],1,n,1));
		x=father[top[x]];
	}
	if(deep[x]<deep[y])swap(x,y);
	res=(res+find(id[y],id[x],1,n,1))%p;
	return res%p;
}
void add_tree(int x,int z){
	add(id[x],id[x]+SIZE[x]-1,z,1,n,1);
}
int find_sum_tree(int x){
	return find(id[x],id[x]+SIZE[x]-1,1,n,1)%p;
}
signed main(){
	cin>>n>>m>>r>>p;
	for(int i=1;i<=n;i++)cin>>c[i];
	for(int i=1;i<=n-1;i++){
		int u,v;
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs_1(r,r);
	dfs_2(r,r);
	build(1,n,1);
	while(m>0){
		m--;
		int op,x,y,z;
		cin>>op>>x;
		if(op==1){
			cin>>y>>z;
			add_road(x,y,z);
		}
		if(op==2){
			cin>>y;
			cout<<find_sum_road(x,y)%p<<endl;
		}
		if(op==3){
			cin>>z;
			add_tree(x,z);
		}
		if(op==4)
		cout<<find_sum_tree(x)%p<<endl;
	}
	return 0;
}