有根树中，一个节点到根的路径上的所有节点被视为这个点的祖先，包括根和它本身
对于点a和b，如果c既是a的祖先又是b的祖先，那么c是a和b的公共祖先 ##深度 子节点的深度=父节点深度+1，一般我们定根的深度为1
树上两个节点的所有公共祖先中，深度最大的那个称为两个点的最近公共祖先(LCA)
很明显，这个方法是很想爬山，我们可以先然两个节点中，深度大的依着父亲爬到两节点深度相同，然后，两个节点一起爬，最后，爬到了同一个节点，这，就是ans； 很明显，这个方法有几个缺陷，时间为O（n）,并且，还要用bfs算深度
在前面爬山法进行改进，在爬山的过程中，其实有些地方可以一蹦千尺高，但却一步一步地走，大大的浪费了时间，于是，我们运用倍增
众所周知，任意一个数是可用二进制来表示，如果，我们用一个二进制来表示两个节点的深度差，那不是就把时间化为O（log2n）
设一个数组dp[i][j]从i这个节点往上走2j步，那么，dp[i][j-1]j就是再往根的方向走2(j-1)步，如果再走2(j-1)步,就相当于走了2j，所以，dp[i][j]=dp[dp[i][j-1]][j-1] 其中，dp[i][0]=fa[i];
那如何来求dp这个数组呢
我们可以在bfs求树上每个点深度的时候，顺便预处理dp数组
void bfs() { queue<int>q; d[root]=1; q.push(root); while(q.size()) { int temp=q.front(); q.pop(); for(int i=0;i<g[temp].size();i++) { int v=g[temp][i]; if(d[v]) { continue; } d[v]=d[temp]+1; dp[v][0]=temp; for(int j=1;j<=Maxstep;j++) { dp[v][j]=dp[dp[v][j-1]][j-1]; } q.push(v); } } }LCA就是在爬山的基础上，将一步一步的枚举，改为，从大到小走2j
int LCA(int a, int b) { if (d[a] > d[b]) { swap(a, b); } for (int i = Maxstep; i >= 0; i--) { if (d[dp[b][i]] >= d[a]) { b = dp[b][i]; } } if (a == b) { return a; } for (int i = Maxstep; i >= 0; i--) { if (dp[b][i] != dp[a][i]) { a = dp[a][i]; b = dp[b][i]; } } return dp[a][0]; }可以先求出两点的LCA，然后，这两点的距离，就是公共祖先到A的距离+公共祖先到B的距离，而距离，可以和算深度一样，算到根节点的距离
int dist(int x, int y) { return d[x] + d[y] - d[LCA(x, y)] * 2; }离线的求LCA的方法 先dfs，然后，标记，用并查集的路径压缩记录这个节点，最近的，没有回溯的节点，如果，询问的两个节点中有被访问的，那就可以将这个结点并查集的祖先放进去，正因为这样，所以，所有的，都需要先放进去，在dfs
void Trajan(int x) { vis[x] = 1; for (int i = 0; i < g[x].size(); i++) { int v = g[x][i]; if (vis[v]) { continue; } Trajan(v); fa[v] = x; } for (int i = 0; i < q[x].size(); i++) { int ID = q[x][i].id; if (vis[q[x][i].v] == 1) { ans[ID] = find(q[x][i].v); } } }