树链剖分模板题样例RE，玄关

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#define int long long
#define N 200005
#define lc u<<1
#define rc u<<1|1
using namespace std;
class SLPF{
	struct node{
		int l,r,sum,add;
	}tr[N*4];
	int cnt;
	int fa[N],dep[N],siz[N],son[N],top[N],id[N],nw[N];
public:
	int root;
	int w[N];
	vector<int> e[N];
protected:
	inline void pushup(int u){
		tr[u].sum=tr[lc].sum+tr[rc].sum;
		return ;
	}
	inline void pushdown(int u){
		if(tr[u].add){
			tr[lc].sum+=tr[u].add*(tr[lc].r-tr[lc].l-1);
			tr[rc].sum+=tr[u].add*(tr[rc].r-tr[rc].l-1);
			tr[lc].add+=tr[u].add;
			tr[rc].add+=tr[u].add;
			tr[u].add=0;
		}
	}
public:
	void build(int u,int l,int r){
		tr[u]={l,r,nw[l],0};
		if(l==r){
			return ;
		}
		int mid=l+r>>1;
		build(lc,l,mid);
		build(rc,mid+1,r);
		pushup(u);
		return ;
	}
	void dfs1(int u,int f){
		fa[u]=f;
		dep[u]=dep[f]+1;
		siz[u]=1;
		for(int v:e[u]){
			if(v==f){
				continue;
			}
			dfs1(v,u);
			siz[u]+=siz[v];
			if(siz[son[u]]<siz[v]){
				son[u]=v;
			}
		}
		return ;
	}
	void dfs2(int u,int tp){
		top[u]=tp;
		id[u]=++cnt;
		nw[cnt]=w[u];
		if(son[u]){
			dfs2(son[u],tp);
		}
		for(int v:e[u]){
			if(v==fa[u]||v==son[u]){
				continue;
			}
			dfs2(v,v);
		}
		return ;
	}
	void change(int u,int x,int y,int k){
		if(x>tr[u].r||y<tr[u].l){
			return ;
		}
		if(x<=tr[u].l&&tr[u].r<=y){
			tr[u].sum+=k*(tr[u].r-tr[u].l+1);
			tr[u].add+=k;
			return ;
		}
		pushdown(u);
		change(lc,x,y,k);
		change(rc,x,y,k);
		pushup(u);
		return ;
	}
	int query(int u,int x,int y){
		if(x>tr[u].r||y<tr[u].l){
			return 0;
		}
		if(x<=tr[u].l&&tr[u].r<=y){
			return tr[u].sum;
		}
		pushdown(u);
		return query(lc,x,y)+query(rc,x,y);
	}
	inline void change_path(int u,int v,int k){
		while(top[u]!=top[v]){
			if(dep[top[u]]<dep[top[v]]){
				swap(u,v);
				change(1,id[top[u]],id[u],k);
				u=fa[top[u]];
			}
		}
		if(dep[u]<dep[v]){
			swap(u,v);
		}
		change(1,id[v],id[u],k);
		return ;
	}
	inline void change_tree(int u,int k){
		change(1,id[u],id[u]+siz[u]-1,k);
		return ;
	}
	int query_path(int u,int v){
		int res=0;
		while(top[u]!=top[v]){
			if(dep[top[u]]<dep[top[v]]){
				swap(u,v);
			}
			res+=query(1,id[top[u]],id[u]);
			u=fa[top[u]];
		}
		if(dep[u]<dep[v]){
			swap(u,v);
		}
		res+=query(1,id[v],id[u]);
		return res;
	}
	int query_tree(int u){
		return query(1,id[u],id[u]+siz[u]-1);
	}
}t;
int n,m,Mod;
int w[N];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>t.root>>Mod;
	for(int i=1;i<=n;i++){
		cin>>w[i];
	}
	for(int i=1;i<=n;i++){
		int a,b;
		cin>>a>>b;
		t.e[a].push_back(b);
		t.e[b].push_back(a);
	}
	t.dfs1(t.root,0);
	t.dfs2(t.root,t.root);
	t.build(1,1,n);
	while(m--){
		int op,x,y,z;
		cin>>op>>x;
		if(x==1){
			cin>>y>>z;
			t.change_path(x,y,z);
		}else if(x==2){
			cin>>y;
			cout<<t.query_path(x,y)%Mod<<'\n';
		}else if(x==3){
			cin>>y;
			t.change_tree(x,y);
		}else{
			cout<<t.query_tree(x)%Mod<<'\n';
		}
	}
	return 0;
}