前置知识：线段树，链式前向星，LCA，DFS序
树链剖分通常的操作:
1.x -> y 的路径上修改 2.x -> y 的路径上查询 3. 对于 x 的子树修改 4.对于 x 的子树查询。
一般还有换根操作。
树链剖分有两个DFS 这两个DFS就是把一棵树变成一个序列。 然后就可以用数据结构来维护了。
第一个DFS 用来求 \(fa\)（祖先节点） \(size\)（子树大小）\(son\)（重儿子） \(d\)（深度）
第二个DFS 用来求\(top\)（这条链上最顶端的点） \(id\)（编号）以及其他的赋值操作。 但是重儿子要先DFS。
const int N = 1e5 + 10 ;
struct node { int v , nxt ; } ;
node e[N << 1] ;
int head[N] , cnt = 0 ;
inline void Add(int u , int v) { e[++ cnt].v = v ; e[cnt].nxt = head[u] ; head[u] = cnt ; }
int size[N] , son[N] , d[N] ;
inline void Dfs1(int u) { size[u] = 1 ;
for(register int i = head[u] ; i ; i = e[i].nxt) {
int v = e[i].v ; if(v == fa[u]) continue ;
d[v] = d[u] + 1 , fa[v] = u , Dfs1(v) ; size[u] += size[v] ;
if(size[v] > size[son[u]]) son[u] = v ;
}
}
int top[N] , id[N] , tot = 0 ;
inline void Dfs2(int u , int tp) { top[u] = tp , id[u] = ++ tot ;
if(! son[u]) return ; Dfs2(son[u] , tp) ;
for(register int i = head[u] ; i ; i = e[i].nxt) { int v = e[i].v ;
if(v ^ fa[u] && v ^ son[u]) Dfs2(v , v) ;
}
}这样就算是一个大概的板子了 没有赋值…（赋值根据编号搞一搞就可以了 下面会讲。）
#include <bits/stdc++.h>
using namespace std ;
inline int read() { register int res = 0 ; register char c ;
#define gc c = getchar()
while(isspace(gc)) ;
while(res = (res << 1) + (res << 3) + (c & 15) , isdigit(gc)) ;
return res ;
}
int n , m , r , p ;
const int N = 1000000 + 5 ;
struct E{ int v ;int nxt ; } ;
E edge[N << 1] ;
int a[N] ; int fa[N] ; int w[N] ; int id[N] ; int son[N] ;
int cnt = 0 ; int head[N] ; int Add[N << 2] , laz[N << 2] ;
int dep[N] , siz[N] , t[N] ;
inline void Add_Edge(register int u , register int v) { edge[++ cnt].v = v ; edge[cnt].nxt = head[u] ; head[u] = cnt ; return ; }//建边。
#define l(x) x << 1
#define r(x) x << 1 | 1
inline void Push_down(register int x , register int len) {
laz[l(x)] += laz[x] ; laz[r(x)] += laz[x] ;
Add[l(x)] += laz[x] * (len - (len >> 1)) ; Add[r(x)] += laz[x] * (len >> 1) ;
Add[l(x)] %= p ; Add[r(x)] %= p ;
laz[x] = 0 ; return ;
}
inline void Build(register int l , register int r , register int rt) {//建树
if(l == r) { Add[rt] = a[l] ; return ; }
register int mid = l + r >> 1 ;
Build(l , mid , l(rt)) ; Build(mid + 1 , r , r(rt)) ;
Add[rt] = (Add[l(rt)] + Add[r(rt)]) % p ;
}
inline void Update(register int a , register int b , register int l , register int r , register int rt , register int k) {//正常的线段树操作
if(a <= l and r <= b) { laz[rt] += k ; Add[rt] += k * (r - l + 1) ; }
else {
if(laz[rt]) Push_down(rt , r - l + 1) ;
register int mid = l + r >> 1 ;
if(a <= mid) Update(a , b , l , mid , l(rt) , k) ;
if(b > mid) Update(a , b , mid + 1 , r , r(rt) , k) ;
Add[rt] = (Add[l(rt)] + Add[r(rt)]) % p ;
}
}
int res = 0 ;
inline void query(register int a , register int b , register int l , register int r , register int rt) {
if(a <= l and r <= b) { res = (res + Add[rt]) % p ; return ; }
else {
if(laz[rt]) Push_down(rt , r - l + 1) ;
register int mid = l + r >> 1 ;
if(a <= mid) query(a , b , l , mid , l(rt)) ;
if(b > mid) query(a , b , mid + 1 , r , r(rt)) ;
}
}
inline int Query(register int a , register int b , register int l , register int r , register int rt) {//正常的线段树操作
res = 0 ; query(a , b , l , r , rt) ;
return res % p ;
}
inline void Upd_Range(register int x , register int y , register int k) {//链上修改
while(t[x] != t[y]) {
if(dep[t[x]] < dep[t[y]]) swap(x , y) ;
Update(id[t[x]] , id[x] , 1 , n , 1 , k) ;
x = fa[t[x]] ;
}
if(dep[x] > dep[y]) swap(x , y) ;
Update(id[x] , id[y] , 1 , n , 1 , k) ;
}
inline int Query_Range(register int x , register int y) {//链上查询
int ans = 0 ;
while(t[x] != t[y]) {
if(dep[t[x]] < dep[t[y]]) swap(x , y) ;
ans += Query(id[t[x]] , id[x] , 1 , n , 1) ;
x = fa[t[x]] ;
}
if(dep[x] > dep[y]) swap(x , y) ;
ans += Query(id[x] , id[y] , 1 , n , 1) ;
return ans % p ;
}
inline int Qson(register int x) { return Query(id[x] , id[x] + siz[x] - 1 , 1 , n , 1) ; } // 子树查询。
inline void Updson(register int x , register int k) { Update(id[x] , id[x] + siz[x] - 1 , 1 , n , 1 , k) ; return ; }
inline void Dfs1(register int x , register int f , register int deep) {
dep[x] = deep ; fa[x] = f ; siz[x] = 1 ;
int max_son = -1 ;
for(register int i = head[x] ; i ; i = edge[i].nxt) {
register int v = edge[i].v ;
if(v == f) continue ;
Dfs1(v , x , deep + 1) ;siz[x] += siz[v] ;
if(siz[v] > max_son) max_son = siz[v] , son[x] = v ;
}
}
int tot = 0 ;
inline void Dfs2(register int x , register int tf) {
id[x] = ++ tot ; a[tot] = w[x] ; t[x] = tf ;
if(! son[x]) return ;
Dfs2(son[x] , tf) ;
for(register int i = head[x] ; i ; i = edge[i].nxt) {
int v = edge[i].v ;
if(v == fa[x] or v == son[x]) continue ;
Dfs2(v , v) ;
}
}
signed main() {
n = read() ; m = read() ; r = read() ; p = read() ;
for(register int i = 1 ; i <= n ; i ++) w[i] = read() ;
for(register int i = 1 ; i <= n - 1 ; i ++) {
int u = read() , v = read() ;
Add_Edge(u , v) ;
Add_Edge(v , u) ;
}
Dfs1(r , 0 , 1) ; Dfs2(r , r) ; Build(1 , n , 1) ;
for( ; m -- ; ) {
register int opt = read() ;
if(opt == 1) {
register int x = read() , y = read() , k = read() ;
Upd_Range(x , y , k % p) ;
}
if(opt == 2) {
register int x = read() , y = read() ;
printf("%d\n" , Query_Range(x , y)) ;
}
if(opt == 3) {
register int x = read() , y = read() ;
Updson(x , y) ;
}
if(opt == 4) { printf("%d\n" , Qson(read())) ; }
}
return 0 ;
}