提交记录

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
const int N=1e5+20,MAXX=0x3f3f3f3f;
inline ll read()
{
	char ch=getchar();
	ll s=0,w=1;
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
	return s*w;
}
int n,m,vis[N],now[N],a[N],son[N],scnt[N],lh[N],id[N],f[N],deg[N],cnt,top[N];
int mark[N*4];
vector<int> ma[N];
struct edge{
	int l,r,sum;
}tr[N*4];
void pushdown(int k)
{
	if(!mark[k]) return;
	tr[k<<1].sum+=mark[k]*(tr[k<<1].r-tr[k<<1].l+1);
	tr[k<<1|1].sum+=mark[k]*(tr[k<<1|1].r-tr[k<<1|1].l+1);
	mark[k<<1]+=mark[k];
	mark[k<<1|1]+=mark[k];
	mark[k]=0;
}
void build(int k,int l,int r)
{
	tr[k].l=l,tr[k].r=r;
	if(l==r) return void(tr[k].sum=lh[l]);
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum;
}
void change(int k,int l,int r,int pos)
{
//	cout << pos << ' ' << l << ' ' << r << ' ' <<tr[k].l << ' ' << tr[k].r << ' ' << tr[k].sum << endl;
	if(l<=tr[k].l&&tr[k].r<=r)
	{
		tr[k].sum+=pos*(r-l+1);
		mark[k]+=pos;
		return;
	}
	pushdown(k);
	int mid=(tr[k].l+tr[k].r)>>1;
	if(l<=mid) change(k<<1,l,r,pos);
	if(mid<r) change(k<<1|1,l,r,pos);
	tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum;
}
int query(int k,int l,int r)
{
	cout << k << ' ' << tr[k].l << ' ' << tr[k].r << ' ' << tr[k].sum << endl;
	if(l<=tr[k].l&&tr[k].r<=r)	return tr[k].sum;
	pushdown(k); 
	int ans=0, mid=(tr[k].l+tr[k].r)>>1;
	if(l<=mid) ans+=query(k<<1,l,r);
	if(mid<r) ans+=query(k<<1|1,l,r);
	return ans;
}

void dfs1(int u,int fa)
{
	f[u]=fa;
	deg[u]=deg[fa]+1;
	scnt[u]=1;
	for(int i=0;i<ma[u].size();i++)
	{
		if(ma[u][i]==fa) continue;
		dfs1(ma[u][i],u);
		if(scnt[son[u]]<=scnt[ma[u][i]]) son[u]=ma[u][i];
		scnt[u]+=scnt[ma[u][i]];
	}
}
void dfs2(int u,int fa,int ftop)
{
//	cout << u << ' ' << cnt <<endl; 
	id[u]=++cnt;
	top[u]=ftop;
	lh[cnt]=a[u];
	if(!son[u]) return;
	dfs2(son[u],u,ftop);
	for(int i=0;i<ma[u].size();i++)
	{
		if(ma[u][i]==fa||ma[u][i]==son[u])continue;
		dfs2(ma[u][i],u,ma[u][i]);
	}
}
int cl2(int x,int y)
{
	int res=0;
	while(top[x]!=top[y])
	{
		if(deg[top[x]]<deg[top[y]]) swap(x,y);
		res+=query(1,id[top[x]],id[x]);
		x=f[top[x]];
	}
	if(deg[x]>deg[y]) swap(x,y);
	res+=query(1,id[x],id[y]);
	return res;
}
void cl1(int x,int y,int z)
{
	int res=0;
	while(top[x]!=top[y])
	{
		if(deg[top[x]]<deg[top[y]]) swap(x,y);
		change(1,id[top[x]],id[x],z);
		x=f[top[x]];
	}
	if(deg[x]>deg[y]) swap(x,y);
	change(1,id[x],id[y],z);
}
int main()
{
	int r,p;
	cin >> n >> m >> r >> p;
	for(int i=1;i<=n;i++) cin >> a[i];
	for(int i=1;i<n;i++)
	{
		int x,y;
		cin >> x >> y;
		ma[x].push_back(y);
		ma[y].push_back(x);
	} 
	dfs1(r,0);
	dfs2(r,0,r);
	build(1,1,n);
	for(int i=1;i<=n;i++) cout << lh[i] << ' ';
	cout <<endl;
	for(int i=1;i<=n;i++) cout << id[i] << ' ';
	cout <<endl;
	while(m--)
	{
		int op,x,y,z;
		cin >> op;
		if(op==1)
		{
			cin >> x >> y >> z;
			cl1(x,y,z);
		}
		else if(op==2)
		{
			cin >> x >> y;
			cout << cl2(x,y)%p << endl;
		}
		else if(op==3)
		{
			cin >> x >> y;
//			cout << id[x] << ' ' << id[x]+scnt[x]-1 << endl;
			change(1,id[x],id[x]+scnt[x]-1,y);
		}
		else if(op==4)
		{
			cin >> x;
//			cout << id[x] << ' ' << id[x]+scnt[x]-1 << endl;
			cout << query(1,id[x],id[x]+scnt[x]-1)%p << endl;
		}
	}
	return 0;
}
/*
5 5 2 2224
7 3 7 8 0 
1 2
1 5
3 1
4 1
1 2 5 3
4 1
3 1 5
2 1 4
*/