萌新刚学树剖1普朗克时间求吊

rt

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+7;
int N,M,R,P,w[maxn],dep[maxn];
int head[maxn],nxt[maxn],to[maxn],cnt;//邻接表全家桶 
int Fa[maxn],Hd[maxn],Hson[maxn],SZ[maxn],id[maxn];
//树剖全家桶(爹,i的重链头,重儿子,子树大小,在线段树的位置 )
struct node{int l,r,dat,add;}tree[maxn];
void edge(int U,int V){
    nxt[++cnt]=head[U];to[cnt]=V;head[U]=cnt;
    nxt[++cnt]=head[V];to[cnt]=U;head[V]=cnt;
    return;
}
//以下为线段树 
int ls(int p){return p<<1;}
int rs(int p){return p<<1|1;}
int Mid(int l,int r){return (l+r)>>1;}
void build(int l,int r,int p){//建树 
    tree[p].l=l;tree[p].r=r;
    if(l==r){tree[p].dat=w[l];return;}
    int mid=Mid(l,r);
    build(l,mid,ls(p));build(mid+1,r,rs(p));
    tree[p].dat=tree[ls(p)].dat+tree[rs(p)].dat;
    return;
}
void lazy(int p){//懒标记
    if(tree[p].add){
        tree[ls(p)].dat+=tree[p].add*(tree[ls(p)].r-tree[ls(p)].l+1);
        tree[rs(p)].dat+=tree[p].add*(tree[rs(p)].r-tree[rs(p)].l+1);
        tree[ls(p)].add+=tree[p].add;tree[rs(p)].add+=tree[p].add;
        tree[p].add=0; 
    }
    return; 
}
void change(int p,int l,int r,int k){
    //cout<<"changeing L:"<<l<<" R: "<<r<<endl; 
    //cout<<"现在事节点 "<<p<<"从 "<<tree[p].l<<" 到 "<<tree[p].r<<endl;
    if(l<=tree[p].l&&r>=tree[p].r){
        tree[p].dat+=1LL*k*(tree[p].r-tree[p].l+1);
        tree[p].add+=k;
        return;
    }
    int mid=Mid(tree[p].l,tree[p].r);
    if(l<=mid)change(ls(p),l,r,k);
    if(r>mid)change(rs(p),l,r,k);
    tree[p].dat=tree[ls(p)].dat+tree[rs(p)].dat;
    return;
}
long long ask(int p,int l,int r){
    if(l<=tree[p].l&&r>=tree[p].r)return tree[p].dat;
    lazy(p);
    int mid=Mid(tree[p].l,tree[p].r);
    long long ret=0;
    if(l<=mid)ret+=ask(ls(p),l,r);
    if(r>mid)ret+=ask(rs(p),l,r);
    return ret;
}
//线段树部分结束 
//它 来 了
int dfs1(int u,int fa){
    SZ[u]=1;Fa[u]=fa;dep[u]=dep[fa]+1;
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(v!=fa){
            SZ[u]+=dfs1(v,u);
            if(SZ[v]>SZ[Hson[u]])Hson[u]=v;
        }
    }
    return SZ[u]; 
}
void dfs2(int u,int fa,int _H){//当前节点,爹,重链头 
    id[u]=++cnt;Hd[u]=_H;
    if(Hson[u])dfs2(Hson[u],u,_H);
    for(int i=head[u];i;i=nxt[i])
        if(to[i]!=fa&&to[i]!=Hson[u])dfs2(to[i],u,to[i]);
    return;
}
void add(int u,int v,int w){
    while(1){
        int hu=Hd[u],hv=Hd[v];
        if(hu==hv)break;
        if(dep[hu]<dep[hv])swap(u,v),swap(hu,hv);
        change(1,id[hu],id[u],w);u=Fa[hu];
    }
    if(dep[u]<dep[v])swap(u,v);
    change(1,id[v],id[u],w);
    return;
}
//E · N · D 
int main(){
    scanf("%d%d%d%d",&N,&M,&R,&P);
    for(int i=1;i<=N;i++)scanf("%d",&w[i]);
    for(int i=1;i<N;i++){int a,b;scanf("%d%d",&a,&b);edge(a,b);}
    cnt=0;//!!!!!!!
    dfs1(R,0);
    dfs2(R,0,R); 
    build(1,N,1);
    while(M--){
        int op,x,y,z;
        scanf("%d",&op);
        if(op==1){
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,z);
        }else if(op==2){
            scanf("%d%d",&x,&y);
            if(id[x]>id[y])swap(x,y);
            printf("%d\n",ask(1,id[x],id[y])%P);
        }else if(op==3){
            scanf("%d%d",&x,&y);
            change(1,id[x],id[x]+SZ[x]-1,y);
        }else{
            scanf("%d",&x);
            printf("%d\n",ask(1,id[x],id[x]+SZ[x]-1)%P);
        }
    }
    return 0;
}