求调【拜托】

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=1e5+2;
int deep[maxn],fa[maxn],son[maxn],flag[maxn];
int hd[maxn],to[maxn],nxt[maxn],ww[maxn],cnt;
int a[maxn],b[maxn],top[maxn];
int n,m,r,p,x,y,z,num=1,op;
struct node{
    int l,r,sum;
    int sz,lz;
} tree[maxn];
void addege(int xx,int yy){
    to[num]=yy;
    nxt[num]=hd[xx];
    hd[xx]=num++;
}
void pushdown(int now){
    if(!tree[now].lz){
        return;
    }
    tree[now*2].sum+=tree[now*2].sz*tree[now].lz;
    tree[now*2].sum%=p;
    tree[now*2+1].sum+=tree[now*2+1].sz*tree[now].lz;
    tree[now*2+1].sum%=p;
    tree[now*2].lz+=tree[now].lz;
    tree[now*2].lz%=p;
    tree[now*2+1].lz+=tree[now].lz;
    tree[now*2+1].lz%=p;
    tree[now].lz=0;
    return;
}
void build(int now,int l,int r){
    tree[now].l=l;
    tree[now].r=r;
    tree[now].sz=r-l+1;
    if(l==r){
        tree[now].sum=a[l];
        tree[now].sum%=p;
        return;
    }
    int mid=(l+r)/2;
    build(now*2,l,mid);
    build(now*2+1,mid+1,r);
    tree[now].sum=tree[now*2].sum+tree[now*2+1].sum;
    tree[now].sum%=p;
    return;
}
void add(int now,int l,int r,int w){
    if(tree[now].l>=l&&tree[now].r<=r){
        tree[now].sum+=tree[now].sz*w;
        tree[now].sum%=p;
        tree[now].lz+=w;
        tree[now].lz%=p;
        return;
    }
    pushdown(now);
    int mid=(tree[now].l+tree[now].r)/2;
    if(l<=mid){
        add(now*2,l,r,w);
    }
    if(r>mid){
        add(now*2+1,l,r,w);
    }
    tree[now].sum=tree[now*2].sum+tree[now*2+1].sum;
    tree[now].sum%=p;
    return;
}
int check(int now,int l,int r){
    int ans=0;
    if(l<=tree[now].l&&tree[now].r<=r){
        return tree[now].sum;
    }
    if(tree[now].l>r||tree[now].r<l){
        return 0;
    }
    pushdown(now);
    int mid=(tree[now].l+tree[now].r)/2;
    if(l<=mid){
        ans+=check(now*2,l,r);
        ans%=p;
    }
    if(r<mid){
        ans+=check(now*2+1,l,r);
        ans%=p;
    }
    return ans%p;
}
int dfs1(int now,int f,int dep){
    deep[now]=dep;
    fa[now]=f;
    flag[now]=1;
    int ms=-1;
    for(int i=hd[now];i;i=nxt[i]){
        if(to[i]==f){
            continue;
        }
        flag[now]+=dfs1(to[i],now,dep+1);
        if(flag[to[i]]>ms){
            ms=flag[to[i]];
            son[now]=to[i];
        }
    }
    return flag[now];
}
void dfs2(int now,int x){
    cnt++;
    ww[now]=cnt;
    a[cnt]=b[cnt];
    top[now]=x;
    if(!son[now]){
        return;
    }
    dfs2(son[now],x);
    for(int i=hd[now];i;i=nxt[i]){
        if(!ww[to[i]]){
            dfs2(to[i],to[i]);
        }
    }
}
int val(int x,int y){
    int ans=0;
    while(top[x]!=top[y]){
        if(deep[top[x]]<deep[top[y]]){
            swap(x,y);
        }
        ans+=check(1,ww[top[x]],ww[x]);
        ans%=p;
        x=fa[top[x]];
    }
    if(deep[x]>deep[y]){
        swap(x,y);
    }
    ans+=check(1,ww[x],ww[y]);
    ans%=p;
    return ans;
}
void tdd(int x,int y,int w){
    while(top[x]!=top[y]){
        if(deep[top[x]]<deep[top[y]]){
            swap(x,y);
        }
        add(1,ww[top[x]],ww[x],w);
        x=fa[top[x]];
    }
    if(deep[x]>deep[y]){
        swap(x,y);
    }
    add(1,ww[x],ww[y],w);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>r>>p;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]%=p;
        b[i]=a[i];
    }
    for(int i=1;i<n;i++){
        cin>>x>>y;
        addege(x,y);
        addege(y,x);
    }
    dfs1(r,0,1);
    dfs2(r,r);
    build(1,1,n);
    while(m--){
        cin>>op;
        if(op==1){
            cin>>x>>y>>z;
            tdd(x,y,z%p);
        }
        if(op==2){
            cin>>x>>y;
            cout<<val(x,y)<<"\n";
        }
        if(op==3){
            cin>>x>>y;
            add(1,ww[x],ww[x]+flag[x]-1,y%p);
        }
        if(op==4){
            cin>>x;
            cout<<check(1,ww[x],ww[x]+flag[x]-1)<<"\n";
        }
    }
    return 0;
}

10分求调

( ๑ŏ ﹏ ŏ๑ )伤心

( ๑ŏ ﹏ ŏ๑ )伤心

(ó﹏ò｡)难受