【求助】随机链剖分无法AC此题

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,m,r,mod;
int a[100010];
vector<int>g[100010];
int siz1[100010];
int bson[100010];
int top[100010];
int siz[100010];
int dfn[100010];
int rev_dfn[100010];
int cnt;
int fat[100010];
int dep[100010];
int l_siz[100010];
mt19937 rng(time(0));

void dfs_pre(int x,int fa)
{
	fat[x]=fa;
	siz1[x]=1;
	int tmp=0;
	for(auto it:g[x])
	{
		if(it==fa) continue;
		dfs_pre(it,x);
		tmp+=l_siz[it];
		siz1[x]+=siz1[it];
	}
	if(tmp==0)
	{
		l_siz[x]=1;
		return;
	}
	int tmp1=abs((int)rng())%tmp+1;
	int tmp2=0;
	for(auto it:g[x])
	{
		if(it==fa) continue;
		tmp2+=l_siz[it];
		if(tmp1<=tmp2)
		{
			bson[x]=it;
			break;
		}
	}
	l_siz[x]=1+l_siz[bson[x]];
	return;
}

void dfs(int x,int t)
{
	// cout<<x<<" "<<t<<endl;
	top[x]=t;
	siz[x]=1;
	dfn[x]=++cnt;
	dep[x]=dep[fat[x]]+1;
	rev_dfn[cnt]=x;
	if(!bson[x]) return;
	dfs(bson[x],t);
	for(auto it:g[x])
	{
		if(dfn[it]) continue;
		if(bson[x]==it) continue;
		dfs(it,it);
	}
}


int tree[1600010];
int tag[1600010];

void do_mod(int p)
{
	tree[p]%=mod;
	tag[p]%=mod;
}

void build(int p=1,int l=1,int r=n)
{
	if(l==r)
	{
		tree[p]=a[rev_dfn[l]]%mod;
		return;
	}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	tree[p]=tree[p<<1]+tree[p<<1|1];
	do_mod(p);
}

void pushdown(int p,int l,int r)
{
	if(!tag[p]) return;
	int mid=(l+r)>>1;
	tag[p<<1]+=tag[p],tag[p<<1|1]+=tag[p];
	tree[p<<1]+=(mid-l+1)*tag[p]%mod;
	tree[p<<1|1]+=(r-mid)*tag[p]%mod;
	tag[p]=0;
	do_mod(p<<1),do_mod(p<<1|1);
}

void modify(int lx,int rx,int x,int p=1,int l=1,int r=n)
{
	// cout<<lx<<" "<<rx<<" "<<x<<" "<<p<<" "<<l<<" "<<r<<endl;
	if(lx<=l&&r<=rx)
	{
		tag[p]+=x;
		tree[p]+=(r-l+1)*x%mod;
		do_mod(p);
		return;
	}
	pushdown(p,l,r);
	do_mod(p);
	int mid=(l+r)>>1;
	if(lx<=mid) modify(lx,rx,x,p<<1,l,mid);
	if(rx>mid) modify(lx,rx,x,p<<1|1,mid+1,r);
	tree[p]=tree[p<<1]+tree[p<<1|1];
	do_mod(p);
}

int query(int lx,int rx,int p=1,int l=1,int r=n)
{
	// cout<<lx<<" "<<rx<<" "<<p<<" "<<l<<" "<<r<<endl;
	if(lx<=l&&r<=rx)
		return tree[p]%mod;
	pushdown(p,l,r);
	do_mod(p);
	int mid=(l+r)>>1;
	int ans=0;
	if(lx<=mid) ans+=query(lx,rx,p<<1,l,mid);
	if(rx>mid) ans+=query(lx,rx,p<<1|1,mid+1,r);
	return ans%mod;
}

void modify_path(int x,int y,int z)
{
	if(top[x]==top[y])
	{
		modify(min(dfn[x],dfn[y]),max(dfn[x],dfn[y]),z);
		return;
	}
	int nowx=x,nowy=y;
	while(top[nowx]!=top[nowy])
	{
		if(dep[top[nowx]]<dep[top[nowy]]) swap(nowx,nowy);
		modify(dfn[top[nowx]],dfn[nowx],z);
		nowx=fat[top[nowx]];
	}
	modify(min(dfn[nowx],dfn[nowy]),max(dfn[nowx],dfn[nowy]),z);
}

