树链剖分lca笔记

树链剖分求lca

参考资料：https://www.cnblogs.com/cangT-Tlan/p/8846408.html [树链剖分lca] 大佬讲的很清楚%%%orz

这篇博客是我的学习笔记。

树链剖分：树链剖分，计算机术语，指一种对树进行划分的算法，它先通过轻重边剖分将树分为多条链，保证每个点属于且只属于一条链，然后再通过数据结构（树状数组、BST、SPLAY、线段树等）来维护每一条链。（来自百度百科）

第一步是对树进行预处理，比如说处理每个节点的父节点，深度等等。

预处理的代码在下面：

int dfs(int now)
{
	siz[now] = 1;
	dep[now] = dep[fa[now]] + 1;
	for(int i = h[now]; i; i = e[i].nxt)
	{
		if(e[i].v != fa[now])
		{
			fa[e[i].v] = now;
			dfs(e[i].v);
			siz[now] += siz[e[i].v];
		}
	}
}

第二步就是找轻重链，其实我们只需要重链就可以了，下面是重边的概念：

在所有的儿子结点中，各以他们为祖先的子树的节点的个数多的儿子节点与其父亲的连边就是一条重边

感觉有点绕口，那么我们解释一下。

我们选中一个节点，以该节点为根节点，看看下一深度的子节点的子树的节点数量（感觉还是非常的绕口），选中子树节点数量最多的那个子节点，那么我们给这两个选中的节点之间的边染色，说明它是一条重边。相反地，轻边就是我们没有选中的边。（其实轻边没有什么用）

（从我看的那篇博客爬了个图过来）图中红色的边即为重边。9号节点的儿子的子树节点数量相同，随便选一个儿子染重边即可。

重边构成的链就是重链了。

树链剖分的代码在下面：

void tcp(int x)
{
	int t = 0;
	if(!top[x]) top[x] = x;//top[i]为沿着重链最高能走到哪个节点
	for(int i = h[x]; i; i = e[i].nxt)
	{
		if(e[i].v != fa[x] && siz[e[i].v] > siz[t]) t = e[i].v;
	}
	if(t)
	{
		top[t] = top[x];
		tcp(t); 
	}
	for(int i = h[x]; i; i = e[i].nxt)
	{
		if(e[i].v != fa[x] && t != e[i].v) tcp(e[i].v);
	}
} 

那么下面我们怎么使用树链剖分来求lca呢？？？？？

先上代码：

int lca(int x, int y)
{
	while(top[x] != top[y])
	{
		if(dep[top[x]] < dep[top[y]]) swap(x, y);
		x = fa[top[x]];
	}
	if(dep[x] > dep[y]) swap(x, y);
	return x;
}

其实很好理解，当两个点位于一条重链上时停止操作。否则，重链顶端深度深的点，我们跳到这条重链的顶端的父节点（注意，不是重链的顶端，而是顶端的父节点），重复操作，在两个点位于一条重链上时，深度浅的点就是我们要找的lca。

（我又从那篇博客爬了一张图过来）

比如说，我们要找10，13节点的lca，我们观察到10号节点是个孤独的节点，那么我们跳到9号节点，随后13号节点跳到5号节点，我们发现5号节点和9号节点位于同一个重链上，那么深度较浅的5号节点就是10和13节点的lca。