树链剖分求调

#include<bits/stdc++.h>
using namespace std;
const double pi=3.14;
const int inf=0x3f3f3f3f;
const int NIL=-1;
const int MAXN=1e5+7; 
int MOD;
int n,m,root;
struct Edge{
	int lst,v;
	Edge(){}
	Edge(int llst,int vv){
		lst=llst,v=vv;
	}
}E[MAXN*2];
int head[MAXN*2],tot;
void add(int u,int v){
	E[++tot]=Edge(head[u],v);
	head[u]=tot;
}
int c[MAXN],siz[MAXN],hson[MAXN];
bool ifh[MAXN];
void DFS1(int s,int faa){//统计节点个数并标记重儿子
	siz[s]=1;
	int maxx=0,heav=-1;
	for (int i=head[s];~i;i=E[i].lst){
		int v=E[i].v;
		if (v==faa) continue;
		DFS1(v,s);
		siz[s]+=siz[v];
		if (siz[v]>maxx){
			maxx=siz[v];
			heav=v;
		}
	}
	hson[s]=heav;
	ifh[heav]=1;
}
int times=0;
int top[MAXN],dep[MAXN],fa[MAXN],end[MAXN],dfn[MAXN];
void DFS2(int s,int faa){//处理 DFS 序，prepare in order to build segment tree
	dfn[s]=++times;
	dep[s]=dep[faa]+1;
	fa[s]=faa;
	if (s==root){
		top[s]=s;
	}else if (ifh[faa]&&ifh[s]){
		top[s]=top[faa];
	}else if (!ifh[faa]&&ifh[s]){
		top[s]=s;
	}else if (!ifh[s]){
		top[s]=s;
	}
	if (hson[s]!=-1) DFS2(hson[s],s);
	for (int i=head[s];~i;i=E[i].lst){
		int v=E[i].v;
		if (v==faa||v==hson[s]) continue;
		DFS2(v,s);
	}
	end[s]=times;
}
int T[MAXN],lazy[MAXN],len[MAXN]; 
void pushup(int x){
	T[x]=(T[x*2]%MOD+T[x*2+1]%MOD)%MOD; 
}
void pushdown(int x){
	if (lazy[x]){
		T[x*2]+=lazy[x]*len[x*2];
		T[x*2+1]+=lazy[x]*len[x*2+1];
		lazy[x*2]=lazy[x];
		lazy[x*2+1]=lazy[x];
		lazy[x]=0;
	}
}
void build(int l,int r,int x){
	len[x]=(r-l+1);
	if (l==r){
		T[x]=c[l];
		lazy[x]=0;
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,x*2);
	build(mid+1,r,x*2+1);
	pushup(x);
}
int query(int l,int r,int ll,int rr,int x){
	if (l>=ll&&r<=rr){
		return T[x]%MOD;
	}
	pushdown(x);
	int mid=(l+r)>>1;
	if (mid<ll) return query(mid+1,r,ll,rr,x*2+1)%MOD;
	else if (rr<=mid) return query(l,mid,ll,rr,x*2)%MOD;
	else{
		return (query(l,mid,ll,rr,x*2)%MOD+query(mid+1,r,ll,rr,x*2+1)%MOD)%MOD;
	}
}
void update(int l,int r,int ll,int rr,int v,int x){
	if (l>=ll&&r<=rr){
		T[x]=(T[x]%MOD+v*len[x]%MOD)%MOD;
		lazy[x]=(lazy[x]%MOD+v%MOD)%MOD;
		return;
	}
	pushdown(x);
	int mid=(l+r)>>1;
	if (mid<ll) update(mid+1,r,ll,rr,v,x*2+1);
	else if (rr<=mid) update(l,mid,ll,rr,v,x*2);
	else{
		update(l,mid,ll,rr,v,x*2);
		update(mid+1,r,ll,rr,v,x*2+1);
	}
	pushup(x);
}
int QTree(int x,int y){
	int ans=0;
	int fx=top[x],fy=top[y];
	while(fx!=fy){
		if(dep[fx]>=dep[fy]){
			ans=(ans%MOD+query(1,n,dfn[fx],dfn[x],1)%MOD)%MOD;
			x=fa[fx];fx=top[x];
			
		}else{
			ans=(ans%MOD+query(1,n,dfn[fy],dfn[y],1)%MOD)%MOD;
			y=fa[fy];fy=top[y];
		} 
	}
	if (dfn[x]<dfn[y]){
		ans=(ans%MOD+query(1,n,dfn[x],dfn[y],1)%MOD);
	}else{
		ans=(ans%MOD+query(1,n,dfn[y],dfn[x],1)%MOD);
	}
	return ans%MOD;
}
void UTree(int x,int y,int z){
	int fx=top[x],fy=top[y];
	while(fx!=fy){
		if (dep[fx]>=dep[fy]){
			update(1,n,dfn[fx],dfn[x],z,1);
			x=fa[fx];fx=top[x];
		}else{
			update(1,n,dfn[fy],dfn[y],z,1);
			y=fa[fy];fy=top[y];
		} 
	}
	if (dfn[x]<dfn[y]){
		update(1,n,dfn[x],dfn[y],z,1);
	}else{
		update(1,n,dfn[y],dfn[x],z,1);
	}
}
int read()
{
    int ans=0,flag=1;
    char ch=getchar();
    while( (ch>'9' || ch<'0') && ch!='-' ) ch=getchar();
    if(ch=='-') flag=-1,ch=getchar();
    while(ch>='0' && ch<='9') ans=ans*10+ch-'0',ch=getchar();
    return ans*flag;
}
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=read(),m=read(),root=read(),MOD=read();
	memset(head,-1,sizeof(head));
	for (int i=1;i<=n;i++){
		c[i]=read();
	}
	for (int i=1;i<n;i++){
		int u=read(),v=read();
		add(u,v);add(v,u);
	}
	DFS1(root,-1);
	ifh[root]=1;
	DFS2(root,-1);
	build(1,n,1);
	for (int i=1;i<=m;i++){
		int opt=read();
		if (opt==1){
			int x=read(),y=read(),z=read();
			UTree(x,y,z);
		}else if (opt==2){
			int x=read(),y=read();
			cout<<QTree(x,y)<<endl;
		}else if (opt==3){
			int x=read(),y=read();
			UTree(dfn[x],end[x],y);
		}else{
			int x=read();
			cout<<QTree(dfn[x],end[x])<<endl;
		}
		cout<<endl;
	}
}