树剖

烛木 · 2020-10-21 22:41:05 · 个人记录

介绍

树剖主要作用可以理解为对一棵树进行类似于线段树的操作。（废话）

主要是通过一些神奇操作将一棵树转化为多个链（可以理解为多个线段树），并且在这多个链中反复跳跃，完成以下几个操作：

将x到y的最短路上的结点都加上a
计算x到y的最短路上的结点值的和
将x的子树上的结点（包括x）都加上a
计算x的子树上的结点（包括x）值的和

（~~其实还有些操作比如求最大值之类的，不过都可自行理解~~）

那么问题来了，我们如何在各个链间反复跳跃呢？

主要内容

几个概念

重儿子（可理解为很重要的儿子，因为真的很重要（雾））：一个结点的重儿子，就是以此结点的各个儿子为根的子树中，结点最多的那棵树的根。

轻儿子：显而易见，不是重儿子的结点就是轻儿子。

重边：一个结点连接其重儿子的边。

轻边：依然显而易见，不是重边的边就是轻边。

重链：几条相连重边组成的链。
- 注：重链起点均为轻儿子。
直接上图

由这个图则可以看出一些有趣的东西：
- 除了重链就是轻儿子叶节点，而这些轻儿子叶结点也会单独构成重链（虽然只有一个结点而没边，但它就是重链）
- 看似毫无意义的轻边作用为连接不同的链
几个数组

注：事实上到这里直接摆几个数组任谁也看不懂，先大概记住每个数组存了啥，结合后面再来理解

fa[MAXN] : 存储此结点的父亲结点

deep[MAXN] ：存储此结点的深度

size[MAXN] ：存储以此结点为根的树的结点个数

son[MAXN] : 存储此结点的重儿子

top[MAXN] : 存储此结点所在链的起点

id[MAXN] : 存储此结点在dfs树的标号（dfs树在倍增求lca中就学了）

di[MAXN] : 存储dfs树的各个标号所对应的结点，即与id[MAXN]数组的下标和存的东西相反（所以这个数组我取名为di）。
- 注：此数组（di[MAXN]）唯一作用为建线段树，所以若题目无初始化每个结点的值（即均为0），则无需此数组。

几个函数

dfs1 ：初始化fa,deep,son数组。

inline void dfs1(int x,int f) //x为当前结点，f为父亲结点
{
     size[x]=1,deep[x]=deep[f]+1,fa[x]=f;
     for(int i=p[x].first;i;i=p[i].next)
     {
         int y=p[i].go;
         if(y==f) continue;//作为无向图，防止在两个结点中反复横跳
         dfs1(y,x);
         size[x]+=size[y];//显而易见，各个子树大小的和加上根这一结点就是此树的结点数
         if(size[y]>size[son[x]]) son[x]=y; //不断比较求得重儿子 
     }
}

dfs2 ：初始化id,di,top数组。

int dotot;//dfs树搜索顺序 
inline void dfs2(int x,int topf) //x为当前结点，topf是此链的开头结点
{
     id[x]=++dotot,di[dotot]=x,top[x]=topf;
     if(!son[x]) return ;//搜到叶节点就返回
     dfs2(son[x],topf);//这里是优先搜重儿子
     for(int i=p[x].first;i;i=p[i].next)
     {
         int y=p[i].go;
         if(y!=son[x]&&y!=fa[x]) dfs2(y,y);//当一个儿子结点没有top时，则此结点非重儿子，那么就是一条新链的起点 
     }
}

再次强调，这里优先搜重儿子，具体体现在下图

build && down && update && answer ：原线段树的四个函数，用于对一棵树进行修改与查询，因写法只需改动少许即放到一处处理。

//线段树与大众写法略有不同，不过不影响树剖学习 
inline void build(int k,int x,int y)
{
     l[k]=x,r[k]=y;
     if(x==y)
     {
         imp[k]=ord[di[x]];//此处即用上di数组
         return ;
     }
     int mid=(x+y)>>1;
     build(k<<1,x,mid);
     build(k<<1|1,mid+1,y);
     imp[k]=imp[k<<1]+imp[k<<1|1]; 
}
inline void down(int k)
{
     if(!add[k]) return ;
     add[k<<1]+=add[k];
     add[k<<1|1]+=add[k];
     imp[k<<1]+=(r[k<<1]-l[k<<1]+1)*add[k];
     imp[k<<1|1]+=(r[k<<1|1]-l[k<<1|1]+1)*add[k];
     add[k]=0;
}//毫无变化
inline void update(int k,int x,int y,int a)
{
     if(x<=l[k]&&y>=r[k])
     {
         add[k]+=a;
         imp[k]+=(r[k]-l[k]+1)*a;
         return ;
     }
     down(k);
     if(x<=r[k<<1]) update(k<<1,x,y,a);
     if(y>=l[k<<1|1]) update(k<<1|1,x,y,a);
     imp[k]=imp[k<<1]+imp[k<<1|1];
}//毫无变化
inline int answer(int k,int x,int y)
{
     if(x<=l[k]&&y>=r[k]) return imp[k];
     down(k);
     int ans=0;
     if(x<=r[k<<1]) ans+=answer(k<<1,x,y);
     if(y>=l[k<<1|1]) ans+=answer(k<<1|1,x,y);
     return ans;
}//毫无变化

upchain && anschain : 相对线段树所新增的两个函数，实现两点间最短路的修改与查询。放在一块处理也是因为差别不大

inline void upchain(int x,int y,int a)
{
     while(top[x]!=top[y])//将x(较深的点)向上爬到和y(较浅的点)同一条链 
     {
         if(deep[top[x]]<deep[top[y]]) swap(x,y);//保持x为较深点便于操作 
         update(1,id[top[x]],id[x],a);//更新x向上爬时经过的点，每次更新一条链
         x=fa[top[x]];//跳到下一条链 
     }
     if(deep[x]>deep[y]) swap(x,y);
     update(1,id[x],id[y],a);//此时两点在同一条链上，则直接修改 
}
//其实修改和查询区别就两行。。。。 
inline void anschain(int x,int y)
{
     int ans=0; 
     while(top[x]!=top[y])
     {
         if(deep[top[x]]<deep[top[y]]) swap(x,y);
         ans+=answer(1,id[top[x]],id[x]);
         x=fa[top[x]];
     }
     if(deep[x]>deep[y]) swap(x,y);
     ans+=answer(1,id[x],id[y]);
     return ans;
}

主函数

主函数要处理的则是关于这四个问题的函数调用。
1. 树修改&&树查询：
```
 update(1,id[x],id[x]+size[x]-1,a);
 answer(1,id[x],id[x]+size[x]-1);
```
对于 id[x]+size[x]-1 这一部分，其实在dfs2时就可见：一棵子树的各个结点所对应在dfs树上的序号是一个区间内递增的。

对这句话的理解，举例子：一颗子树的序号可以为
- 2,3,4,5
- 5,6,7,8,9,10,11
- 6
（应该举例就很好理解了）

配合图理解

2.两点修改&&两点查询：
```
upchain(x,y,a);
anschain(x,y);
```
这倒是很直白。

树剖

介绍

将x到y的最短路上的结点都加上a

计算x到y的最短路上的结点值的和

将x的子树上的结点（包括x）都加上a

计算x的子树上的结点（包括x）值的和

那么问题来了，我们如何在各个链间反复跳跃呢？

主要内容

几个概念

除了重链就是轻儿子叶节点，而这些轻儿子叶结点也会单独构成重链（虽然只有一个结点而没边，但它就是重链）

看似毫无意义的轻边作用为连接不同的链

几个数组

几个函数

主函数