树链剖分（重链剖分法）

几何微粒子 · 2023-05-09 22:42:13 · 个人记录

简单的讲一下重剖。

模板题：ZJOI 2008 树的统计 + USACO 2011 Dec Gold 种草

Chapter Former 声明

在此之前，我们先声明以下定义：

重儿子：一个节点的子树大小最大的子节点

重边：链接重儿子的边（自然而然，轻边就是树中不是重边的边）

重链：一堆重儿子和重边组成的链。为了避免一个点的特殊情况，我们规定一个单独的点也成一个重链。

接下来是树剖的代码思路：

Chapter I 处理重链

第一步：找重儿子和重边

首先我们需要找到重儿子。我们用一个深搜来遍历整棵树，找到每个节点的重儿子。

判断搜到的新的子节点是否是这个节点的当前真正重儿子的方法：计算子树大小，然后比较。

在遍历每个子节点时，这个节点的子树大小要加上节点的子树大小。一开始每个节点的子树大小都为1

代码写起来是这样的：

void dfs1(int x,int fath){
    siz[x]=1;//初始大小 
    for(int i=head[x];i;i=edge[i].next){//链式前向星存图 
        int exi=edge[i].to;
        if(exi!=fath){//查回父亲也有可能 
            dfs1(exi,x);
            siz[x]+=siz[exi];
            if(siz[son[x]]<siz[exi]){//如果当前已知重儿子的子树大小比该子节点子树大小小 
                son[x]=exi;//替换重儿子 
            }
        }
    } 
}

为后续方便，我们需要处理dep数组（存储每个节点的深度）和fa数组（每个节点的父亲），所以可以一并写进这个dfs里：

void dfs1(int x,int fath,int depth){
    siz[x]=1;//初始大小 
    fa[x]=fath;//写好父亲 
    dep[x]=depth;//写好深度 
    for(int i=head[x];i;i=edge[i].next){//链式前向星存图 
        int exi=edge[i].to;
        if(exi!=fath){//查回父亲也有可能 
            dfs1(exi,x,depth+1);//更深一层 
            siz[x]+=siz[exi];
            if(siz[son[x]]<siz[exi]){//如果当前已知重儿子的子树大小比该子节点子树大小小 
                son[x]=exi;//替换重儿子 
            }
        }
    } 
}

第二步：链接重边，形成重链并计算各种值

为了方便后续操作，我们还需要建立一个关于节点的新的dfn序，以及存储每个节点的重链顶端节点（为了后面跳lca）。

所以我们需要再写个dfs，处理重链，新的dfn序，以及存储每个节点的重链定端节点。

void dfs2(int x,int nowtop){
    dfn[x]=++labor;//labor用于辅助给dfn赋值 
    top[x]=nowtop;//当前节点的重链顶端
    if(!son[x])
        return;//叶子结点，因为没有重儿子，所以没有儿子。
    dfs2(son[x],nowtop);//为了保证dfn序可以在重链上连续，我们优先搜索重儿子
    for(int i=head[x];i;i=edge[i].next){
        int exi=edge[i].to;
        if(exi!=fa[x]&&exi!=son[x]){
            dfs2(exi,exi);//从exi开始，开辟一条新的重链，链顶为exi自身 
        }
    } 
}

Chapter II 维护重链

那么接下来我们需要维护重链。那怎么维护啊？

剖分完之后，我们发现，每条重链就相当于一段编号连续的区间，用数据结构 (比如线段树和平衡树~~这种恶俗东西~~)去维护。

把所有的重链首尾相接，放到同一个数据结构上，然后维护这一个整体即可。

Chapter III 修改查询

最后是修改和查询。

单独修改一个点的权值

根据新的编号直接在数据结构中修改就行了。

修改从 u 到 v 的路径上（含 u,v）每个点的权值

我们分类讨论。

如果 u,v 在同一条重链上

此时可以直接用数据结构修改 dfn_u,dfn_v 一段的值。
```
if(dep[v]>dep[u])swap(v,u);
Modify_SegTree(dfn[v],dfn[u]);
```
如果 u,v 不在同一条重链上

