性感代码在线求调教

厌氧

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int n , m , r , mod , tp;
vector<int> q[N];
int fa[N] , dep[N] , sz[N] , son[N] , hd[N] , id[N] , a[N] , tree[N << 2] , tg[N << 2];
void dfs1(int x , int y){
    fa[x] = y;
    dep[x] = dep[y] + 1;
    sz[x] = 1;
    for(int i = 0; i < q[x].size(); i ++){
        int v = q[x][i];
        if(v == y) continue;
        dfs1(v , x);
        sz[x] += sz[v];
        if(sz[v] > sz[son[x]]) son[x] = v; 
    }
    return;
}
void dfs2(int x , int h){
    hd[x] = h;
    id[x] = ++ tp;
    if(son[x] != 0) dfs2(son[x] , h);
    for(int i = 0; i < q[x].size(); i ++){
        int v = q[x][i];
        if(v == son[x] || v == fa[x]) continue;
        dfs2(v , v);
    }
    return;
}
void down(int p , int l , int r){
    if (tg[p]) {
        int mid = l + r >> 1;
        tree[p << 1] = (tree[p << 1] + tg[p] * (mid - l + 1) % mod) % mod;
        tree[p << 1 | 1] = (tree[p << 1 | 1] + tg[p] * (r - mid) % mod) % mod;
        tg[p << 1] = (tg[p << 1] + tg[p]) % mod;
        tg[p << 1 | 1] = (tg[p << 1 | 1] + tg[p]) % mod;
        tg[p] = 0;
    }
}
void update(int p , int l , int r , int x , int y , int z){
    if (x > y) return;
    if(x <= l && r <= y){
        tg[p] += z;
        tree[p] += z * (r - l + 1);
        tree[p] %= mod;
        return ;
    }
    int mid = l + r >> 1;
    down(p, l, r);
    if (mid >= x) update(p << 1 , l , mid , x , y , z);
    if (mid < y) update(p << 1 | 1 , mid + 1 , r , x , y , z);
    tree[p] = (tree[p << 1] + tree[p << 1 | 1]) % mod;
}
int query(int p , int l , int r , int x , int y){
//  if(l > y || r < x) return 0;
    if (x > y) return 0; 
    if(x <= l && r <= y) return tree[p];
    int mid = l + r >> 1;
    int res = 0;
    down(p, l, r);
    if (mid >= x) res = (res + query(p << 1, l, mid, x, y)) % mod;
    if (mid < y) res = (res + query(p << 1 | 1, mid + 1, r, x, y)) % mod; 
    tree[p] = (tree[p << 1] + tree[p << 1 | 1]) % mod;
    return res;
}
int d1(int x , int y){
    int ans = 0;
    while(hd[x] != hd[y]){
        if(dep[hd[x]] < dep[hd[y]]) swap(x , y);
        ans = (ans + query(1 , 1 , n , id[hd[x]], id[x])) % mod;
        x = fa[hd[x]];
    }
    if(dep[x] < dep[y]) swap(x , y);
    ans = (ans + query(1 , 1 , n , id[y] , id[x])) % mod;
    return ans;
}
int d2(int x , int y , int z){
    while(hd[x] != hd[y]){
        if(dep[hd[x]] < dep[hd[y]]) swap(x , y);
        update(1 , 1 , n , id[hd[x]], id[x] , z);
        x = fa[hd[x]];
    }
    if(dep[x] < dep[y]) swap(x , y);
    update(1 , 1 , n , id[y] , id[x] , z);
}
signed main(){
    cin >> n >> m >> r >> mod;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];
    for(int i = 1; i < n; i ++){
        int x , y;
        cin >> x >> y;
        q[x].push_back(y);
        q[y].push_back(x); 
    }
    dfs1(r , 0);
    dfs2(r , r);
    for(int i = 1; i <= n; i ++)
        update(1 , 1 , n , id[i] , id[i] , a[i]);
    while(m --){
        int op , x , y , z;
        cin >> op >> x;
        if(op == 1) cin >> y >> z , d2(x , y , z);
        if(op == 2) cin >> y , cout << d1(x , y) % mod << '\n';
        if(op == 3) cin >> z , update(1 , 1 , n , id[x] , id[x] + sz[x] - 1 , z); 
        if(op == 4) cout << query(1 , 1 , n , id[x] , id[x] + sz[x] - 1) % mod << '\n';
    }
    return 0;
}