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

如何将一棵树剖成链

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

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

概念引入

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

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

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

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

$dfn$序：使用$dfs$按照先枚举重儿子再枚举轻儿子得到的$dfs$序

那么我们怎么来建树呢？

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

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

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序以及链顶

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

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

以下是一棵剖好的树。

树链剖分の妙用

1.求LCA

思想：

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

代码实现

时间复杂度$O(logn)$

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.在树上建立线段树

思想：

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

代码实现

时间复杂度$O(???)$

看操作建不同的线段树吧。

练习:

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

P5556 圣剑护符 - 洛谷

THE END - 感谢阅读！