洛谷 P3384 【模闆】樹鍊剖分

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

#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
const int maxn=100000+100;

struct Edge{
  
  int to,next;
}edge[maxn*2];
int head[maxn],tot;
int fa[maxn],size[maxn],son[maxn],du[maxn],id[maxn],rev[maxn],top[maxn],maxid[maxn],cnt;
int n,m,root,p;
int ans[maxn];
int tree[maxn<<2],add[maxn<<2];

void DFS1(int f,int u,int d){
  
  fa[u]=f;du[u]=d;size[u]=1;
  for(int i=head[u];i!=-1;i=edge[i].next){
    
    Edge e=edge[i];
    int v=e.to;
    if(v==f) continue;
    DFS1(u,v,d+1);
    size[u]+=size[v];
    if(size[son[u]]<size[v]) son[u]=v;
  }
}

void DFS2(int t,int u){
  
  top[u]=t;id[u]= ++cnt;rev[cnt]=u;maxid[u]=cnt;
  if(!son[u]) return ;
  DFS2(t,son[u]);
  maxid[u]=max(maxid[u],maxid[son[u]]);
  for(int i=head[u];i!=-1;i=edge[i].next){
    
    Edge e=edge[i];
    int v=e.to;
    if(v==fa[u] || v==son[u]) continue;
    DFS2(v,v);
    maxid[u]=max(maxid[u],maxid[v]);
  }
}

void build(int rt,int l,int r){
  
  if(l==r){
    
    tree[rt]=ans[rev[l]];
    return ;
  }
  int mid=(l+r)>>1;
  build(lson);
  build(rson);
  tree[rt]=(tree[rt<<1]+tree[rt<<1|1])%p;
}

inline void updateup(int rt,int l,int r,int mid){
  
  if(add[rt]){
    
    add[rt<<1]+=add[rt];add[rt<<1]%=p;
    add[rt<<1|1]+=add[rt];add[rt<<1|1]%=p;
    tree[rt<<1]+=add[rt]*(mid-l+1);tree[rt<<1]%=p;
    tree[rt<<1|1]+=add[rt]*(r-mid);tree[rt<<1|1]%=p;
    add[rt]=0;
  }
}

inline void update(int rt,int l,int r,int L,int R,int v){
  
  if(L>r || R<l) return ; 
  if(L<=l && R>=r){
    
    add[rt]+=v;add[rt]%=p;
    tree[rt]+=v*(r-l+1);tree[rt]%=p;
    return ;
  }
  int mid=(l+r)>>1;
  updateup(rt,l,r,mid);
  update(lson,L,R,v);
  update(rson,L,R,v);
  tree[rt]=(tree[rt<<1]+tree[rt<<1|1])%p;
}

inline int query(int rt,int l,int r,int L,int R){
  
  if(L>r || R<l) return 0;
  if(L<=l && R>=r) return tree[rt];
  int mid=(l+r)>>1;
  updateup(rt,l,r,mid);
  return (query(lson,L,R)+query(rson,L,R))%p;
}

inline int getSum(int u,int v){
  
  int sum=0;
  while(top[u]!=top[v]){
    
    if(du[top[u]]<du[top[v]]) swap(u,v);
    sum+=query(1,1,n,id[top[u]],id[u]);sum%=p;
    u=fa[top[u]];
  }
  return (sum+query(1,1,n,min(id[u],id[v]),max(id[u],id[v])))%p;
}

inline void update1(int u,int v,int val){
  
  while(top[u]!=top[v]){
    
    if(du[top[u]]<du[top[v]]) swap(u,v);
    update(1,1,n,id[top[u]],id[u],val);
    u=fa[top[u]];
  }
  update(1,1,n,min(id[u],id[v]),max(id[u],id[v]),val);
}

inline int getTreeSum(int rt){
  
  return query(1,1,n,id[rt],maxid[rt])%p;
}

inline void update2(int rt,int val){
  
  update(1,1,n,id[rt],maxid[rt],val);
}

int main(){
  
  scanf("%d%d%d%d",&n,&m,&root,&p);
  for(int i=1;i<=n;i++) scanf("%d",&ans[i]);
  for(int i=1;i<=n;i++) head[i]=-1;
  for(int i=1;i<n;i++){
    
    int u,v;
    scanf("%d%d",&u,&v);
    edge[tot].to=v;
    edge[tot].next=head[u];
    head[u]=tot++;
    edge[tot].to=u;
    edge[tot].next=head[v];
    head[v]=tot++;
  }
  DFS1(-1,root,1);
  DFS2(root,root);
  build(1,1,n);
  while(m--){
    
    int type;
    scanf("%d",&type);
    if(type==1){
      
      int u,v,val;
      scanf("%d%d%d",&u,&v,&val);
      update1(u,v,val);
    }
    else if(type==2){
      
      int u,v;
      scanf("%d%d",&u,&v);
      printf("%d\n",getSum(u,v));
    }
    else if(type==3){
      
      int rt,val;
      scanf("%d%d",&rt,&val);
      update2(rt,val);
    }
    else{
      
      int rt;
      scanf("%d",&rt);
      printf("%d\n",getTreeSum(rt));
    }
  }
}