可爱树剖 37pts AC #1-3 #11 求调

rt，玄关。

#include <iostream>
#include <vector>
#define int long long
#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)
using namespace std;

const int N = 1e5 + 10;

int n,m,r,mod,tot = 0;
int f[N],dep[N],siz[N],son[N],dfn[N],rk[N],top[N],tag[N * 4],a[N],tree[N * 4];

vector <int> G[N];

void dfs1(int u,int fa){
    f[u] = fa;
    dep[u] = dep[fa] + 1;
    siz[u] = 1;
    int p = -1;
    for(auto to : G[u]){
        if(to == fa) continue;
        dfs1(to,u);
        siz[u] += siz[to];
        if(siz[to] > p) p = siz[to],son[u] = to;
    }
}

void dfs2(int u,int fa){
    dfn[u] = ++tot;
    rk[tot] = u;
    if(u == son[fa]) top[u] = top[fa];
    else top[u] = u;
    for(auto to : G[u]){
        if(to == fa) continue;
        dfs2(to,u);
    }
}

void pushup(int u){
    tree[u] = (tree[ls(u)] + tree[rs(u)]) % mod;
}

void build(int u,int l,int r){
    if(l == r){
        tree[u] = a[rk[l]];
        return;
    }
    int mid = (l + r) / 2;
    build(ls(u),l,mid);
    build(rs(u),mid + 1,r);
    pushup(u);
}

bool inrange(int l,int r,int L,int R){
    return (L <= l) && (r <= R);
}

bool outofrange(int l,int r,int L,int R){
    return (L > r) || (R < l);
}

void maketag(int u,int l,int r,int x){
    tag[u] += x;
    tree[u] += (r - l + 1) * x;
    tag[u] %= mod,tree[u] %= mod;
}

void pushdown(int u,int l,int r){
    if(!tag[u]) return;
    int mid = (l + r) / 2;
    maketag(ls(u),l,mid,tag[u]);
    maketag(rs(u),mid + 1,r,tag[u]);
    tag[u] = 0;
}

int query(int u,int l,int r,int L,int R){
    if(inrange(l,r,L,R)){
        return tree[u];
    }else if(!outofrange(l,r,L,R)){
        int mid = (l + r) / 2;
        pushdown(u,l,r);
        return (query(ls(u),l,mid,L,R) + query(rs(u),mid + 1,r,L,R)) % mod;
    }else return 0;
}

void update(int u,int l,int r,int L,int R,int x){
    if(inrange(l,r,L,R)){
        maketag(u,l,r,x);
    }else if(!outofrange(l,r,L,R)){
        int mid = (l + r) / 2;
        pushdown(u,l,r);
        update(ls(u),l,mid,L,R,x);update(rs(u),mid + 1,r,L,R,x);
        pushup(u);
    }else return;
}

int sumpath(int u,int v){
    int cnt = 0;
    while(top[u] != top[v]){
        if(dep[top[u]] > dep[top[v]]){
            cnt += query(1,1,n,dfn[top[u]],dfn[u]);
            //cout << top[u] << ' ' << u << '/';
            u = f[top[u]];
        }else{
            cnt += query(1,1,n,dfn[top[v]],dfn[v]);
            //cout << top[v] << ' ' << v << '/';
            v = f[top[v]];
        }
        cnt %= mod;
    }
    if(dep[u] > dep[v]) swap(u,v);
    cnt += query(1,1,n,dfn[u],dfn[v]);
    //cout << u << ' ' << v << '/';
    return cnt % mod;
}

void changepath(int u,int v,int x){
    while(top[u] != top[v]){
        if(dep[top[u]] > dep[top[v]]){
            update(1,1,n,dfn[top[u]],dfn[u],x);
            u = f[top[u]];
            //cout << top[u] << ' ' << u << '/';
        }else{
            update(1,1,n,dfn[top[v]],dfn[v],x);
            v = f[top[v]];
            //cout << top[v] << ' ' << v << '/';
        }
    }
    if(dep[u] > dep[v]) swap(u,v);
    update(1,1,n,dfn[u],dfn[v],x);
    //cout << u << ' ' << v << '/';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> r >> mod;
    for(int i = 1;i <= n;i ++){
        cin >> a[i];
    }
    for(int i = 1;i < n;i ++){
        int u,v;cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    dfs1(r,0);
    dfs2(r,0);
    build(1,1,n);
    //  for(int i = 1;i <= n;i ++) cout << son[i] <<' ';

    while(m --){
        int op,x,y,z;
        cin >> op;
        if(op == 1){
            cin >> x >> y >> z;
            changepath(x,y,z);
        }else if(op == 2){
            cin >> x >> y;
            cout << sumpath(x,y) % mod << '\n';
        }else if(op == 3){
            cin >> x >> z;
            update(1,1,n,dfn[x],dfn[x] + siz[x] - 1,z);
        }else{
            cin >> x;
            cout << query(1,1,n,dfn[x],dfn[x] + siz[x] - 1) % mod << '\n';
        }
    }
    return 0;
}