树链剖分

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<ctime>
#include<cstdlib>
#include<queue>
using namespace std;

struct SegTree{//线段树 
    struct Node{
        long long l,r,val,lazy;
    }tree[400000];
    long long size;
    void build(long long id,long long l,long long r){
        tree[id]=(Node){l,r,0,0};
        if(l==r) return ;
        long long mid=(l+r)/2;
        build(id*2,l,mid);
        build(id*2+1,mid+1,r);
    }
    void lazydown(long long id){
        long long lc=id*2,rc=id*2+1,lazy=tree[id].lazy;
        tree[lc].lazy+=lazy;
        tree[lc].val+=(tree[lc].r-tree[lc].l+1)*lazy;
        tree[rc].lazy+=lazy;
        tree[rc].val+=(tree[rc].r-tree[rc].l+1)*lazy;
        tree[id].lazy=0;
    }
    long long al,ar,aval;
    void update(long long id){
        long long l=tree[id].l,r=tree[id].r;
        if(al<=l&&r<=ar){
            tree[id].lazy+=aval;
            tree[id].val+=(r-l+1)*aval;
            return ;
        }
        if(tree[id].lazy!=0) lazydown(id);
        long long mid=(l+r)/2;
        if(al<=mid) update(id*2);
        if(ar>mid) update(id*2+1);
        tree[id].val=tree[id*2].val+tree[id*2+1].val;
    }
    void afo(long long id){//别问我这个函数名是什么鬼 
        long long l=tree[id].l,r=tree[id].r;
        if(al<=l&&r<=ar){
            aval+=tree[id].val;
            return ;
        }
        if(tree[id].lazy!=0) lazydown(id);
        long long mid=(l+r)/2;
        if(al<=mid) afo(id*2);
        if(ar>mid) afo(id*2+1);
    }
    //for user 
    void init(long long mys){
        size=mys;
        build(1,1,size);
    }
    void change(long long l,long long r,long long val){
        al=l;ar=r;aval=val;
        update(1);
    }
    long long ask(long long l,long long r){
        al=l;ar=r;aval=0;
        afo(1);
        return aval;
    }
};
long long n,qn,root,MOD;

struct star{//链式前向星存树 
    long long u,v;
}edge[400000];
long long last[400000],nxt[400000],m;
void addedge(long long u,long long v){
    m++;
    edge[m]=(star){u,v};
    nxt[m]=last[u];
    last[u]=m;
}

long long prt[400000],dep[400000],size[400000],
    son[400000],top[400000],rk[400000],rkn;
void dfs1(long long id,long long fa,long long d){//第一遍dfs，处理prt,dep,size,son 
    prt[id]=fa;
    dep[id]=d;
    size[id]=1;
    long long fat=-1;
    for(long long i=last[id];i!=-1;i=nxt[i]){
        long long to=edge[i].v;
        if(to==fa) continue;
        dfs1(to,id,d+1);
        size[id]+=size[to];
        if(fat==-1) fat=to;
        else if(size[to]>size[fat]) fat=to;
    }
    son[id]=fat;
}
void dfs2(long long id,long long tp){//第二遍dfs，处理top,rk 
    rkn++;rk[id]=rkn;
    top[id]=tp;
    if(son[id]==-1) return;
    dfs2(son[id],tp);
    for(long long i=last[id];i!=-1;i=nxt[i]){
        long long to=edge[i].v;
        if(to==prt[id]||to==son[id]) continue;
        dfs2(to,to);
    }
}
SegTree seg;

void change(long long px,long long py,long long val){//操作1 
    for(;top[px]!=top[py];){
        if(dep[top[px]]<dep[top[py]]) swap(px,py);//注意应比较top[px]和top[py]的深度，而不是px和py的深度 
        long long fx=top[px],fy=top[py];
        if(prt[fx]!=-1){//如果top不是根节点
            seg.change(rk[fx],rk[px],val);
            px=prt[fx];
        }
    }
    if(rk[px]>rk[py]) swap(px,py);//就是这里忘swap了害得我调了1hour 
    seg.change(rk[px],rk[py],val);
}
long long ask(long long px,long long py){//操作2 
    long long ans=0;
    for(;top[px]!=top[py];){
        if(dep[top[px]]<dep[top[py]]) swap(px,py);
        long long fx=top[px],fy=top[py];
        if(prt[fx]!=-1){
            ans+=seg.ask(rk[fx],rk[px]);
            px=prt[fx];
        }
    }
    if(rk[px]>rk[py]) swap(px,py);
    ans+=seg.ask(rk[px],rk[py]);
    return ans;
}

long long stv[400000];
int main(){
    cin>>n>>qn>>root>>MOD;
    seg.init(n);
    for(long long i=1;i<=n;i++){
        scanf("%lld",&stv[i]);
    }
    m=0;
    for(long long i=1;i<=n;i++) last[i]=-1;
    for(long long i=1;i<=n-1;i++){
        long long u,v;
        scanf("%lld%lld",&u,&v);
        addedge(u,v);
        addedge(v,u);
    }
    dfs1(root,-1,1);
    rkn=0;
    dfs2(root,root);
    for(long long i=1;i<=n;i++){
        seg.change(rk[i],rk[i],stv[i]);
    }
    for(long long i=1;i<=qn;i++){
        long long type,l,r,val;
        scanf("%lld",&type);
        switch(type){
            case 1:{
                scanf("%lld%lld%lld",&l,&r,&val);
                change(l,r,val);
                break;
            }
            case 2:{
                scanf("%lld%lld",&l,&r);
                printf("%lld\n",ask(l,r)%MOD);
                break;
            }
            case 3:{
                scanf("%lld%lld",&l,&val);
                r=rk[l]+size[l]-1;
                l=rk[l];
                seg.change(l,r,val);
                break;
            }
            case 4:{
                scanf("%lld",&l);
                r=rk[l]+size[l]-1;
                l=rk[l];
                printf("%lld\n",seg.ask(l,r)%MOD);
                break;
            }
        }
    }
    return 0;
}