ダブリング

$v$ の $2^i$ 回先の表を前計算し、 $K$ を 2 進数で表して $2^i$ 回先への移動を組み合わせます。木である必要はなく、各頂点 $v$ の行き先 nxt[v] が 1 つに決まっていれば使えます。

• Doubling(nxt, max_k, w): 各頂点の $1$ 回先 nxt（ $0 \le \mathrm{nxt}[v] < N$）から、max_k 回先まで求められるように前計算する。w[v] は $v$ から nxt[v] へ進むときの重みで、使わなければ省略する。 $O(N \log K)$
• kth(v, k): $v$ の $k$ 回先（ $0 \le k \le K$）。 $O(\log K)$
• kth_sum(v, k): $v$ の $k$ 回先と、そこまでに通った $k$ 本の重みの和の組を返す（w を渡したときだけ使える）。 $O(\log K)$
• max_step(v, ok): $v$ の $k$ 回先を $u$ として、ok(u) が True になる最大の $k$ と、そのときの $u$ を返す。ok(u) は $k = 0$ で True で、 $k$ を増やすと途中から False に変わるものとする。ずっと True のときは $K$ 以上の値を返す。 $O(\log K)$
• kth_all(nxt, k): すべての頂点について $k$ 回先を求めたリストを返す。表を持たないので、メモリは $O(N)$ で済む。 $O(N \log k)$

ここで $K$ は max_k です。

例（nxt[v] $\ge v$ のとき、 $l$ から何回進むと $r$ 以上に届くか）:

D = Doubling(nxt, n)
k, u = D.max_step(l, lambda u: u < r)
# k + 1 回で r 以上に届く（k が n 以上なら届かない）

コード

class Doubling:
    def __init__(self, nxt, max_k, w=None):
        # nxt[v] は v の 1 回先（0 <= nxt[v] < N）。max_k 回先まで求められるようにする
        # w[v] は v から nxt[v] へ進むときの重み（使わなければ None）
        self.log = max(1, max_k.bit_length())
        self.up = [nxt[:]]
        self.ws = None if w is None else [w[:]]
        for _ in range(self.log - 1):
            p = self.up[-1]
            if self.ws is not None:
                s = self.ws[-1]
                self.ws.append([s[v] + s[p[v]] for v in range(len(p))])
            self.up.append([p[p[v]] for v in range(len(p))])

    def kth(self, v, k):
        # v の k 回先
        i = 0
        while k:
            if k & 1:
                v = self.up[i][v]
            k >>= 1
            i += 1
        return v

    def kth_sum(self, v, k):
        # (v の k 回先, その間に通った k 本の重みの和)
        res = 0
        i = 0
        while k:
            if k & 1:
                res += self.ws[i][v]
                v = self.up[i][v]
            k >>= 1
            i += 1
        return v, res

    def max_step(self, v, ok):
        # ok(v の k 回先) が True である最大の k と、そのときの頂点（ok(v) は True とする）
        k = 0
        for i in range(self.log - 1, -1, -1):
            u = self.up[i][v]
            if ok(u):
                v = u
                k += 1 << i
        return k, v


def kth_all(nxt, k):
    # すべての v について、v の k 回先を求める
    res = list(range(len(nxt)))
    p = nxt[:]
    while k:
        if k & 1:
            res = [p[v] for v in res]
        p = [p[v] for v in p]
        k >>= 1
    return res