树链剖分——将一棵树解剖成链

如何将一棵树剖成链

树链剖分可以将一棵有nn个节点的树在两次时间复杂度为O(n)O(n)的操作里将一颗树剖成一条长度为nn的链,我们可以在上面建立线段树等数据结构来维护这颗树。

树链剖分通常有重链剖分、长链剖分和随机剖分等实现,它们的时间复杂度都差不多,且一般使用的为重链剖分,因此在这里只介绍重链剖分。

概念引入

一个点的"重量":指这个点的子树的点的个数之和

重儿子:当前节点的所有儿子节点中最重的一个

重边:当前节点连接重儿子的边

轻边:当前节点连接非重儿子的边

dfndfn序:使用dfsdfs按照先枚举重儿子再枚举轻儿子得到的dfsdfs

那么我们怎么来建树呢?

第一个DFS——求重量及深度

我们可以写一个dfsdfs,枚举当前节点的子节点,计算出所有子节点的重量,再根据子节点的重量计算出当前节点的重量并求出重儿子,深度则可以通过父节点的深度+1来实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void build1(const gg &p)
{
gg tpcnt=cnt;
cnt++;
dep[p]=dep[fa[p]]+1;
flag[p]=true;
for(gg i=0;i<tp[p].size();i++) //当时还不会链式前向星QAQ
{
if(!flag[tp[p][i]])
{
fa[tp[p][i]]=p;
build1(tp[p][i]);
if(siz[son[p]]<=siz[tp[p][i]]) son[p]=tp[p][i];
}
}
siz[p]=cnt-tpcnt;
return;
}

第二个DFS——求DFN序以及链顶

再写一个dfsdfs,用于求dfndfn序和链顶,每次先枚举重儿子,这样就可以保证一条链上的dfndfn序是连续的,然后还可以给每个重儿子继承链顶的序号,代表当前这条链的链顶。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void build2(const gg &p,const gg &v)
{
cnt++;
top[p]=v;
dfn[p]=cnt;
rnk[cnt]=p;
if(!son[p])
{
return;
}
build2(son[p],v);
for(gg i=0;i<tp[p].size();i++)
{
if(tp[p][i]!=son[p]&&fa[tp[p][i]]==p)
{
build2(tp[p][i],tp[p][i]);
}
}
return;
}

以下是一棵剖好的树。

一棵被OI-Wiki剖好的树(树:QAQ)

树链剖分の妙用

1.求LCA

思想:

我们只需要判断两个点是否在同一条链上,如果不在,则选择链顶最深的一个进行跳链,跳到这条链的链顶的父节点,等到两个节点在同一条链上时,深度最小的那个节点即为这两个点的LCA。

代码实现-时间复杂度O(logn)O(logn)
1
2
3
4
5
6
7
8
9
gg lca(gg &x,gg &y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=fa[top[x]];
}
return dep[x]>dep[y]?y:x;
}
练习:

P3379 【模板】最近公共祖先(LCA)

P3258 [JLOI2014]松鼠的新家

P3398 仓鼠找 sugar

2.在树上建立线段树

思想:

没啥好说的,就是在求出的dfndfn序上建线段树,资瓷了树上区间操作,可以求子树和、LCA路径和之类的操作,复杂度大概也是O(logn)O(logn)

代码实现-时间复杂度O(???)O(???)
1
看操作建不同的线段树吧。
练习:

P3384 【模板】轻重链剖分/树链剖分

P5556 圣剑护符 - 洛谷

THE END - 感谢阅读!