10pts 玄关求调

样例输出

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 ;
}