样例输出

2
7

代码：

#include <bits/stdc++.h>
using namespace std ;
#define int long long
#define rep( i , l , r ) for (int i = (l) ; i <= (r) ; i++)
#define per( i , r , l ) for (int i = (r) ; i >= (l) ; i--)
#define MID (l + r >> 1)

const int M = 1e5 + 10 ;
const int N = M ;

int n , m , r , p ;
int cc[N] ;
struct node{
	int to ;
	int nxt ;
}g[2 * M + 1] ;
int head[4 * M + 1] ;
int tot ;
void add ( int u , int v ){
	g[++tot] = (node){v , head[u]} ;
	head[u] = tot; 
}
int dep[N] , sz[N] , fa[N] , top[N] , dfn[N] , rdfn[N] , wc[N] , nw[N];
int vt ;
void dfs ( int u , int f ){
	sz[u] = 1 ;
	dep[u] = dep[f] + 1 ; 
	fa[u] = f;
	for ( int i = head[u] ; i ; i = g[i].nxt){
		int v = g[i].to ;
		if ( v == f ) continue ;
		dfs (v , u) ;
		sz[u] += sz[v] ;
		if ( sz[v] > sz[wc[u]] ) wc[u] = v ; 
	}
}
void dfs1 ( int u , int tp , int f ){
	dfn[u] = ++vt ;
	nw[vt] = cc[u] ;
	rdfn[vt] = u ;
	top[u] = tp ;
	if ( wc[u] != 0 ){	
		dfs1 ( wc[u] , tp , u) ;
		for ( int i = head[u] ; i ; i = g[i].nxt ){
			int v = g[i].to ;
			if ( v != f && v != wc[u] ){
				dfs1(v , v , u) ;
			}
		}
	}
}
int tree[4 * N] , tag[4 * N];
void push_up ( int now ){
	tree[now] = tree[now * 2] % p + tree[now * 2 | 1] % p ;
	tree[now] %= p ; 
}
void make_tag ( int l , int r , int now , int k ){
	tag[now] += k % p ;
	tree[now] += (k % p) * (( r - l + 1 ) % p) ;
	tree[now] %= p ;
	tag[now] %= p;
}
void push_down ( int now , int l , int r ){
	int mid = l + r >> 1;
	if ( tag[now] ){
		make_tag ( l , mid , now * 2 , tag[now] ) ;
		make_tag ( mid + 1 , r , now * 2 + 1 , tag[now] ) ;
		tag[now] = 0 ;
	}
}
void build ( int now , int l , int r ){
	if ( l == r ){
		tree[p] = nw[l] % p ;
		return ;
	}
	build ( now * 2 , l , MID ) ;
	build ( now * 2 + 1 , MID + 1 , r ) ;
	push_up (now) ;
}
void addp (int l , int r , int L , int R , int num , int now){
	if ( r < L || l > R ) return ;
	if ( L <= l && r <= R ){
		tree[now] += ( r - l + 1 ) % p * (num % p) ;
		tag[now] += num % p; 
		return ;
	}
	push_down ( now , l , r ) ;
	int mid = l + r >> 1 ;
	if ( L <= mid )addp ( l , mid , L , R , num , now * 2 ) ;
	if ( R > mid ) addp ( mid + 1 , r , L , R , num , now * 2 | 1) ;
	push_up (now) ;
}
int query ( int l , int r , int L , int R , int now ){
	if ( L <= l && r <= R  ){
		return tree[now] % p ;
	}
	int mid = l + r >> 1 ;
	push_down (now , l , r ) ;
	int sum = 0 ;
	if ( L <= mid ) sum += query ( l , mid , L , R , now * 2 ) % p ;
	sum %= p ;
	if ( R > mid ) sum += query ( mid + 1 , r , L , R , now * 2 + 1 ) % p ;
	return sum % p ;
}
void upd ( int x , int y , int z){
	while ( top[x] != top[y] ){
		if (dep[top[x]] < dep[top[y]]) swap (x , y) ;
		addp ( 1 , n , dfn[top[x]] , dfn[x] , z , 1) ;
		x = fa[top[x]] ;
	}
	addp ( 1 , n , min ( dfn[x] , dfn[y]) , max ( dfn[x] , dfn[y] ) , z , 1 ) ;
}
int qry ( int x , int y ){
	int sm = 0 ;
	while ( top[x] != top[y] ) {
		if ( dep[top[x]] < dep[y] ) swap ( x , y ) ;
		sm += query ( 1 , n , dfn[top[x]] , dfn[x] , 1 ) ;
		sm %= p ;
		x = fa[top[x]] ;
	}
	return (sm + (query(1 , n, min (dfn[x] , dfn[y]) , max (dfn[x] , dfn[y] ) , 1 ) % p )) % p ;
}
void solve (){
	cin >> n >> m >> r >> p ;
	rep ( i , 1 , n ){
		cin >> cc[i] ;
		cc[i] %= p ;
	}
	rep ( i , 1 , n - 1 ){
		int u , v ;
		cin >> u >> v ;
		add ( u , v ) ;
		add ( v , u ) ;
	}
	dfs (r , r) ;
	dfs1 (r , r , r) ;
	build (1 , 1 , n) ;
	while (m--){
		int op , x , y , z ;
		cin >> op >> x ;
		if ( op == 1 ){
			cin >> y >> z ;
			upd ( x , y , z ) ;
		}else if ( op == 2 ){
			cin >> y ;
			cout << qry ( x , y ) << '\n' ;
		}else if ( op == 3 ){
			cin >> z ;
			addp (1 , n , dfn[x] , dfn[x] + sz[x] - 1 , z , 1) ;
		}else{
			cout << query ( 1 , n , dfn[x] , dfn[x] + sz[x] - 1 , 1) << '\n' ;
		}
	}
}

signed main (){
	int _ = 1 ;
	//cin >> _ ;
	while ( _-- ){solve () ;}
	return 0 ;
}