救命！

P3384 30分

蒟蒻第一次学树剖，求各位大佬帮忙改改QAQ

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+10;

struct edge
{
	int v;
	int next;
}e[N];

struct tree
{
	int dat,lazy;
}t[N<<2];

int n,m,r,mod;
int a[N],b[N];
int head[N];
int son[N],id[N],fa[N],dis[N],size[N],top[N];
int tot;
int cnt;

inline void add(int u,int v)
{
	e[++tot].v=v;
	e[tot].next=head[u];
	head[u]=tot;
}

inline void pushup(int p)
{
	t[p].dat=t[p<<1].dat+t[p<<1|1].dat;
	t[p].dat%=mod;
}

inline void pushdown(int p,int l)
{
	if(t[p].lazy)
	{
		t[p<<1].lazy+=t[p].lazy;
		t[p<<1|1].lazy+=t[p].lazy;
		t[p<<1].dat+=t[p].lazy*(l-(l>>1));
		t[p<<1|1].dat+=t[p].lazy*(l>>1);
		t[p<<1].dat%=mod;
		t[p<<1|1].dat%=mod;
		t[p].lazy=0;
	}
}

inline void build(int l,int r,int p)
{
	if(l==r)
	{
		t[p].dat=b[l];
		t[p].dat%=mod;
		return ;
	}
	int mid=(l+r)>>1;
	build(l,mid,p<<1);
	build(mid+1,r,p<<1|1);
	pushup(p);
}

inline int query(int p,int l,int r,int L,int R)
{
	if(L<=l&&r<=R)
	{
		return t[p].dat%mod;
	}
	int ans=0;
	pushdown(p,r-l+1);
	int mid=(l+r)>>1;
	if(L<=mid) ans+=query(p<<1,l,mid,L,R);
	if(mid<R) ans+=query(p<<1|1,mid+1,r,L,R);
	return ans;
}

inline void update(int p,int l,int r,int L,int R,int k)
{
	if(L<=l&&r<=R)
	{
		t[p].lazy+=k;
		t[p].dat+=k*(r-l+1);
		return ;
	}
	pushdown(p,r-l+1);
	int mid=(l+r)>>1;
	if(L<=mid) update(p<<1,l,mid,L,R,k);
	if(mid<R) update(p<<1|1,mid+1,r,L,R,k);
	pushup(p);
}

inline int query2(int x,int y)
{
	int ans=0;
	while(top[x]!=top[y])
	{
		if(dis[top[x]]<dis[top[y]]) swap(x,y);
		ans+=query(1,1,n,id[top[x]],id[x]);
		x=fa[top[x]];
	}
	if(dis[x]>dis[y]) swap(x,y);
	ans+=query(1,1,n,id[x],id[y]);
	return ans%mod;
}

inline void update2(int x,int y,int k)
{
	k%=mod;
	while(top[x]!=top[y])
	{
		if(dis[top[x]]<dis[top[y]]) swap(x,y);
		update(1,1,n,id[top[x]],id[x],k);
		x=fa[top[x]];
	}
	if(dis[x]>dis[y]) swap(x,y);
	update(1,1,n,id[x],id[y],k);
}

inline int query_son(int x)
{
	return query(1,1,n,id[x],id[x]+size[x]-1);
}

inline void update_son(int x,int k)
{
	update(1,1,n,id[x],id[x]+size[x]-1,k);
}

inline void dfs1(int x,int f,int deep)
{
	dis[x]=deep;
	fa[x]=f;
	size[x]=1;
	int zhongson=-1;
	for(int i=head[x];i;i=e[i].next)
	{
		int v=e[i].v;
		if(v!=f)
		{
			dfs1(v,x,deep+1);
			size[x]+=size[v];
			if(size[v]>zhongson) son[x]=v,zhongson=size[x];
		}
	}
}

inline void dfs2(int x,int topf)
{
	id[x]=++cnt;
	b[cnt]=a[x];
	top[x]=topf;
	if(!son[x]) return ;
	dfs2(son[x],topf);
	for(int i=head[x];i;i=e[i].next)
	{
		int v=e[i].v;
		if(v!=fa[x]&&v!=son[x])
		{
			dfs2(v,v);
		}
	}
}

int main()
{
	scanf("%d%d%d%d",&n,&m,&r,&mod);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&a[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,1);
	dfs2(r,r);
	build(1,n,1);
	while(m--)
	{
		int op,x,y,z;
		scanf("%d",&op);
		switch(op)
		{
			case 1:
				scanf("%d%d%d",&x,&y,&z);
				update2(x,y,z);
				break;
			case 2:
				scanf("%d%d",&x,&y);
				printf("%d\n",query2(x,y));
				break;
			case 3:
				scanf("%d%d",&x,&y);
				update_son(x,y);
				break;
			case 4:
				scanf("%d",&x);
				printf("%d\n",query_son(x));
		}
	}
	return 0;
}