LCA，即树上两点之间的公共祖先，求这样一个公共祖先有很多种方法:
暴力向上：O(n)
每次将深度大的点往上移动，直至二者相遇
树剖：O(logn)
在O(2n)预处理重链之后，每次就将深度大的沿重链向上，直至二者在一条链上
tarjan_lca:离线O(n+m)
先记录所有的询问，对树进行一次dfs，对于搜索到的点u，先将点u往下搜，再将点u与父节点所在集合合并，之后对于它的所有询问(u,v)，若v已被访问，那么找v所在集合的祖先e，则e就是u与v的lca
但我们今天要讲的是
倍增lca
所谓倍增，就是利用二进制将冗长的多个相同步骤合并，以实现加速转移的算法。
比如快速幂就是一个经典的例子，将多次乘法通过二进制合并
下面我们来讲讲如何利用倍增求LCA：
还记得上面的暴力算法吗？
暴力算法是最质朴的东西，却是所有高端操作的出发点，倍增就是这样。
我们只需要利用倍增，将往上移动的操作压缩，就能实现算法复杂度的优化
实现
我们设f[i][j]表示i节点的第2^j代祖先，这样f[i][0]就是i的父亲，而对于所有j>0，我们有
f[i][j] = f[f[i][j - 1]][j - 1]
怎么理解呢？
i节点的第2^(j - 1)代祖先的2^(j - 1)祖先就是i的第2^j代祖先
所以我们用O(nlogn)的时间就预处理出了f[][]数组
void dfs(int u,int fa){
dep[u] = dep[fa] + 1;
f[u][0] = fa;
for (int k = head[u]; k != -1; k = edge[k].next)
if (edge[k].to != fa)
dfs(edge[k].to,u);
}
求深度
void cal(){
for (int i = 1; (1<<i) <= N; i++)
for(int u = 1; u <= N; u++)
f[u][i] = f[f[u][i - 1]][i - 1];
}
预处理
求出了f数组，怎么求lca呢？
对于询问lca(u,v),不妨设u是其中深度较大的，我们先将u升到离v同样的深度，设需要向上移动d = dep[u] - dep[v]
我们把d看做二进制，那么我们只需对于其中所有的1进行操作就好了
比如说：
我们需要向上5次，即101，那么我们只需要向上转移100次和1次，这就刚好与f[i][2]和f[i][0]相对应
移到相同位置后，我们从二进制大到小枚举，当u和v祖先不同时，就向上转移，最后u的祖先就是lca
int lca(int u,int v){
if (dep[u] < dep[v]) swap(u,v);
int d = dep[u] - dep[v];
for (int i = 0; (1<<i) <= d; i++)
if ((1<<i) & d)
u = f[u][i];
if (u != v){
for (int i = (int)log(N); i >= 0; i--)
if (f[u][i] != f[v][i]){
u = f[u][i];
v = f[v][i];
}
return f[u][0];
}
else return u;
}