方法
（1）向上标记法O(n)
这个方法很暴力，没什么说的，如果有m次查询，那时间复杂度就会是O(nm)
（2）倍增
步骤:
1.初始化:通过dfs初始化两个数组depth[],fa[i,j];
depth[i]:表示深度
fa[i,j]:表示从i开始，向上走$2^j$步所能走到的节点编号($0 \leq j \leq logn$)
哨兵:如果从i开始跳$2^j$步会跳过根节点，那么fa[i,j]=0,depth[0]=0;
2.查询
[1]现将两个点同时调到同一层
[2]让两个点同时往上跳，一直跳到它们的最近公共祖先的下一层
预处理 O(nlogn)
查询O(logn)
具体代码实现可以看这里 AcWing1172.祖孙询问
(3)Tarjan——离线求LCA O(n+m)
在优先遍历时，将所有点分为三大类:
[0] 还未搜索过的点
[1] 正在搜索的分支
[2] 已经遍历过，且回溯过的点。

步骤:
1.在进入递归层时，将点标记为1
2.搜索所有没有遍历过的链接且与该点链接的点，搜索回溯后，完成集合合并。
3.将所有与该层点有关系的询问，全部遍历，当另一个点已经被标记为2，则找到了最近公共祖先，就是另一个点的并查集标志节点。
4.最后回溯时，将该节点标记为2.

注意:
一定要先将要拓展的点进行拓展，回溯时再进行集合合并。记忆的话，就记住，我们进行集合合并的点一定是被回溯过的。理解的话，可以看这个例子。
比如正在遍历的一条路径上a->b->c->d刚遍历完c节点的子树并回溯到c节点
那么假如有一个询问是在c-d节点之间，对于d节点st[d]=2;
如果先p[j]=u,那么p[a]=a,p[b]=a,p[c]=b那么进行anc=find(d)操作时会把d的祖先p[d]直接路径压缩成a节点。
如果后p[j]=u,由于p[c]=c,那么在进行anc=find(d)操作时p[d]是c节点
显然，我们要找的是最近公共祖先，那就要先遍历再合并。
其实就是，如果我们提前进行合并那同一路上的公共祖先就会出现问题。