测试记录

#include<bits/stdc++.h>
using namespace std;
#define int long long

inline int fread()
{
    int n = 0, f = 0; char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-') f = 1;
        c = getchar();
    }
    while ('0' <= c && c <= '9')
        n = (n << 3) + (n << 1) + c - '0', c = getchar();
    return f ? -n : n;
}

int n, m, r, p, a[100005];
int depth[100005], size[100005], son[100005], fa[100005], dfn[100005], top[100005], curdfn, lx[100005], rx[100005];
struct node{
    int l, r, sum, lazy;
}f[400005];
vector<int> g[100005];
void dfs1(int x, int father, int dep){
    depth[x] = dep, size[x] = 1, fa[x] = father;
    int maxson = 0, maxs = 0;
    for(int i = 0;i < g[x].size();i++){
        int k = g[x][i];
        if(k == father)
            continue;
        dfs1(k, x, dep + 1);
        size[x] += size[k];
        if(size[k] > maxson)
            maxson = size[i], maxs = k;
    }
    son[x] = maxs;
}
void dfs2(int x, int cl){
    dfn[x] = ++curdfn, top[x] = cl;
    if(g[x].size() > 1 || x == r)
        dfs2(son[x], cl);
    for(int i = 0;i < g[x].size();i++){
        int k = g[x][i];
        if(dfn[k])
            continue;
        dfs2(k, k);
    }
    lx[x] = dfn[x], rx[x] = curdfn;
}
void pushup(int id){
    f[id].sum = (f[id * 2 + 1].sum + f[id * 2].sum) % p;
}
void pushdown(int id){
    f[id * 2].sum = (f[id * 2].sum + f[id].lazy * (f[id * 2].r - f[id * 2].l + 1)) % p;
    f[id * 2 + 1].sum = (f[id * 2 + 1].sum + f[id].lazy * (f[id * 2 + 1].r - f[id * 2 + 1].l + 1)) % p;
    f[id * 2].lazy += f[id].lazy, f[id * 2].lazy %= p;
    f[id * 2 + 1].lazy += f[id].lazy, f[id * 2 + 1].lazy %= p;
    f[id].lazy = 0;
}
void build(int l, int r, int id){
    f[id].l = l, f[id].r = r;
    if(l == r)
        return;
    int mid = (l + r) / 2;
    build(l, mid, id * 2);
    build(mid + 1, r, id * 2 + 1);
    pushup(id);
}
void modify(int l, int r, int k, int id){
    if(f[id].l == l && f[id].r == r){
        f[id].lazy += k, f[id].lazy %= p;
        f[id].sum += k * (r - l + 1), f[id].sum %= p;
        return;
    }
    pushdown(id);
    if(r <= f[id * 2].r)
        modify(l, r, k, id * 2);
    else
        if(l >= f[id * 2 + 1].l)
            modify(l, r, k, id * 2 + 1);
        else
            modify(l, f[id * 2].r, k, id * 2), modify(f[id * 2 + 1].l, r, k, id * 2 + 1);
    pushup(id);
}
int query(int l, int r, int id){
    if(l == f[id].l && r == f[id].r)
        return f[id].sum;
    pushdown(id);
    if(r <= f[id * 2].r)
        return query(l, r, id * 2) % p;
    else
        if(l >= f[id * 2 + 1].l)
            return query(l, r, id * 2 + 1) % p;
        else
            return (query(l, f[id * 2].r, id * 2) + query(f[id * 2 + 1].l, r, id * 2 + 1)) % p;
    pushup(id);
}
signed main(){
    n = fread(), m = fread(), r = fread(), p = fread();
    for(int i = 1;i <= n;i++)
        a[i] = fread();
    for(int i = 1;i < n;i++){
        int u, v;
        u = fread(), v = fread();
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs1(r, 0, 0);
    dfs2(r, r);
    build(1, n, 1);
    for(int i = 1;i <= n;i++)
        modify(dfn[i], dfn[i], a[i], 1);
    /*for(int i = 1;i <= n;i++)
        cout<<lx[i]<<' '<<rx[i]<<' '<<son[i]<<' '<<fa[i]<<' '<<size[i]<<' '<<top[i]<<' '<<dfn[i]<<endl;*/
    while(m--){
        int op;
        op = fread();
        if(op == 1){
            int x, y, z;
            x = fread(), y = fread(), z = fread();
            int u = x, v = y;
            /*for(int i = 1;i <= n;i++)
                cout<<query(i, i, 1)<<' ';
            cout<<endl;*/
            while(top[u] != top[v]){
                if(depth[top[u]] < depth[top[v]])
                    swap(u, v);
                modify(dfn[top[u]], dfn[u], z, 1);
                u = fa[top[u]];
            }
            if(depth[u] > depth[v])
                swap(u, v);
            /*for(int i = 1;i <= n;i++)
                cout<<query(i, i, 1)<<' ';
            cout<<endl;*/
            modify(dfn[u], dfn[v], z, 1);
            /*cout<<dfn[u]<<' '<<dfn[v]<<endl;*/
            /*for(int i = 1;i <= n;i++)
                cout<<query(i, i, 1)<<' ';
            cout<<endl;*/
        }
        if(op == 2){
            int x, y;
            x = fread(), y = fread();
            int u = x, v = y, ans = 0;
            while(top[u] != top[v]){
                if(depth[top[u]] < depth[top[v]])
                    swap(u, v);
                ans += query(dfn[top[u]], dfn[u], 1);
                ans %= p;
                u = fa[top[u]];
                /*cout<<u<<' '<<v<<endl;*/
            }
            if(depth[u] > depth[v])
                swap(u, v);
            ans += query(dfn[u], dfn[v], 1);
            printf("%lld\n", ans % p);
        }
        if(op == 3){
            int x, z;
            x = fread(), z = fread();
            modify(lx[x], rx[x], z, 1);
            /*for(int i = 1;i <= n;i++)
                cout<<query(i, i, 1)<<' ';
            cout<<endl;*/
        }
        if(op == 4){
            int x;
            x = fread();
            printf("%lld\n", query(lx[x], rx[x], 1));
        }
    }
    return 0;
}