树剖模板

jiangjiangQwQ · 2023-08-31 20:21:00 · 算法·理论

题目：P3384 【模板】重链剖分/树链剖分

传送门:P3384 【模板】重链剖分/树链剖分

代码结构剖分

dfs1

• ### $code

  inline void dfs1(int u,int faz){
  dep[u]=dep[faz]+1;//等于父亲的深度+1
  fa[u]=faz;
  sz[u]=1;//初始化子树大小为1，只有自己
  for(auto v:edge[u]){
      if(v==faz) continue;//跳过父亲
      dfs1(v,u);
      sz[u]+=sz[v];//累加子树大小
      if(sz[v]>sz[son[u]]) son[u]=v;//更新重儿子
  }
  }

dfs2

• ### $code

  inline void dfs2(int u,int head){
  id[u]=++cnt;//这个节点的新编号
  nw[cnt]=w[u];
  top[u]=head;
  if(son[u]) dfs2(son[u],head);//优先遍历重儿子
  for(auto v:edge[u]){
      if(v==son[u]||v==fa[u]) continue;
      dfs2(v,v);//轻儿子的链头是自己
  }
  }

  优先遍历重儿子的好处是一条重链上的所有节点编号是连续的。

• 定理

  1. 重链上的点编号连续。
  2. 任意子树的节点编号连续。

所以使用线段树来维护一条重链上的信息。

路径的修改与查询

修改

默认 x 的深度较大，让 x 反复跳向当前所在重链顶端。直到 x 与 y 在同一条重链上。同时对重链上的节点进行线段树区间操作。当满足条件后，还要将 x 与 y 之间的节点修改。

code

inline 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);
}

查询

与修改相差无几。将函数 update 部分改为 query，对重链进行线段树的区间查询。多加几个变量记录查询结果。

code

long long query_path(int u,int v){
    long long ans=0;
   //根据题目要求进行取模
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        ans=(ans%p+query(1,id[top[u]],id[u])%p)%p;
     //只需要将update改query再记录答案
        u=fa[top[u]];
    }
    if(dep[u]<dep[v]) swap(u,v);
    ans=(ans%p+query(1,id[v],id[u])%p)%p;
    return ans;
}

main 函数部分

• 输入每个节点初始权值 w_u。

• 变量 rt 为根节点。

  1. 进行 dfs1(rt,-1)
  2. 进行 dfs2(rt,rt)
  3. 进行 build(1,1,n)，建树。

对于路径 x\to y

直接 update(x,y) 或 query(x,y)。

对于 u 的子树操作

需要操作的范围为 u\to u+size_u-1。