P3384 【模板】轻重链剖分

#include <bits/stdc++.h>
#define de cout<<"$#^%%#@$*^%$^@#^&%$^$#^#$"<<endl
using namespace std;
const int mn=1e5+7;
int w[mn],p;
int tt=0,fr[mn],nx[2*mn],to[2*mn];
int tot=0,siz[mn],son[mn],fa[mn],dep[mn];
int pos[mn],val[4*mn],top[mn];
int tree[4*mn],lz[4*mn];
void add(int x,int y)
{
	++tt;
	nx[tt]=fr[x];
	fr[x]=tt;
	to[tt]=y;
}
void dfs1(int x,int f)
{
	fa[x]=f;
	dep[x]=dep[f]+1;
	siz[x]=1;
	int k=0,mx=-1;
	for(int i=fr[x];i;i=nx[i])
	{
		int y=to[i];
		if(y==f)  continue;
		dfs1(y,x);
		siz[x]+=siz[y];
		if(mx<siz[y])
		{
			mx=siz[y];
			k=y;
		}
	}
	son[x]=k;
}
void dfs2(int x)
{
	if(son[x])
	{
		++tot;
		pos[son[x]]=tot;
		val[tot]=son[x];
		top[son[x]]=top[x];
		dfs2(son[x]);
	}
	for(int i=fr[x];i;i=nx[i])
	{
		int y=to[i];
		if(top[y])  continue;
		++tot;
		pos[y]=tot;
		val[tot]=y;
		top[y]=y;
		dfs2(y);
	}
}
void build(int k,int l,int r)
{
	if(l==r)
	{
		tree[k]=w[val[l]]%p;
		return ;
	}
	int m=(l+r)>>1;
	build(k<<1,l,m);
	build(k<<1|1,m+1,r);
	tree[k]=tree[k<<1]+tree[k*2+1];
	tree[k]%=p;
}
void down(int x,int l,int r)
{
	if(!lz[x])  return ;
	int m=(l+r)>>1;
	tree[x*2]+=lz[x]*(m-l+1);
	tree[x*2+1]+=lz[x]*(r-m);
	lz[x*2]+=lz[x];
	lz[x*2+1]+=lz[x];
	lz[x]=0;
}
void upd(int k,int l,int r,int x,int y,int v)
{
	if(x>r||y<l)  return ;
	if(l>=x&&r<=y)
	{
		lz[k]+=v;
		tree[k]+=v*(r-l+1);
		return ;
	}
	down(k,l,r);
	int m=(l+r)>>1;
	if(x<=m)  upd(k*2,l,m,x,y,v);
	if(y>m)  upd(k*2+1,m+1,r,x,y,v);
	tree[k]=tree[k*2]+tree[k*2+1];
	tree[k]%=p;
}
int sum(int k,int l,int r,int x,int y)
{
	if(x>r||y<l) return 0;
	if(l>=x&&r<=y)
	  return tree[k]%p;
	down(k,l,r);
	int m=(l+r)>>1;
	int ans=0;
	if(x<=m)  ans=sum(k*2,l,m,x,y);
	if(y>m)  ans+=sum(k*2+1,m+1,r,x,y)%p;
	return ans%p;
}
void change(int x,int y,int v)
{
	v%=p;
	int fx=top[x],fy=top[y];
	while(fx!=fy)
	{
		if(dep[fx]<dep[fy])  swap(x,y),swap(fx,fy);
		//cout<<x<<" "<<y<<" "<<fx<<" "<<fy<<"----------------"<<endl;
		upd(1,1,tot,pos[fx],pos[x],v);
		x=fa[fx];fx=top[x];
	}
	if(dep[x]>dep[y])  swap(x,y);
	upd(1,1,tot,pos[x],pos[y],v);
}
int order2(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+=sum(1,1,tot,pos[fx],pos[x]);
		ans%=p;
		x=fa[fx];fx=top[x];
	}
	if(dep[x]>dep[y])  swap(x,y);
	ans+=sum(1,1,tot,pos[x],pos[y]);
	return ans%p;
}
int main()
{
	int n,m,r;
	cin>>n>>m>>r>>p;
	for(int i=1;i<=n;++i)
	  scanf("%d",&w[i]);
	for(int i=1;i<n;++i)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	dfs1(r,0);
	tot=pos[r]=1;
	val[1]=top[r]=r;
	dfs2(r);
	build(1,1,tot);
	for(int i=1;i<=m;++i)
	{
		//cout<<"                        "<<i<<endl;
		int op;
		scanf("%d",&op);
		switch(op)
		{
		  case 1:
		    {
			  	int x,y,v;
			  	scanf("%d%d%d",&x,&y,&v);
			  	change(x,y,v);
				break;
		    }
		  case 2:
		  	{
		  		int x,y;
		  		scanf("%d%d",&x,&y);
		  		printf("%d
",order2(x,y)%p);
		  		break;
			}
		  case 3:
		  	{
		  		int x,v;
		  		scanf("%d%d",&x,&v);
		  		upd(1,1,tot,pos[x],pos[x]+siz[x]-1,v);
				break;	
			}
		  case 4:
		  	{
		  		int x;
		  		scanf("%d",&x);
		  		printf("%d
",sum(1,1,tot,pos[x],pos[x]+siz[x]-1)%p);
		  		break;
			}
		}
	}
	return 0;
}