树链剖分讲解及总结(重链剖分+长链剖分)

　　树链剖分是解决树上问题的一种常见数据结构，对于树上路径修改及路径信息查询等问题有着较优的复杂度。树链剖分分为两种：重链剖分和长链剖分，因为长链剖分不常见，应用也不广泛，所以通常说的树链剖分指的是重链剖分。在这里讲解并总结一下树链剖分的实现、优秀性质及应用。

重链剖分

 先来介绍几个重链剖分的专业名词：

• 重儿子：每个点的子树中，子树大小(即节点数)最大的子节点
• 轻儿子：除重儿子外的其他子节点
• 重边：每个节点与其重儿子间的边
• 轻边：每个节点与其轻儿子间的边
• 重链：重边连成的链
• 轻链：轻边连成的链

重链剖分顾名思义是按轻重链进行剖分，对于每个点找到重儿子，如果多个子树节点数同样多，随便选一个作为重儿子就好了，一个点也可以看做一条重链。

用图来形象的描述一下，粗边就代表重边啦qwq

重链剖分的实现是由两次dfs来实现的，第一次dfs处理出每个点的重儿子son[]，子树大小size[]，深度d[]及父节点f[]

具体实现很简单，回溯时直接比较当前子节点和重儿子子树大小关系来更新重儿子

void dfs(int x)
{
	size[x]=1;
	d[x]=d[f[x]]+1;
	for(int i=head[x];i;i=next[i])
	{
		if(to[i]!=f[x])
		{
			f[to[i]]=x;
			dfs(to[i]);
			size[x]+=size[to[i]];
			if(size[to[i]]>size[son[x]])
			{
				son[x]=to[i];
			}
		}
	}
}

而第二遍dfs则是要处理出每个点所在重链的链头top[]

void dfs2(int x,int tp)//dfs2(root,root);
{
	top[x]=tp;
	if(son[x])
	{
		dfs2(son[x],tp);
	}
	for(int i=head[x];i;i=next[i])
	{
		if(to[i]!=f[x]&&to[i]!=son[x])
		{
			dfs2(to[i],to[i]);
		}
	}
}

通过代码及图示可以发现重链剖分的一些性质：

1、所有重链互不相交，即每个点只属于一条重链

2、所有重链长度和等于节点数(链长指链上节点数)

3、一个点到根节点的路径上经过的边中轻边最多只有log条

前两个性质好理解，那么第三个性质是为什么呢？因为最坏情况就是这个点到根路径上经过的边都是轻边，那么每走一条轻边到达这个点的父节点就代表这个父节点至少还有一个与当前子树同样大的子树，也就是说每走一条轻边走到的点的子树大小就要*2，因此最多只能走log次。这也是为什么要选重儿子而不是随便一个儿子的原因。

重链剖分有什么用呢？

举个例子：求LCA

对于求x,y的lca，可以每次优先爬点所在重链链头深的点，如果两个点不在同一条重链上，那么直接把链头深的点跳到链头，重复这个过程，直到两个点处在同一条重链上，直接输出深度浅的点就是lca了。因为重链是直接跳到链头，时间复杂度是O(1)的，而跳轻边最多就log条，因此求两个点的lca时间复杂度是O(logn)。具体实现如下。

#include
#include