数据是否过水

rt，重儿子换成第一个儿子然后过了，跑得比重链剖分还快。

代码：

#include<bits/stdc++.h>

using namespace std;

const int N=4e5+10;

int n,m,r,p;
int a[N];
int an[N];
int deep[N];
int siz[N];
int fa[N];
int son[N];
int id[N];
int cnt;
int top[N];
int tree[N];
int lazy[N];
int res;

vector<int>v[N];

void dfs1(int x,int f,int de){
    deep[x]=de;
    fa[x]=f;
    siz[x]=1;
    for(int i=0;i<v[x].size();i++){
        int y=v[x][i];
        if(y==f) continue;
        dfs1(y,x,de+1);
        siz[x]+=siz[y];
        if(!son[x]){
            son[x]=y;
        }
    }
}

void dfs2(int x,int topfa){
    id[x]=++cnt;
    an[cnt]=a[x];
    top[x]=topfa;

    if(!son[x]) return;
    dfs2(son[x],topfa);

    for(int i=0;i<v[x].size();i++){
        int y=v[x][i];
        if(y==fa[x]||y==son[x]) continue;
        dfs2(y,y);
    }
}

void build(int rt,int l,int r){
    if(l==r){
        tree[rt]=an[l];
        tree[rt]%=p;
        return;
    }
    int mid=(l+r)/2;
    build(rt*2,l,mid);
    build(rt*2+1,mid+1,r);
    tree[rt]=(tree[rt*2]+tree[rt*2+1])%p;
}

void pushdown(int rt,int len){
    lazy[rt*2]+=lazy[rt];
    lazy[rt*2+1]+=lazy[rt];
    tree[rt*2]+=lazy[rt]*(len-len/2);
    tree[rt*2+1]+=lazy[rt]*(len/2);
    tree[rt*2]%=p;
    tree[rt*2+1]%=p;
    lazy[rt]=0;
}

void update(int rt,int l,int r,int L,int R,int k){
    if(L<=l&&r<=R){
        lazy[rt]+=k;
        tree[rt]+=k*(r-l+1);
        return;
    }
    if(lazy[rt]) pushdown(rt,r-l+1);
    int mid=(l+r)/2;
    if(L<=mid) update(rt*2,l,mid,L,R,k);
    if(R>mid) update(rt*2+1,mid+1,r,L,R,k);
    tree[rt]=(tree[rt*2]+tree[rt*2+1])%p;
}

void query(int rt,int l,int r,int L,int R){
    if(L<=l&&r<=R){
        res+=tree[rt];
        res%=p;
        return;
    }
    if(lazy[rt]) pushdown(rt,r-l+1);
    int mid=(l+r)/2;
    if(L<=mid) query(rt*2,l,mid,L,R);
    if(R>mid) query(rt*2+1,mid+1,r,L,R);
}

void updateL(int x,int y,int z){
    z%=p;
    while(top[x]!=top[y]){
        if(deep[top[x]]<deep[top[y]]){
            swap(x,y);
        }
        update(1,1,n,id[top[x]],id[x],z);
        x=fa[top[x]];
    }
    if(deep[x]>deep[y]) swap(x,y);
    update(1,1,n,id[x],id[y],z);
}

int queryL(int x,int y){
    int ans=0;
    while(top[x]!=top[y]){
        if(deep[top[x]]<deep[top[y]]){
            swap(x,y);
        }
        res=0;
        query(1,1,n,id[top[x]],id[x]);
        ans+=res;
        ans%=p;
        x=fa[top[x]];
    }
    if(deep[x]>deep[y]) swap(x,y);
    res=0;
    query(1,1,n,id[x],id[y]);
    ans+=res;
    return ans%p;
}

void updateS(int x,int z){
    update(1,1,n,id[x],id[x]+siz[x]-1,z);
}

int queryS(int x){
    res=0;
    query(1,1,n,id[x],id[x]+siz[x]-1);
    return res%p;
}

int main(){
    scanf("%d%d%d%d",&n,&m,&r,&p);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n-1;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs1(r,0,1);
    dfs2(r,r);
    build(1,1,n);
    while(m--){
        int op,x,y,z;
        scanf("%d",&op);
        if(op==1){
            scanf("%d%d%d",&x,&y,&z);
            updateL(x,y,z);
        }
        if(op==2){
            scanf("%d%d",&x,&y);
            printf("%d\n",queryL(x,y));
        }
        if(op==3){
            scanf("%d%d",&x,&z);
            updateS(x,z);
        }
        if(op==4){
            scanf("%d",&x);
            printf("%d\n",queryS(x));
        }
    }
    return 0;
}