树上两点的最近公共祖先问题（LCA - Least Common Ancestors）

对于有根树T的两个结点u、v，最近公共祖先LCA(T,u,v)表示一个结点x，满足x是u和v的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先。

例如，如图，在以A为根的树上

节点 8 和 9 的LCA为 4

节点 8 和 5 的LCA为 2

节点 8 和 3 的LCA为 1

区别就在于是同时处理询问后输出还是边询问边输出

在线算法是读入一组询问，查询一次后紧接着输出一次

离线算法是读入全部的询问，在查询的过程中将所有询问全部处理，最后一起输出

如果给定的是一颗二叉查找树，那么每次询问就能从根节点开始，拿查询的两个数与节点的值进行对比。如果查询到两个数位于某个节点的两侧时，说明这个节点就是他们的LCA。这是特殊情况的特殊解法。

而LCA问题一般给定的不会是二叉树而是生成树（满足节点数n=边数m+1）。有可能会限制根节点，也有可能不会限制。在未限制根节点时，建图可以以任意一个节点作为根节点来建树。

常见在线算法为 倍增法

常见离线算法为Tarjan算法（下文）

也可以选择将LCA问题转化成RMQ问题使用 ST算法 求解

这个算法主要用到dfs与并查集

给每个节点置一个组别（并查集），如下图

离线算法，记录下所有待查询的节点对

这里假设要查询的点对有 2 - 7 8 - 9 8 - 5 8 - 3

从根节点开始深搜，遍历所有子树

第一次，遇到节点2时，发现7与它有查询关系。但是7还没有被搜索到，所以不做处理

向下，到节点7时，发现2与他有查询关系。发现2已经被搜索过了，那么2与7的LCA就是此时2所在的集合，即2

节点7之后没有子树，所以进行回溯

把节点7与节点7的所有子节点（无）组别置为节点7的父节点，然后继续搜索节点4的其他子树

搜索到节点8，发现与它有查询关系的 3 5 9节点均没有被搜索过，故像上一步一样回溯后继续查询

接着查询节点9，发现8与它有查询关系且节点8已经被搜索过，所以8与9的LCA就是此时8所在集合，即4

也就是说，当你搜索到一个节点 u ，发现节点 v 与它有查询关系且节点 v 已经被搜索过时，那么LCA(u,v)就是此时v所在的集合

按照这个思路继续下去，得到下列步骤

至此，整个图就构建完了，时间复杂度为 O(节点个数n+查询数量m)

　　第一行给出三个数n m q，表示有n个节点，m条边，q次询问 (假设此时n,q