树上倍增算法

倍增思想

如图，是一棵树

假设一棵树有$n$个节点，开一个数组$father[n][logn]$，$father[i][j]$表示第$i$个节点的第$2^j$个父亲。当寻找父亲节点时，每次跳$2^p$层，大大降低时间复杂度，显然有$2^{p-1}+2^{p-1}=2^p$，于是得到递推式：

$$father[i][j]=father[fahter[i][j-1]][j-1]$$

其实就是$2^{j}$分成两步跳。
由于二进制可以表示任何数字，所以这样的跳跃能到达树上的每一个节点。

寻找父亲节点

我们要寻找$i$的第$k$个父亲节点，就需要把$k$拆成二进制，若$k$的第$j$位为$1$，则需要将$i$向上倍增$2^j$。
代码如下

int FindFather(int i,int k)
{
	int j;
    for(j=0;j<=int(log2(k));j++)
        if((1<<j)&k)  i=father[i][j];//如果k的第j位是1，那就要把i往上提
    return i;
}