最近公共祖先

概念

给定一棵有n个节点的树，树中的两个节点u和v的最近公共祖先lca，有以下定义

（1）lca既是u的祖先，又是v的祖先

（2）lca是所有u和v的公共祖先中深度最深的祖先，也就是距离u和v最近的祖先

倍增法

先来看一下朴素方法，假设在如下图所示的树上寻找节点u和v的最近公共祖先，过程如图所示，需要走5步。

考虑用倍增法，如下图所示，每次走一大步，假设步幅从8开始尝试，走8步明显超过了节点u的深度，不可以，那么尝试减少一半，走4步是可行的，接着尝试走2步，发现此时2步还是多了，那么再减少一半，尝试走1步，刚好走到了lca上，此时只走了2次，可见倍增法大大减少了操作的次数，可以提高效率。

接下来讲一下具体的代码思路，

1. 先把u和v放在同一深度上，所以我们需要一个数组记录u和v的深度，这里用depth[i]来表示节点i的深度，深度浅的不需要动，深度深的节点沿着树向上走，直到走到和深度浅的节点的深度相同。

   先判断一下哪个深度深，哪个深度浅，统一规定节点u的深度深。

   if(depth[u]<depth[v]) {
   		int temp = u;
   		u = v;
   		v = temp;
   	}
   

   然后让节点u沿着树向上跳，假设跳2的i次方步，我需要直到此时跳到了哪个节点上，所以再来一个数组$pa[u][i]$来记录节点u向上跳2的i次方次时对应的节点。从最大的步幅开始跳，如果跳多了就会导致depth[u] < depth[v]+(1<<i)，此时就不跳了，否则就向上跳，那么u就变成了$pa[u][i]$。for循环结束后u和v统一到了同一高度。

   for(int i =max-1;i >= 0;i--) {
   		if(depth[u] >= depth[v]+(1<<i))
   			u = pa[u][i];
   	}
   

   此时如果u和v相等说明已经找到了最近公共祖先，否则要接着找。

   if(u == v) return u;
   

2. u和v一起向上跳，直到u和v相等。这里也是先从最大的步幅开始跳，如果跳大了肯定是相等的，但是这不是最近公共祖先，所以就不跳，只有不相等的时候才会跳。

   for(int i =max-1;i >= 0;i--) {
   		if(pa[u][i] != pa[v][i]) {
   			u  =pa[u][i];
   			v = pa[v][i];
   		}
   	}
   

3. 预处理数组depth和pa

   在求数组pa时可以利用前面已经求出来的数组来求，比如要求$pa[u][i]$，也就是节点u走2的i次方步，可以分成两步，即节点u先走2的i-1次方步，然后再走2的i-1次方步，加起来就是$2^{i-1}+2^{i-1}=2^i$，也就是$pa[pa[u][i-1]][i-1]$

   private static void dfs(int u, int fa) {
   	// TODO Auto-generated method stub
   	for(int i =1;i < max;i++) pa[u][i] = pa[pa[u][i-1]][i-1];
   	for(int e:map[u]) {
   		if(e!=fa) {
   			depth[e] = depth[u]+1;
   			pa[e][0]=u;
   			 dfs(e, u);
   		}
   	}
   }
   

   额外思考：不会跳过头吗？

   其实这里也是为什么要采用倍增的原因，我们都知道二进制可以表示任意的十进制数字，假设我要向上跳n次，在我选择步幅跳的时候，每次选择的都是2的i次幂，当选择过大时我就不跳，也相当于第i位填0，当选择恰当时我就跳，相当于第i位填1，比如最开始的例子里8我没有跳，4跳了，2没有跳，1跳了，一共跳了4+1次，写成二进制就是101，所以不会跳过头，并且如果要跳n步，通过倍增我可以正好跳n步。