一、LCA的定义：

　　在一棵树上，点u到点v之间的路径最短的那个节点就是lca(u,v)

二、倍增思想：

　　我们定义fa[i][j]表示节点i往上跳跃2^j次所到达的节点标号，则有结论：

　　1.因为2^(j-1)+2^(j-1)=2^j，所以fa[i][j]=f[f[i][j-1]][j-1],即2^j的父亲就是跳2^(j-1)步到达的点再跳2^(j-1)所到达的点;

　　2.dep[i]表示节点i的深度，可以一次dfs求出

　　3.fa[i][0]=fa[i];

三、具体运用：

　　若dep[u]!=dep[v]，则把dep大的往上跳k=dep[x(较大)]-dep[y(较小)]步，使得两个节点处于同一层上

　　可以把k表示为2的幂次和，即转换为二进制然后按位做，这时候fa数组就派上用场了

　　往上跳k步可以表示为多个fa数组中的j之和，求出跳越k层后的节点

　　然后两个节点一起往上走，直到遇见