倍增思想
如图,是一棵树
假设一棵树有n个节点,开一个数组father[n][logn],father[i][j]表示第i个节点的第2j个父亲。当寻找父亲节点时,每次跳2p层,大大降低时间复杂度,显然有2p−1+2p−1=2p,于是得到递推式:
father[i][j]=father[fahter[i][j−1]][j−1]
其实就是2j分成两步跳。
由于二进制可以表示任何数字,所以这样的跳跃能到达树上的每一个节点。
寻找父亲节点
我们要寻找i的第k个父亲节点,就需要把k拆成二进制,若k的第j位为1,则需要将i向上倍增2j。
代码如下
1 2 3 4 5 6 7
| int FindFather(int i,int k) { int j; for(j=0;j<=int(log2(k));j++) if((1<<j)&k) i=father[i][j]; return i; }
|