倍增（也叫二分倍增）通常被叫做“树上倍增”，是因为这种方法最初用于树形结构中，特别是在树的上升路径查询、LCA（最近公共祖先）问题等场景中非常有效。在树上倍增的过程中，树的结构天然适合这种操作，因为树是无环的，且每个节点的父节点可以通过倍增逐步上升，直到找到需要的节点或信息。

对于树上的倍增，最常见的应用是处理树中节点到根节点的路径，或者查询某个节点的某些属性（比如LCA）时，通过倍增可以快速跳跃至目标位置，节省时间复杂度。`

class BinaryLiftingTree:
    def __init__(self, parent: List[int]):
        n = len(parent)
        m = n.bit_length() - 1
        # pa[x][i] 表示 x 的第 2^i 个祖先节点
        # pa[x][0] = parent[x]
        # pa[x][1] = pa[pa[x][0]][0]
        # pa[x][i] = pa[pa[x][i]][i]
        self.pa = [[p] + [-1] * m for p in parent]
        for i in range(m):
            for x in range(n):
                if (p := self.pa[x][i]) != -1:
                    self.pa[x][i + 1] = self.pa[p][i]

    def getKth(self, node: int, k: int) -> int:
        for i in range(k.bit_length()):
            if (k >> i) & 1:
                node = self.pa[node][i]
                if node < 0:  # 如果祖先不存在，直接返回 -1
                    break
        return node