324 树上修改与查询 树链剖分

视频链接：https://www.bilibili.com/video/BV18S4y1e7qb/

// Luogu P3384 【模板】轻重链剖分/树链剖分
#include 
#include 
#include 
#include 
#define lc u<<1
#define rc u<<1|1
using namespace std;

typedef long long LL;
const int N=100010;
int n,m,a,b,root,p;
int w[N];
vector<int> e[N];
int fa[N],dep[N],sz[N],son[N];
int top[N],id[N],nw[N],cnt;

void dfs1(int u,int father){//搞fa,dep,sz,son
  fa[u]=father,dep[u]=dep[father]+1,sz[u]=1;
  for(int v:e[u]){
    if(v==father) continue;
    dfs1(v,u);
    sz[u]+=sz[v];
    if(sz[son[u]]v; 
  }
}
void dfs2(int u,int t){//搞top,id,nw
  top[u]=t,id[u]=++cnt,nw[cnt]=w[u];
  if(!son[u]) return;
  dfs2(son[u],t);
  for(int v:e[u]){
    if(v==fa[u]||v==son[u])continue;
    dfs2(v,v);
  }
}

struct tree{
  int l,r; 
  LL add,sum;
}tr[N*4]; //线段树

void pushup(int u){
  tr[u].sum=tr[lc].sum+tr[rc].sum;
}
void pushdown(int u){
  if(tr[u].add){
    tr[lc].sum+=tr[u].add*(tr[lc].r-tr[lc].l+1);
    tr[rc].sum+=tr[u].add*(tr[rc].r-tr[rc].l+1);
    tr[lc].add+=tr[u].add;
    tr[rc].add+=tr[u].add;
    tr[u].add=0;
  }
}
void build(int u,int l,int r){
  tr[u]={l,r,0,nw[r]};
  if(l==r) return;
  int mid=l+r>>1;
  build(lc,l,mid),build(rc,mid+1,r);
  pushup(u);
}
void update(int u,int l,int r,int k){
  if(l<=tr[u].l&&r>=tr[u].r){
    tr[u].add+=k;
    tr[u].sum+=k*(tr[u].r-tr[u].l+1);
    return;
  }
  pushdown(u);
  int mid=tr[u].l+tr[u].r>>1;
  if(l<=mid) update(lc,l,r,k);
  if(r>mid) update(rc,l,r,k);
  pushup(u);
}
void update_path(int u,int v,int k){
  while(top[u]!=top[v]){
    if(dep[top[u]]<dep[top[v]])swap(u,v);
    update(1,id[top[u]],id[u],k);
    u=fa[top[u]];
  }
  if(dep[u]<dep[v])swap(u,v);
  update(1,id[v],id[u],k);//最后一段
}
void update_tree(int u,int k){
  update(1,id[u],id[u]+sz[u]-1,k);
}
LL query(int u,int l,int r){
  if(l<=tr[u].l&&r>=tr[u].r)return tr[u].sum;
  pushdown(u);
  int mid=tr[u].l+tr[u].r>>1;
  LL res=0;
  if(l<=mid) res+=query(lc,l,r);
  if(r>mid) res+=query(rc,l,r);
  return res;
}
LL query_path(int u,int v){
  LL res=0;
  while(top[u]!=top[v]){
    if(dep[top[u]]<dep[top[v]]) swap(u,v);
    res+=query(1,id[top[u]],id[u]);
    u=fa[top[u]];
  }
  if(dep[u]<dep[v]) swap(u,v);
  res+=query(1,id[v],id[u]);//最后一段
  return res;
}
LL query_tree(int u){
  return query(1,id[u],id[u]+sz[u]-1);
}
int main(){
  scanf("%d%d%d%d",&n,&m,&root,&p);
  for(int i=1; i<=n; i++) 
    scanf("%d",&w[i]);
  for(int i=0; i1; i++){
    scanf("%d%d",&a,&b);
    e[a].push_back(b);
    e[b].push_back(a);
  }
  dfs1(root,0);
  dfs2(root,root);//把树拆成链
  build(1,1,n); //用链建线段树
  while(m--){
    int t,u,v,k;
    scanf("%d%d",&t,&u);
    if(t==1){
      scanf("%d%d",&v,&k);
      update_path(u,v,k);
    }
    else if(t==3){
      scanf("%d",&k);
      update_tree(u,k);
    }
    else if(t==2){
      scanf("%d",&v);
      printf("%d\n",query_path(u,v)%p);
    }
    else printf("%d\n",query_tree(u)%p);
  }
  return 0;
}