解释

倍增法的核心起源于每一个数字都可以使用二进制表示：

13 = 8+4+1=0b1000 + 0b0100 + 0b0001

那么我们先预处理这样的一个表，之后是不是就可以直接使用，快速得到结果呢？相比于一层层的获取的时间复杂度O(n)，倍增法的事件复杂度是O(lgn)

数据结构： up[i][j]表示在i点$2^j$跳达到后的点。 up[i][0]表示i点点直接parent

核心公式：

mid = up[i][j-1] // 从i经过2^(j-1)跳到达mid
up[i][j] = up[mid][j-1] //从mid经过2^(j-1)达到j，总共就是2*2^(j-1)=2^j跳

预处理

for (int j = 1; j < LOG; ++j) {
        for (int i = 1; i <= n; ++i) {
            int mid = up[i][j - 1];
            up[i][j] = (mid == 0 ? 0 : up[mid][j - 1]);
        }
    }

注意这里第一层循环是j，因为他应该一层一层的处理，那么首先j=0应该处理完，才能处理下面的，以此类推。

为什么要拆成两半？

是因为在预处理的时候我们是从小的变成大的，并且这个变化都是2次方来变化的。

运用

在完成了这个倍增表之后，我们需要使用。常见的表示方法是：

if (k & (1LL << j)) u = up[u][j];

我们把(k & (1LL << j))单独拎出来解释一下。 同样以k=13即二进制1101为例， 那么上面为真只能在j=0, 2, 3为真。那么这里就从13次直接变成了跳3次，很大程度减少了计算量。

实战练手

cses题目:# Company Queries I