我的最近公共祖先果然有问题

到处寻找逃避现实的理由，最终怀抱着理想溺死。——《我的青春恋爱物语果然有问题》

最近公共祖先

最近公共祖先（Lowest Common Ancestors），对于有根树 的两个结点 、 ，最近公共祖先 表示一个结点 ，满足 是 和 的祖先且 的深度尽可能大（也就是离它们俩最近）。

好吧，上面这个解释也太敷衍了，我们来看一张图：

根据这个要求，那么我们就有了一个朴素的想法，先让较深的节点向上爪巴到和另一个点深度相同，再一起向上爪巴，爪巴到父节点相同为止，就可以得到它们的最近公共祖先了。

深度的话，可以使用 来获取，子节点的深度就是父节点的深度 ，代码如下：

int dep[MAXN]; // 存深度 
bool vis[MAXN]; // 标记是否走过 
void dfs (int cur, int fath) // 传入当前子节点和它的父节点 
{
	if (vis[cur]) // 如果已经走过，就返回 
		return ;
	vis[cur] = true; // 标记为走过 
	dep[cur] = dep[fath] + 1; // 每个点的深度为它的父节点的深度 + 1
	for (int i = head[cur]; i; i = edge[i].nxt) // 前向星遍历
		dfs (edge[i].to, cur); // 传入接下来的儿子，也就是这条边的终点，传入接下来的父亲，也就是这个点。 
}

最坏复杂度为 ，在面对许多的询问时，这样是绝对绝对绝对不可以的！！

所以我们将介绍到接下来这个让人感到惊讶但又不得不服的东西，倍增思想。

倍增思想

我们考虑使用一个数组 来存一个编号为 的子节点的 级祖先是谁（父节点是 级祖先，祖父节点是 级祖先，以此类推）

然后因为每个数都可以用二进制来表示，那么我们就可以每次跳最大的深度，如果这个深度不能跳了，就看它除于二的深度能不能跳，这样子一直下去，一个深度就会被拆分成很多个可以被 这样表示的数（比如像 ）。

这里先给出常数优化的代码（ 预处理）：

for (int i = 2; i <= n; i ++) // Log2 预处理，用于常数优化  
	Log2[i] = Log2[i / 2] + 1;

主要代码

void dfs (int cur, int fath) // 传入当前节点和父节点 
{
	if (vis[cur]) // 如果已经走过，就返回 
		return ;
	vis[cur] = true; // 标记为走过 
	dep[cur] = dep[fath] + 1; // 每个点的深度为它的父节点的深度 + 1
	fa[cur][0] = fath; // 那么 2 的 0 次就是 1 级祖先，也就是向上一层的祖先，是它的父亲 
	for (int i = 1; i <= Log2[dep[cur]]; i ++) // 使用了常数优化，处理出祖先  
		fa[cur][i] = fa[fa[cur][i - 1]][i - 1]; // 以翻一番的速度增长，也就是这个点的父亲的父亲。
	for (int i = head[cur]; i; i = edge[i].nxt) // 前向星遍历 
		dfs (edge[i].to, cur); // 向下递归  
}
inline int LCA (int a, int b) // 最近公共祖先 
{
	if (dep[a] > dep[b])
		swap (a, b); // 保证 b 的深度大于 a
	while (dep[a] != dep[b]) // 先使其在同一深度
		b = fa[b][Log2[dep[b] - dep[a]]]; // 每次算一边深度差距， b 指针通过它的父节点逐渐到达 a 的深度
	if (a == b) // 如果这时两者已在同一个点 
		return a; // 说明 a 就是一个父节点（同样是 b 的父节点）
	for (int k = Log2[dep[a]]; k >= 0; k --) // 遍历 2 的 k 次结构的数（ k 就是级数） 
		if (fa[a][k] != fa[b][k]) // 如果它们的父节点仍不相同 
			a = fa[a][k], b = fa[b][k]; // 向上移动指针 
	return fa[a][0]; // 最后返回这个指针的父亲（因为上面在判断到相同时直接退出了） 
}

当然也有别的简单的写法（给出小鱼的代码）。

在 里可以这么写：

for (int i = 1; (1 << i) <= dep[cur]; i ++)
	fa[cur][i] = fa[fa[cur][i - 1]][i - 1];
for (int i = head[cur]; i; i = edge[i].nxt)
{
	int v = edge[i].to;
	if (v == fath)
		continue;
	dfs (v, cur);
}

在 里保持相同高度时可以这么写：

for (int i = 20; i >= 0; i --)
	if (dep[fa[b][i]] >= dep[a])
		b = fa[b][i];

树上距离

至于树上两点的 的距离，有公式：

$$\large dis_{u,v} = dep_u + dep_v - 2dep_{LCA(u,v)}$$

（据说很好推）， 预处理， 查询，空间复杂度为 。

当然，以上都是针对无权树的，如果有权值，可以额外记录一下每个点到根的距离，然后用几乎相同的公式求出（不过就是把深度改成了从根节点到这个点的长度罢了）

$$\large dis_{8,9} = dep_8 + dep_9 - 2dep_3$$ $$\large 3 = 3 + 4 - (2 \times 2)$$

使用了容斥原理，因为要算 号点到 号点的树上距离，所以先算出它们到根节点的距离 ，把重复的根节点的距离 减去两遍，就得到了答案。