树剖求调

9分，第三点AC，其它全WA

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

const int maxn=100050;
int n,m,r,p,val[maxn],op,x,y,z,T[4*maxn],tag[4*maxn],len[4*maxn],tmp[maxn];
int dfn[maxn],tp[maxn],siz[maxn],depth[maxn],fa[maxn],heavy[maxn],nth,bottom[maxn];
vector<int> Tree[maxn];

void build_tree(int l,int r,int no){//线段树建树
    len[no]=r-l+1;
    if(l==r){
        T[no]=tmp[l];
        return;
    }int mid=(l+r)/2;
    build_tree(l,mid,no<<1);
    build_tree(mid+1,r,(no<<1)|1);
    T[no]=(T[no<<1]+T[(no<<1)|1])%p;
}

void update(int no){//标记更新（就是pushdown）
    T[no<<1]+=tag[no]*len[no<<1];
    T[no<<1]%=p;
    T[(no<<1)|1]+=tag[no]*len[(no<<1)|1];
    T[(no<<1)|1]%=p;
    tag[no<<1]+=tag[no];
    tag[no<<1]%=p;
    tag[(no<<1)|1]+=tag[no];
    tag[(no<<1)|1]%=p;
    tag[no]=0;
}

int sum(int l,int r,int no,int L,int R){//线段树求和
    if(l>R||r<L)return 0;
    if(l>=L&&r<=R)return T[no];
    update(no);
    int ret=0,mid=(l+r)/2;
    ret+=sum(l,mid,no<<1,L,R);
    ret+=sum(mid+1,r,(no<<1)|1,L,R);
    return ret%p;
}

void add(int l,int r,int no,int v,int L,int R){//线段树区间加
    if(l>R||r<L)return;
    if(l>=L&&r<=R){
        T[no]+=(r-l+1)*v;
        tag[no]+=v;
        return;
    }update(no);
    int mid=(l+r)/2;
    add(l,mid,no<<1,v,L,R);
    add(mid+1,r,(no<<1)|1,v,L,R);
}

void dfs1(int no,int deep){
    siz[no]=1;
    depth[no]=deep;
    int hson=-1,maxn=-1;
    for(unsigned int i=0;i<Tree[no].size();i++){
        if(siz[Tree[no][i]]==0){
            fa[Tree[no][i]]=no;
            dfs1(Tree[no][i],deep+1);
            siz[no]+=siz[Tree[no][i]];
            if(maxn<siz[Tree[no][i]]){hson=Tree[no][i];maxn=siz[Tree[no][i]];}
        }
    }heavy[no]=hson;
}

void dfs2(int no,int t){
    if(dfn[no])return;
    dfn[no]=++nth;
    bottom[no]=dfn[no];
    tmp[nth]=val[no];
    tp[no]=t;
    if(heavy[no]!=-1){dfs2(heavy[no],t);bottom[no]=max(bottom[no],bottom[heavy[no]]);}
    for(unsigned int i=0;i<Tree[no].size();i++){
        if(dfn[Tree[no][i]]==0){
            dfs2(Tree[no][i],Tree[no][i]);
            bottom[no]=max(bottom[no],bottom[Tree[no][i]]);
        }
    }
}

int link_sum(int xx,int yy){//树剖路径和
    int ret=0;
    while(tp[xx]!=tp[yy]){
        if(depth[tp[xx]]<depth[tp[yy]])swap(xx,yy);
        ret+=sum(1,n,1,dfn[tp[xx]],dfn[xx]);
        ret%=p;
        xx=fa[tp[xx]];
    }ret+=sum(1,n,1,dfn[xx],dfn[yy]);
    return ret%p;
}

void link_add(int xx,int yy,int v){//树剖加
    while(tp[xx]!=tp[yy]){
        if(depth[tp[xx]]<depth[tp[yy]])swap(xx,yy);
        add(1,n,1,v%p,dfn[tp[xx]],dfn[xx]);
        xx=fa[tp[xx]];
    }add(1,n,1,v,dfn[xx],dfn[yy]);
}

int sub_sum(int xx){//树剖子树和
    return sum(1,n,1,dfn[xx],bottom[xx]);
}

void sub_add(int xx,int v){//树剖子树加
    add(1,n,1,v%p,dfn[xx],bottom[xx]);
}

int main()
{
//  freopen("input.txt","r",stdin);
    cin>>n>>m>>r>>p;
    for(int i=1;i<=n;i++)cin>>val[i];
    for(int i=1;i<n;i++){
        cin>>x>>y;
        Tree[x].push_back(y);
        Tree[y].push_back(x);
    }dfs1(r,1);
    dfs2(r,r);
    build_tree(1,n,1);
    while(m--){
        cin>>op;
        switch(op){
            case 1:{
                cin>>x>>y>>z;
                link_add(x,y,z);
                break;
            }case 2:{
                cin>>x>>y;
                cout<<link_sum(x,y)<<endl;
                break;
            }case 3:{
                cin>>x>>z;
                sub_add(x,z);
                break;
            }case 4:{
                cin>>x;
                cout<<sub_sum(x)<<endl;
                break;
            }default:break;
        }
    }
    return 0;
}