求最近公共先人的几种办法
1.向上标记法（暴力做法，不罕用）
工夫复杂度为O(n)，最坏状况下为一条链；
求4和6的最近公共先人：首先建设一个bool类型的数组用来标记4或者6的先人，比方，4的先人是2,1（从下往上顺次遍历并标记），那就将2,1标记为1，之后标记6的先人，在标记过程中如果遇到已被标记的先人，那么这个先人就是4和6的公共先人，在本例中为1。
2.倍增法（罕用）
fa[i,j]示意从i开始，向上走2^j步所能走到的节点。0<=j<=logn,depth[i]示意深度
步骤：
哨兵：如果从i节点跳2^j次方步会跳过根节点，那么fai=0（非凡标记），规定depth[0]=0;
【1】先将两个点跳到同一层
例如：
如上图，要从x节点跳到与y节点同一高度
当初已知depth[x]和depth[y]
假如t=depth[x]-depth[y]，为x与y之间的高度差；
利用二进制拼凑的思维，假如t=11,先找到小于等于11的最大的2的整数幂，也就是8，那么11-8=3，接下来再找到小于等于3的最大的2的整数次幂，也就是2，那么3-2=1，之后再找到小于等于1的2的整数次幂，也就是2^0=1，那么1-1=0，就拼凑好了t。
要害局部代码：
//depth代表节点深度，fai代表节点i向上跳2^j步的节点编号
for(int i=15;i>=0;i--) { if(depth[fa[u][i]]>=depth[v]) { u=fa[u][i]; } }【2】让两个同时往上跳，始终跳到它们的最近公共先人的下一层。
预处理O(nlogn)
查问O(logn)
for(int i=15;i>=0;i--) { if(fa[u][i]!=fa[v][i]) { u=fa[u][i]; v=fa[v][i]; } }