树链剖分

什么是树链剖分?

一句话概括:把一棵树剖分为若干条链,然后利用数据结构(树状数组,SBT,Splay,线段树等)去维护每一条链,复杂度为O(logn).

定义

重边与轻边:定义size(x)为以x为根的子树节点个数,令v为u的儿子中size值最大的节点,那么(u,v)就是重边,其余边为轻边.

性质

  • 轻边(u,v)中,size(v)<=size(u/2).
  • 从根到某一点的路径上,不超过logn条轻边和不超过logn条重路径.

步骤

步骤1:对树进行轻重边的划分

两次dfs.
第一次dfs找重边,也就是记录下所有的重边.
第二次dfs链接重边成重链,即:以根节点为起点,沿着重边向下拓展,拉成重链,不在当前重链上的节点都以该节点为起点向下重新拉一条重链.


剖分完毕后,每条重链相当于一段区间,然后用数据结构去维护,把所有重链首尾相接,放到数据结构上,然后维护整体.

在这里,当然有很多数组,现在我来分别介绍它们的作用:

siz[]数组:用来保存以x为根的子树节点个数
top[]数组:用来保存当前节点的所在链的顶端节点
son[]数组:用来保存重儿子
dep[]数组:用来保存当前节点的深度
fa[]数组:用来保存当前节点的父亲
tid[]数组:用来保存树中每个节点剖分后的新编号
rank[]数组:用来保存当前节点在线段树中的位置

代码实现:
第一次dfs:记录所有的重边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void dfs1(int u,int father,int d)  
{
dep[u]=d;
fa[u]=father;
siz[u]=1;
for(int i=head[u];~i;i=next[i])
{
int v=to[i];
if(v!=father)
{
dfs1(v,u,d+1);
siz[u]+=siz[v];
if(son[u]==-1||siz[v]>siz[son[u]])
son[u]=v;
}
}
}

第二次dfs:连重边成重链

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void dfs2(int u,int tp)  
{
top[u]=tp;
tid[u]=++tim;
rank[tid[u]]=u;
if(son[u]==-1) return;
dfs2(son[u],tp);
for(int i=head[u];~i;i=next[i])
{
int v=to[i];
if(v!=son[u]&&v!=fa[u])
dfs2(v,v);
}
}


这里面还有一个重要的操作,那就是修改树中边权的值.
有两种情况:

  1. 如果u与v在同一条重链上,那么就直接修改了
  2. 如果u与v不在同一条重链上,那么就一边进行修改,一边将u与v往同一条重链上靠,这样就变成了第一种情况了

余下的留坑待补

显示 Gitment 评论