【模板】树链剖分(Luogu P3384)

题目描述

众所周知

树链剖分是个好东西QWQ

也是一个代码量破百的算法

 

基本定义

树路径信息维护算法。

 

ž将一棵树划分成若干条链,用数据结构去维护每条链,复杂度为O(logN)。

 

其实本质是一些数据结构/算法在树上的推广
 
华丽的分割线———————————————————————————————————–
 
【模板】树链剖分(Luogu P3384)

 

 
【模板】树链剖分(Luogu P3384)
 

具体步骤

预处理
第一遍dfs求出树每个结点的深度deep[x],其为根的子树大小size[x]
以及祖先的信息fa[x][i]表示x往上距离为2^i的祖先
第二遍dfs
ž根节点为起点,向下拓展构建重链
选择最大的一个子树的根继承当前重链
其余节点,都以该节点为起点向下重新拉一条重链
ž给每个结点分配一个位置编号,每条重链就相当于一段区间,用数据结构去维护。
把所有的重链首尾相接,放到同一个数据结构上,然后维护这一个整体即可
修改操作
ž1、单独修改一个点的权值
根据其编号直接在数据结构中修改就行了。
2、修改点u和点v的路径上的权值
(1)若u和v在同一条重链上
直接用数据结构修改pos[u]至pos[v]间的值。
(2)若u和v不在同一条重链上
一边进行修改,一边将u和v往同一条重链上靠,然后就变成了情况(1)。
 
具体代码
 
#include<bits/stdc++.h>  using namespace std;  template <typename T> inline void read(T &x)  {      x=0;int f=1;char c=getchar();      for(;c>'9'||c<'0';c=getchar()) if(c=='-') f=-1;      for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);      x*=f;  }  template <typename T> inline void print(T x)  {      if(x<0) putchar('-'),x=-x;      if(x>9) print(x/10);      putchar(x%10+48);  }  int tree[1010001],lazy[1010101];  struct ss{      int v;      int next;      int u;  };  ss s1[1010001];  int head[1101001],cnt;  int w[1010101],wt[1010101];  int n,m,r,mod;  int res=0;  int son[1010101],id[1010101],fa[1010101],tot,deep[1010100],size[1010101],top[1010010];  //--------------------------------------  inline void build(int rt,int l,int r)  {      if(l==r)      {          tree[rt]=wt[l];          tree[rt]%=mod;          return;      }      int mid=(l+r)>>1;      build(rt<<1,l,mid);      build(rt<<1|1,mid+1,r);      tree[rt]=(tree[rt<<1]+tree[rt<<1|1])%mod;  }  inline void pushdown(int rt,int len)  {      lazy[rt<<1]+=lazy[rt];      lazy[rt<<1|1]+=lazy[rt];      tree[rt<<1]+=lazy[rt]*(len-(len>>1));      tree[rt<<1|1]+=lazy[rt]*(len>>1);      tree[rt<<1]%=mod;      tree[rt<<1|1]%=mod;      lazy[rt]=0;  }  inline void query(int rt,int l,int r,int L,int R)  {      int mid=(l+r)>>1;      if(L<=l&&r<=R)      {          res+=tree[rt],res%=mod;          return;      }      else      {          if(lazy[rt])              pushdown(rt,(r-l+1));          if(L<=mid)              query(rt<<1,l,mid,L,R);          if(R>mid)              query(rt<<1|1,mid+1,r,L,R);      }  }  inline void update(int rt,int l,int r,int L,int R,int k)  {      int mid=(l+r)>>1;      if(L<=l&&r<=R)          lazy[rt]+=k,tree[rt]+=k*(r-l+1);      else      {          if(lazy[rt])              pushdown(rt,r-l+1);          if(L<=mid)              update(rt<<1,l,mid,L,R,k);          if(R>mid)              update(rt<<1|1,mid+1,r,L,R,k);          tree[rt]=(tree[rt<<1]+tree[rt<<1|1])%mod;      }  }  //--------------------------------------  inline void abb(int x,int y)  {      cnt++;      s1[cnt].u=x;      s1[cnt].v=y;      s1[cnt].next=head[x];      head[x]=cnt;  }  inline void DFS(int x,int f,int dep)  {      deep[x]=dep;      fa[x]=f;      size[x]=1;      int MAXX=-1;      for(register int i=head[x];i;i=s1[i].next)      {          int v=s1[i].v;          if(v==f)              continue;          DFS(v,x,dep+1);          size[x]+=size[v];          if(size[v]>MAXX)              son[x]=v,MAXX=size[v];      }  }  inline void DFS_(int x,int TOP)  {      id[x]=++tot;      wt[tot]=w[x];      top[x]=TOP;      if(!son[x])          return;      DFS_(son[x],TOP);      for(register int i=head[x];i;i=s1[i].next)      {          int v=s1[i].v;          if(v==fa[x]||v==son[x])              continue;          DFS_(v,v);      }  }  //--------------------------------------------  inline int qSon(int x)  {      res=0;      query(1,1,n,id[x],id[x]+size[x]-1);      return res;  }  inline void updSon(int x,int k)  {      update(1,1,n,id[x],id[x]+size[x]-1,k);  }  inline void updRange(int x,int y,int k)  {      k%=mod;      while(top[x]!=top[y])      {          if(deep[top[x]]<deep[top[y]])              swap(x,y);          update(1,1,n,id[top[x]],id[x],k);          x=fa[top[x]];      }      if(deep[x]>deep[y])          swap(x,y);      update(1,1,n,id[x],id[y],k);  }  inline int qRange(int x,int y)  {      int ans=0;      while(top[x]!=top[y])      {          if(deep[top[x]]<deep[top[y]])              swap(x,y);          res=0,query(1,1,n,id[top[x]],id[x]),ans+=res,ans%=mod,x=fa[top[x]];      }      if(deep[x]>deep[y])          swap(x,y);      res=0,query(1,1,n,id[x],id[y]),ans+=res;      return ans%mod;  }  int main()  {      read(n),read(m),read(r),read(mod);      for(register int i=1;i<=n;++i)          read(w[i]);      for(register int i=1,a,b;i<n;++i)          read(a),read(b),abb(a,b),abb(b,a);      DFS(r,0,1);      DFS_(r,r);      build(1,1,n);      while(m--)      {          int a,b,c,q;          read(q);          if(q==1)              read(a),read(b),read(c),updRange(a,b,c);          else if(q==2)              read(a),read(b),print(qRange(a,b)),putchar('n');          else if(q==3)              read(a),read(b),updSon(a,b);          else              read(a),print(qSon(a)),putchar('n');      }      return 0;  }

 

 

 

未经允许不得转载:杂烩网 » 【模板】树链剖分(Luogu P3384)

评论 0

#快捷签到点我#

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

置顶文章