我们就想方设法把 u,v 往一条重链上套。在套的过程中，一边修改沿途路径。最后按照 u,v 在同一条重链上的处理方法处理一次即可完成修改。

那么怎么把 u,v 往同一条重链上套？

我们~~最喜欢套娃~~分类讨论。
- 若 u 所在的重链的父亲（记作 w）与v在同一条重链上。
  
  此时可以修改 u,w 之间的权值，再对于 w,v 执行“在同一条重链上的操作”即可。
  
  也就是说，让 u 直接跳到 v 所在的重链上，然后变成“u,v 在同一条重链上”的情况。
```
Modify_SegTree(dfn[top[u]],dfn[u]);
u=fa[top[u]];
if(dep[v]>dep[u])swap(v,u);
Modify_SegTree(dfn[v],dfn[u]);
```
- 若 w 和 v 不在一条重链上
  
  那就一直重复以下操作：
  - 找到重链顶端（记作 top_u）
  - 修改 u,top_u 路径上的点的权值
  - 跳转 u 到 w（w = top_u 的父亲节点）
  直到 u 与 v 在同一条重链上，然后处理即可。
```
while(top[v]!=top[u])
{
Change_SegTree(dfn[top[u]],dfn[u]);
u=fa[top[u]];
}
if(dep[v]>dep[u])swap(v,u);
Change_SegTree(dfn[v],dfn[u]);
```
- 若 u 和 v 都需要往上跳重链才能满足 u 与 v 在同一条重链上
  
  此时按照LCA的思路，每次选择深度大的点，进行“找到重链顶端修改权值跳转 u ”的操作，直到 u 与 v 在同一条重链上，然后处理即可。
```
while(top[v]!=top[u])
{
if (dep[top[v]]<dep[top[u]])swap(v,u); 
Modify_SegTree(dfn[top[v]],dfn[v]); 
v=fa[top[v]]; 
}
if(dep[v]>dep[u])swap(v,u);
Change_SegTree(dfn[v],dfn[u]);
```

经过上述漫长的讨论，我们发现，之前的所有情况不过都是最后一种情况的特殊情况而已，所以在实际写题中，我们只需要使用最后一种情况的代码即可。

如果要和之前的dfs码与之后的询问并在一起，可以使用以下代码：

void modifyX (int x, int y ,int d) //将x到y路径上的所有点的权值修改为d
{
  while(top[x]!=top[y])
  {
    if (dep[top[x]]<dep[top[y]])swap(x,y); //选深度大的点往上跳
    modify(dfn[top[x]],dfn[x],d);
    //修改存储重链的数据结构,将指定区间的值改为d
    x=fa[top[x]]; //X往上跳
  }
  if(dep[x]>dep[y])swap (x,y);
  modify(dfn[x],dfn[y],d);
}

其中 modify 也就是 Modify_Segtree ，修改线段树

询问

对于询问一个节点和询问一段路径，思路参照修改。

int queryX(int x,int y) //比如查询x到y路径上点权总和
{
  int Sum=0;
  while(top[x]!=top[y])
  {
  if(dep[top[x]]<dep[top[y]])swap(x,y);
  Sum+=query(dfn[top[x]],dfn[x]);
  x=fa[top[x]];
  }
  if(dep[x]>dep[y])swap(x,y);
  Sum+=query(dfn[x],dfn[y]);
return Sum;
}

其中 query 同理，是修改线段树（Query_Segtree）

Chapter IV 创意工坊

下列是树剖的各个拓展用法：

求LCA

在树剖过程中，我们会求到两个点的LCA，此时可以借机写一份求LCA的代码。

int getLCA(int x,int y)
{
  while(top[x]!=top[y])
  {
  if(dep[top[x]]<dep[top[y]])swap(x,y);
  x=fa[top[x]];
  }
  if(dep[x]>dep[y])swap(x,y);
  return x;
}

Chapter V 总结

树链剖分：把树的边映射到线段树上的数据结构。

求重链：用两个dfs处理树的信息，重边以及轻边，然后链接重链。

修改和查询：重复往上，一条一条重链地跳，找到LCA，途中用数据结构边跳边修/查。