int query_path(int x,int y)
{
	if(top[x]==top[y])
		return query(min(dfn[x],dfn[y]),max(dfn[x],dfn[y]))%mod;
	int nowx=x,nowy=y;
	int ans=0;
	while(top[nowx]!=top[nowy])
	{
		if(dep[top[nowx]]<dep[top[nowy]]) swap(nowx,nowy);
		// cout<<top[nowx]<<" "<<nowx<<endl;
		ans+=query(dfn[top[nowx]],dfn[nowx]);
		nowx=fat[top[nowx]];
		ans%=mod;
	}
	ans+=query(min(dfn[nowx],dfn[nowy]),max(dfn[nowx],dfn[nowy]));
	ans%=mod;
	return ans;
}

main()
{
	// ifstream cin(".in",ios::in);
	// ofstream cout(".out",ios::out);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);   
	cin>>n>>m>>r>>mod;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs_pre(r,0);
	dfs(r,r);
	for(int i=1;i<=n;i++) siz[i]=siz1[i];
	build();
	// for(int i=1;i<=n;i++) cout<<dfn[i]<<" ";
	// cout<<endl;
	for(int i=1;i<=m;i++)
	{
		int op;
		cin>>op;
		if(op==1)
		{
			int x,y,z;
			cin>>x>>y>>z;
			z%=mod;
			modify_path(x,y,z);
		}
		if(op==2)
		{
			int x,y;
			cin>>x>>y;
			cout<<query_path(x,y)<<"\n";
		}
		if(op==3)
		{
			int x,z;
			cin>>x>>z;
			z%=mod;
			// cout<<siz[x]<<endl;
			modify(dfn[x],dfn[x]+siz[x]-1,z);
		}
		if(op==4)
		{
			int x;
			cin>>x;
			cout<<query(dfn[x],dfn[x]+siz[x]-1)<<"\n";
		}
	}
}
//#include<bits/stdc++.h>
//#define int long long
//using namespace std;
//
//int n,m,r,mod;
//int a[100010];
//vector<int>g[100010];
//int siz1[100010];
//int bson[100010];
//int top[100010];
//int siz[100010];
//int dfn[100010];
//int rev_dfn[100010];
//int cnt;
//int fat[100010];
//int dep[100010];
//
//void dfs_pre(int x,int fa)
//{
//	fat[x]=fa;
//	int tmpmax=0;
//	siz1[x]=1;
//	for(auto it:g[x])
//	{
//		if(it==fa) continue;
//		dfs_pre(it,x);
//		if(siz1[it]>tmpmax)
//		{
//			tmpmax=siz1[it];
//			bson[x]=it;
//		}
//		siz1[x]+=siz1[it];
//	}
//	return;
//}
//
//void dfs(int x,int t)
//{
//	// cout<<x<<" "<<t<<endl;
//	top[x]=t;
//	siz[x]=1;
//	dfn[x]=++cnt;
//	dep[x]=dep[fat[x]]+1;
//	rev_dfn[cnt]=x;
//	if(!bson[x]) return;
//	dfs(bson[x],t);
//	for(auto it:g[x])
//	{
//		if(dfn[it]) continue;
//		if(bson[x]==it) continue;
//		dfs(it,it);
//	}
//}
//
//
//int tree[1600010];
//int tag[1600010];
//
//void do_mod(int p)
//{
//	tree[p]%=mod;
//	tag[p]%=mod;
//}
//
//void build(int p=1,int l=1,int r=n)
//{
//	if(l==r)
//	{
//		tree[p]=a[rev_dfn[l]]%mod;
//		return;
//	}
//	int mid=(l+r)>>1;
//	build(p<<1,l,mid);
//	build(p<<1|1,mid+1,r);
//	tree[p]=tree[p<<1]+tree[p<<1|1];
//	do_mod(p);
//}
//
//void pushdown(int p,int l,int r)
//{
//	if(!tag[p]) return;
//	int mid=(l+r)>>1;
//	tag[p<<1]+=tag[p],tag[p<<1|1]+=tag[p];
//	tree[p<<1]+=(mid-l+1)*tag[p]%mod;
//	tree[p<<1|1]+=(r-mid)*tag[p]%mod;
//	tag[p]=0;
//	do_mod(p<<1),do_mod(p<<1|1);
//}
//
//void modify(int lx,int rx,int x,int p=1,int l=1,int r=n)
//{
//	// cout<<lx<<" "<<rx<<" "<<x<<" "<<p<<" "<<l<<" "<<r<<endl;
//	if(lx<=l&&r<=rx)
//	{
//		tag[p]+=x;
//		tree[p]+=(r-l+1)*x%mod;
//		do_mod(p);
//		return;
//	}
//	pushdown(p,l,r);
//	do_mod(p);
//	int mid=(l+r)>>1;
//	if(lx<=mid) modify(lx,rx,x,p<<1,l,mid);
//	if(rx>mid) modify(lx,rx,x,p<<1|1,mid+1,r);
//	tree[p]=tree[p<<1]+tree[p<<1|1];
//	do_mod(p);
//}
//
//int query(int lx,int rx,int p=1,int l=1,int r=n)
//{
//	// cout<<lx<<" "<<rx<<" "<<p<<" "<<l<<" "<<r<<endl;
//	if(lx<=l&&r<=rx)
//		return tree[p]%mod;
//	pushdown(p,l,r);
//	do_mod(p);
//	int mid=(l+r)>>1;
//	int ans=0;
//	if(lx<=mid) ans+=query(lx,rx,p<<1,l,mid);
//	if(rx>mid) ans+=query(lx,rx,p<<1|1,mid+1,r);
//	return ans%mod;
//}
//
//void modify_path(int x,int y,int z)
//{
//	if(top[x]==top[y])
//	{
//		modify(min(dfn[x],dfn[y]),max(dfn[x],dfn[y]),z);
//		return;
//	}
//	int nowx=x,nowy=y;
//	while(top[nowx]!=top[nowy])
//	{
//		if(dep[top[nowx]]<dep[top[nowy]]) swap(nowx,nowy);
//		modify(dfn[top[nowx]],dfn[nowx],z);
//		nowx=fat[top[nowx]];
//	}
//	modify(min(dfn[nowx],dfn[nowy]),max(dfn[nowx],dfn[nowy]),z);
//}
//
//int query_path(int x,int y)
//{
//	if(top[x]==top[y])
//		return query(min(dfn[x],dfn[y]),max(dfn[x],dfn[y]))%mod;
//	int nowx=x,nowy=y;
//	int ans=0;
//	while(top[nowx]!=top[nowy])
//	{
//		if(dep[top[nowx]]<dep[top[nowy]]) swap(nowx,nowy);
//		// cout<<top[nowx]<<" "<<nowx<<endl;
//		ans+=query(dfn[top[nowx]],dfn[nowx]);
//		nowx=fat[top[nowx]];
//		ans%=mod;
//	}
//	ans+=query(min(dfn[nowx],dfn[nowy]),max(dfn[nowx],dfn[nowy]));
//	ans%=mod;
//	return ans;
//}
//
//
//main()
//{
//	// ifstream cin(".in",ios::in);
//	// ofstream cout(".out",ios::out);
//	ios::sync_with_stdio(false);
//	cin.tie(nullptr);   
//	cin>>n>>m>>r>>mod;
//	for(int i=1;i<=n;i++) cin>>a[i];
//	for(int i=1;i<n;i++)
//	{
//		int x,y;
//		cin>>x>>y;
//		g[x].push_back(y);
//		g[y].push_back(x);
//	}
//	dfs_pre(r,0);
//	dfs(r,r);
//	for(int i=1;i<=n;i++) siz[i]=siz1[i];
//	build();
//	// for(int i=1;i<=n;i++) cout<<dfn[i]<<" ";
//	// cout<<endl;
//	for(int i=1;i<=m;i++)
//	{
//		int op;
//		cin>>op;
//		if(op==1)
//		{
//			int x,y,z;
//			cin>>x>>y>>z;
//			z%=mod;
//			modify_path(x,y,z);
//		}
//		if(op==2)
//		{
//			int x,y;
//			cin>>x>>y;
//			cout<<query_path(x,y)<<"\n";
//		}
//		if(op==3)
//		{
//			int x,z;
//			cin>>x>>z;
//			z%=mod;
//			// cout<<siz[x]<<endl;
//			modify(dfn[x],dfn[x]+siz[x]-1,z);
//		}
//		if(op==4)
//		{
//			int x;
//			cin>>x;
//			cout<<query(dfn[x],dfn[x]+siz[x]-1)<<"\n";
//		}
//	}
//}