MLE73 pts求助

record

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 9;
int n,m,root,p;
int op,x,y,k;
struct Tree{
    struct egde{
        int to,nex;
    } e[N];
    int ecnt,head[N];
    int fa[N],weight_child[N],siz[N];
    int weight_link_top[N],dep[N];
    int dfn[N],rdfn[N],id;
    Tree(){
        ecnt = 0;
        memset(head,0,sizeof head);
        memset(dep,0,sizeof dep);
        memset(weight_child,0,sizeof weight_child);
        memset(weight_link_top,0,sizeof weight_link_top);
    }
    void addegde(int u,int v){
        ecnt++;
        e[ecnt] = (egde){v,head[u]};
        head[u] = ecnt;
    }
    void dfs1(int cur,int father){
        fa[cur] = father;
        siz[cur] = 1;
        dep[cur] = dep[father] + 1;
        for(int i = head[cur];i;i = e[i].nex){
            int v = e[i].to;
            if(v != father){
                dfs1(v,cur);
                siz[cur] += siz[v];
                if(siz[v] > siz[weight_child[cur]])
                    weight_child[cur] = v;
            }
        }
    }
    void dfs2(int cur,int link_top){
        id++;
        dfn[cur] = id;
        rdfn[id] = cur;
        weight_link_top[cur] = link_top;
        if(weight_child[cur]){
            dfs2(weight_child[cur],link_top);
            for(int i = head[cur];i;i = e[i].nex){
                int v = e[i].to;
                if(v != fa[cur] && v != weight_child[cur])
                    dfs2(v,v);
            }
        }
    }
} t;
int a[N];
struct seg_tree{
    struct node {
        int val,add;
    } tree[N << 2];
    bool in_range(int l,int r,int now_l,int now_r){
        return l <= now_l && now_r <= r;
    }
    bool out_range(int l,int r,int now_l,int now_r){
        return now_r < l || now_l > r;
    }
    int len(int l,int r){
        return r - l + 1;
    }
    void push_up(int root){
        int lchild = root * 2,rchild = root * 2 + 1;
        tree[root].val = (tree[lchild].val + tree[rchild].val) % p;
    }
    void make_tag(int Len,int root,int add){
        tree[root].add = (tree[root].add + add) % p;
        tree[root].val = (tree[root].val + Len * add % p) % p;
    }
    void push_down(int l,int r,int root){
        int mid = (l + r) / 2,lchild = root * 2,rchild = root * 2 + 1;
        make_tag(len(l,mid),lchild,tree[root].add % p);
        make_tag(len(mid + 1,r),rchild,tree[root].add % p);
        tree[root].add = 0;
    }
    void build(int l,int r,int root) {
        if(l == r) {
            tree[root].val = a[t.rdfn[l]] % p;
            return;
        }
        int mid = (l + r) / 2,lchild = root * 2,rchild = root * 2 + 1;
        build(l,mid,lchild);
        build(mid + 1,r,rchild);
        push_up(root);
    }
    void update(int l,int r,int now_l,int now_r,int root,int add) {
        if(in_range(l,r,now_l,now_r)) {
            tree[root].val = (tree[root].val + len(now_l,now_r) * add) % p;
            tree[root].add = (tree[root].add + add) % p;
        }
        else if(!out_range(l,r,now_l,now_r)){
            int mid = (now_l + now_r) / 2,lchild = root * 2,rchild = root * 2 + 1;
            push_down(now_l,now_r,root);
            update(l,r,mid + 1,now_r,rchild,add);
            update(l,r,now_l,mid,lchild,add);
            push_up(root);
        }
        return;
    }
    void path_update(int x,int y,int k){
        while(t.weight_link_top[x] != t.weight_link_top[y]){
            if(t.dep[t.weight_link_top[x]] < t.dep[t.weight_link_top[y]])
                swap(x,y);
            update(t.dfn[t.weight_link_top[x]],t.dfn[x],1,n,1,k);
            x = t.fa[t.weight_link_top[x]];
        }
        update(min(t.dfn[x],t.dfn[y]),max(t.dfn[x],t.dfn[y]),1,n,1,k);
    }
    int getsum(int l, int r, int now_l, int now_r, int root) {
        int mid = (now_l + now_r) / 2,lchild = root * 2,rchild = root * 2 + 1;
        if(in_range(l,r,now_l,now_r))
            return tree[root].val % p;
        else if(!out_range(l,r,now_l,now_r)){
            push_down(now_l,now_r,root);
            return (getsum(l,r,now_l,mid,lchild) + getsum(l,r,mid + 1,now_r,rchild)) % p;
        }
        else
            return 0;
    }
    int path_query(int x,int y){
        int ans = 0;
        while(t.weight_link_top[x] != t.weight_link_top[y]){
            if(t.dep[t.weight_link_top[x]] < t.dep[t.weight_link_top[y]])
                swap(x,y);
            ans = (ans + getsum(t.dfn[t.weight_link_top[x]],t.dfn[x],1,n,1)) % p;
            x = t.fa[t.weight_link_top[x]];
        }
        return (ans + getsum(min(t.dfn[x],t.dfn[y]),max(t.dfn[x],t.dfn[y]),1,n,1));
    }
} seg;
signed main() {
    scanf("%lld%lld%lld%lld", &n, &m ,&root, &p);
    for(int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    for(int i = 1;i < n;i++){
        scanf("%lld%lld", &x, &y);
        t.addegde(x,y);
        t.addegde(y,x);
    }
    t.dfs1(root,0);
    t.dfs2(root,0);
    seg.build(1,n,1);
    for(int i = 1;i <= m;i++){
        scanf("%lld" ,&op);
        if(op == 1){
            scanf("%lld%lld%lld", &x ,&y, &k);
            k %= p;
            seg.path_update(x,y,k);
        }
        if(op == 2){
            scanf("%lld%lld", &x ,&y);
            printf("%lld\n",seg.path_query(x,y) % p);
        }
        if(op == 3){
            scanf("%lld%lld", &x ,&k);
            k %= p;
            seg.update(t.dfn[x],t.dfn[x] + t.siz[x] - 1,1,n,1,k);
        }
        if(op == 4){
            scanf("%lld", &x);
            printf("%lld\n",seg.getsum(t.dfn[x],t.dfn[x] + t.siz[x] - 1,1,n,1) % p);
        }
    }
    return 0;
}