记录详情

题目

#include<bits/stdc++.h>
# define reg register
# define N (10000005)
# define int long long
using namespace std;
struct node{
	int l;
	int r;
	int sum;
	int lazy;
}t[N];
int n,m,r,P;
int num[N];
int head[N],nxt[N],to[N],tot;
int rev[N],seg[N],top[N],fa[N],size[N],son[N],dep[N],sum;
inline int read(){
	char c=getchar();reg int sum=0,f=1;
	while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
	while(c<='9'&&c>='0'){sum=sum*10+c-'0';c=getchar();}
	return sum*f;
}
inline void update(const int &p){
	if(t[p].lazy){
		t[p<<1].lazy=(t[p<<1].lazy+t[p].lazy)%P;
		t[p<<1|1].lazy=(t[p<<1|1].lazy+t[p].lazy)%P;
		t[p<<1].sum+=(t[p<<1].r-t[p<<1].l+1)*t[p].lazy%P;
		t[p<<1|1].sum+=(t[p<<1|1].r-t[p<<1|1].l+1)*t[p].lazy%P;
		t[p].lazy=0;
	}
}
void build(const int &p,const int &l,const int &r){
	t[p].l=l;
	t[p].r=r;
	t[p].sum=0;
	t[p].lazy=0;
	if(l==r){
		t[p].sum=num[rev[l]];
		return;
	}
	reg int mid=l+r>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	t[p].sum=(t[p<<1].sum+t[p<<1|1].sum)%P;
}
void change(const int &p,const int &l,const int &r,const int &k){
	if(t[p].l>=l&&t[p].r<=r){
		t[p].lazy=(t[p].lazy+k)%P;
		t[p].sum=(t[p].sum+(t[p].r-t[p].l+1)*k%P)%P;
		return;
	}
	update(p);
	reg int mid=t[p].l+t[p].r>>1;
	if(mid>=l)change(p<<1,l,r,k);
	if(mid<r)change(p<<1|1,l,r,k);
	t[p].sum=(t[p<<1].sum+t[p<<1|1].sum)%P;
}
int query(const int &p,const int &l,const int &r){
	if(t[p].l>=l&&t[p].r<=r)return t[p].sum;
	update(p);
	reg int mid=t[p].l+t[p].r>>1,ans=0;
	if(mid>=l)ans+=query(p<<1,l,r);
	if(mid<r)ans+=query(p<<1|1,l,r);
	return ans;
}
inline void add(const int &x,const int &y){
	to[++tot]=y;nxt[tot]=head[x];head[x]=tot;
	to[++tot]=x;nxt[tot]=head[y];head[y]=tot;
}
void dfs1(const int &u,const int &f){
	reg int v;
	size[u]=1;
	fa[u]=f;
	dep[u]=dep[f]+1;
	for(reg int i=head[u];i;i=nxt[i]){
		v=to[i];
		if(v==f)continue;
		dfs1(v,u);
		size[u]+=size[v];
		if(size[v]>size[son[u]])
			son[u]=v;
	}
}
void dfs2(const int &u,const int &r){
	reg int v;
	seg[u]=++sum;
	rev[sum]=u;
	top[u]=r;
	if(!son[u])return;
	dfs2(son[u],r);
	for(reg int i=head[u];i;i=nxt[i]){
		v=to[i];
		if(v!=fa[u]&&v!=son[u])
			dfs2(v,v);
	}
}
inline void ask1(int x,int y,int z){
	int fx=top[x],fy=top[y];
	while(fx!=fy){
		if(dep[fx]<dep[fy])swap(x,y),swap(fx,fy);
		change(1,seg[fx],seg[x],z);
		x=fa[fx];fx=top[x];
	}
	if(dep[x]>dep[y])change(1,seg[y],seg[x],z);
	else change(1,seg[x],seg[y],z);
}
inline int ask2(int x,int y){
	int ans=0;
	int fx=top[x],fy=top[y];
	while(fx!=fy){
		if(dep[fx]<dep[fy])swap(x,y),swap(fx,fy);
		ans=(ans+query(1,seg[fx],seg[x]))%P;
		x=fa[fx];fx=top[x];
	}
	if(dep[x]>dep[y])ans=(ans+query(1,seg[y],seg[x]))%P;
	else ans=(ans+query(1,seg[x],seg[y]))%P;
	return ans;
}
inline void ask3(const int &x,const int &z){change(1,seg[x],seg[x]+size[x]-1,z);}
inline int ask4(const int &x){return query(1,seg[x],seg[x]+size[x]-1);}
signed main(){
	reg int i,j,k,x,y,z;
	n=read();m=read();r=read();P=read();
	for(i=1;i<=n;++i)
		num[i]=read();
	for(i=1;i<n;++i){
		x=read();
		y=read();
		add(x,y);
	}
	dfs1(r,0);
	dfs2(r,r);
	build(1,1,n);
	for(i=1;i<=m;++i){
		k=read();
		if(k==1){
			x=read();y=read();z=read();
			ask1(x,y,z);
		}
		if(k==2){
			x=read();y=read();
			printf("%d\n",ask2(x,y));
		}
		if(k==3){
			x=read();z=read();
			ask3(x,z);
		}
		if(k==4){
			x=read();
			printf("%d\n",ask4(x));
		}
	}				
	return 0;
}