树链剖分

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,r,p;
struct node{
	int to,nxt;
}e[N];
int w[N];
int h[N];
int tot=0;
void _add(int u,int v)
{
	tot++;
	e[tot].to=v;
	e[tot].nxt=h[u];
	h[u]=tot;
}//建边

int dep[N],siz[N],fa[N],son[N];
void dfs1(int u,int f)//当前节点u，其父节点f
{
	dep[u]=dep[f]+1;//深度
	fa[u]=f;//父节点标记
	siz[u]=1;//子树个数
	int mx=-1;
	for(int i=h[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==f)//是父节点就跳
		{
			continue;
		}
		dfs1(v,u);//便利下去
		siz[u]+=siz[v];//子树和
		if(siz[v]>mx)//重链剖分，子树最大的为重边
		{
			mx=siz[v];
			son[u]=v;
		}
	}
	return;
}

int id[N],wt[N],top[N];
int cnt=0;
void dfs2(int u,int tp)
{
	id[u]=++cnt;//给点标号
	wt[cnt]=w[u];//点权转移
	top[u]=tp;//top记录链顶
	if(!son[u])//没有子节点就结束
	{
		return;
	}
	dfs2(son[u],tp);//同一条链最顶端的点不变
	for(int i=h[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa[u]||v==son[u])//特判
		{
			continue;
		}
		dfs2(v,v);//遍历所有链
	}
	return;
}

int a[N*2],laz[N*2];
int res=0;
void pushdown(int rt,int lenn)//懒标记下放
{
	laz[rt<<1]+=laz[rt];
	laz[rt<<1|1]+=laz[rt];
	a[rt<<1]+=laz[rt]*(lenn-(lenn>>1));
	a[rt<<1|1]+=laz[rt]*(lenn>>1);
	a[rt<<1]%=p;
	a[rt<<1|1]%=p;
	laz[rt]=0;
	return ;
}
void build(int rt,int l,int r)//节点编号rt，区间[l,r]
{
	if(l==r)//单节点
	{
		a[rt]=wt[l];//赋值
		if(a[rt]>p)//取模
		{
			a[rt]%=p;
		}
		return ;
	}
	int mid=(l+r)>>1;//常识，不解释
	build(rt<<1,l,mid);//左
	build(rt<<1|1,mid+1,r);//右
	a[rt]=(a[rt<<1]+a[rt<<1|1])%p;//求和
}
void query(int rt,int l,int r,int lx,int rx)//懒得解释了......
{
	if(lx<=l&&r<=rx)
	{
		res+=a[rt];
		res%=p;
		return ;
	}else{
		if(laz[rt])
		{
			pushdown(rt,r-l+1);
		}
		int mid=(l+r)>>1;
		if(lx<=mid)
		{
			query(rt<<1,l,mid,lx,rx);
		}
		if(rx>mid)
		{
			query(rt<<1|1,mid+1,r,lx,rx);
		}
	}
	return;
}
void update(int rt,int l,int r,int lx,int rx,int k)
{
	if(lx<=l&&r<=rx)//区间内就区间加
	{
		laz[rt]+=k;//懒标记
		a[rt]+=(r-l+1)*k;//区间多少个就要加多少个K
	}else{
		if(laz[rt])//懒标记释放
		{
			pushdown(rt,r-l+1);
		}
		//后面是线段树常规知识，不解释
		int mid=(l+r)>>1;
		if(lx<=mid)
		{
			update(rt<<1,l,mid,lx,rx,k);
		}
		if(rx>mid)
		{
			update(rt<<1|1,mid+1,r,lx,rx,k);
		}
		a[rt]=(a[rt<<1]+a[rt<<1|1])%p;
	}
	return;
}

int qrange(int x,int y)
{
	int ans=0;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])
		{
			swap(x,y);
		}
		res=0;
		query(1,1,n,id[top[x]],id[x]);
		ans+=res;//求和
		ans%=p;
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])
	{
		swap(x,y);
	}
	res=0;
	query(1,1,n,id[x],id[y]);
	ans+=res;
	return ans%p;//取模
}
void updrange(int x,int y,int k)
{
	k%=p;//取模
	while(top[x]!=top[y])//不在同一条链
	{
		if(dep[top[x]]<dep[top[y]])//确保深度上x在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 qrson(int x)
{
	res=0;
	query(1,1,n,id[x],id[x]+siz[x]-1);//树链剖分下来，所有的子树链一定是连续的。
	return res;
}
void updson(int x,int k)
{
	update(1,1,n,id[x],id[x]+siz[x]-1,k);//同上
	return;
}

int main()
{
	scanf("%d%d%d%d",&n,&m,&r,&p);//输入
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&w[i]);//点权
	}
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);//建边
		_add(u,v);
		_add(v,u);
	}
	dfs1(r,0);//dfs序
	dfs2(r,r);//求每条链顶点 
	build(1,1,n);//线段树建树
	while(m--)
	{
		int op,x,y,z;
		scanf("%d",&op);
		if(op==1)//表示将树从 x 到 y 结点最短路径上所有节点的值都加上 z。
		{
			scanf("%d%d%d",&x,&y,&z);//输入
			updrange(x,y,z);
		}else if(op==2){//表示求树从 x 到 y 结点最短路径上所有节点的值之和。
			scanf("%d%d",&x,&y);
			printf("%d\n",qrange(x,y));
		}else if(op==3){//表示将以 x 为根节点的子树内所有节点值都加上 z。
			scanf("%d%d",&x,&y);
			updson(x,y);
		}else{//表示求以 x 为根节点的子树内所有节点值之和
			scanf("%d",&x);
			printf("%d\n",qrson(x));
		}
	}
    return 0;
}