P3384 【模板】重链剖分/树链剖分
Orz

#include <bits/stdc++.h> 
using namespace std;
int n,m,r,p;
const int maxn = 1e5 + 1;
struct edge{
	int fr,to,nxt;
}e[maxn*2] = {};
int w[maxn] = {}, head[maxn] = {}, cnt_edge = 0;
int top[maxn] = {}, dfn[maxn] = {}, rnk[maxn] = {}, fa[maxn] = {}, dep[maxn] = {}, son[maxn] = {}, siz[maxn] = {};

void add_edge(int u, int v){
	e[++cnt_edge] = (edge){u,v,head[u]};
	head[u] = cnt_edge;
}
struct segTree{
	int sum[maxn*4], lazy[maxn*4];
	segTree() {
		memset(sum, 0, sizeof(sum));
		memset(lazy, 0, sizeof(lazy));
	}
	
	void pushDown(int s, int t, int node){
		int left = 2*node, right = 2*node + 1, mid = (s+t)/2;
		int k = lazy[node];
		lazy[node] = 0;
		lazy[left] = (lazy[left] + k) % p; 
		lazy[right] = (lazy[right] + k) % p;
		sum[left] = (sum[left] + k*(mid-s+1)%p) % p; 
		sum[right] = (sum[right] + k*(t-mid)%p) % p; 
	}
	
	void buildTree(int s, int t, int node){
		int left = 2*node, right = 2*node + 1, mid = (s+t)/2;
		if(s == t){
			sum[node] = w[rnk[t]];
			return ;
		}
		buildTree(s,mid,left);
		buildTree(mid+1,t,right);
		sum[node] = (sum[left] + sum[right]) % p;
	}
	
	int getsum(int l, int r, int s, int t, int node){
		int left = 2*node, right = 2*node + 1, mid = (s+t)/2;
		if(l <= s && t <= r) return sum[node] ;
		pushDown(s,t,node);
		int ret = 0;
		if(l <= mid) ret = getsum(l,r,s,mid,left) % p;
		if(r > mid) ret = (ret + getsum(l,r,mid+1,t,right)) % p;
		return ret;
	}
	
	void update(int l,  int r, int k, int s, int t, int node){
		int left = 2*node, right = 2*node + 1, mid = (s+t)/2;
		if(l <= s && t <= r){
			sum[node] = (sum[node] + k*(t-s+1)%p) % p;
			lazy[node] = (lazy[node] + k) % p;
			return;
		}
		pushDown(s,t,node);
		if(l <= mid) update(l,r,k,s,mid,left);
		if(r > mid) update(l,r,k,mid+1,t,right);
		sum[node] = (sum[left] + sum[right]) % p;
	}
}st;

int dfs1(int u){
	son[u] = -1;
	siz[u] = 1;
	for(int i = head[u]; i != -1; i = e[i].nxt){
		int v = e[i].to;
		if(!dep[v]){
			dep[v] = dep[u] + 1;
			fa[v] = u;
			dfs1(v);
			siz[u] += siz[v];
			if(son[u] == -1 || siz[son[u]] < siz[v]) son[u] = v;
		}
	}
}
int cnt_dfn = 0;
void dfs2(int u, int t){
	top[u] = t;
	dfn[u] = ++cnt_dfn;
	rnk[cnt_dfn] = u;
	if(son[u] == -1) return;
	dfs2(son[u],t);
	for(int i = head[u]; i != -1; i = e[i].nxt){
		int v = e[i].to;
		if(v != fa[u] && v != son[u]) dfs2(v,v);
	}
}
void updateAdd(int u, int v, int k){
	while(top[u] != top[v]){
		if(dep[top[u]] < dep[top[v]]) swap(u,v);
		st.update(dfn[top[u]],dfn[u],k,1,n,1);
		u = fa[top[u]];
	}
	if(dfn[u] > dfn[v]) swap(u,v);
	st.update(dfn[u],dfn[v],k,1,n,1);
}
int querySum(int u, int v){
	int ans = 0;
	while(top[u] != top[v]){
		if(dep[top[u]] < dep[top[v]]) swap(u,v);
		ans =(ans + st.getsum(dfn[top[u]],dfn[u],1,n,1)) % p;
		u = fa[top[u]];
	}
	if(dfn[u] > dfn[v]) swap(u,v);
	ans = (ans + st.getsum(dfn[u],dfn[v],1,n,1)) % p;
	return ans;
}
int main(){
	cin>>n>>m>>r>>p;
	for(int i = 1; i <= n; ++i) cin>>w[i];
	memset(head, -1, sizeof(head));
	for(int i = 1; i <= n-1; ++i){
		int u,v;
		scanf("%d%d",&u,&v);
		add_edge(u,v); add_edge(v,u);
	}
	
	fa[r] = r;
	dep[r] = 1;
	dfs1(r);
	dfs2(r,r);
	st.buildTree(1,n,1);
	
	do{
		int t,x,y,z;
		scanf("%d",&t);
		if(t == 1){
			scanf("%d%d%d",&x,&y,&z);
			updateAdd(x,y,z);
		}
		if(t == 2){
			scanf("%d%d",&x,&y);
			printf("%d\n",querySum(x,y));
		}
		if(t == 3){
			scanf("%d%d",&x,&z);
			st.update(dfn[x],(dfn[x]+siz[x]-1),z,1,n,1);
		}
		if(t == 4){
			scanf("%d",&x);
			printf("%d\n",st.getsum(dfn[x],(dfn[x]+siz[x]-1),1,n,1));
		}
	}while(--m);
	return 0;
}