倍增法求LCA

1. 先用dfs求出每个点的深度(这个你应该会吧？)
2. 设F[x][i]表示x的$2^i$的辈祖先，即x向根节点走$2^i$步到达的节点，若该点不存在，则令f[x][i] = 0,那么F[x][0]就是x的父节点。因为x向根节点走$2^k==2^{k-1}再走2^{k-1}$步，所以F[x][k] = F[F[x][k-1]][k-1]这是一个类似于dp的过程
3. 预处理$O(nlogn)$完了以后。之后可以对不同的x，y计算LCA，每次复杂度$O(logn)$

其步骤是:

1. dep[x]表示x的深度，不妨设dep[x]>dep[y]
2. 利用二进制拆分的思想，把x向上调整到与y同一深度。就是把x向上走$2^{logn}…2^1,2^0$步，若depp[x]比dep[y]深，则x = f[x,k]。
3. 若x==y ，则已经找到LCA ，LCA等于x
4. 若x!=y，则一起向上跳，跳$2^{logn}…2^1,2^0$步，若f[x,k]!=f[y,k]，则令x = f[x,k],y = f[y,k]
5. 此时，x，y一定就只差一步就相会了，那么他们的父节点f[x,0]就是LCA(如果真的走到这一步了，LCA就是根节点了)

代码见板子