1483. Kth Ancestor of a Tree Node / 2836. Maximize Value of Function in a Ball Passing Game

[Woodyiiiiiii]

1483. Kth Ancestor of a Tree Node / 2836. Maximize Value of Function in a Ball Passing Game

1483. Kth Ancestor of a Tree Node
2836. Maximize Value of Function in a Ball Passing Game

资料：
【模板讲解】树上倍增算法（以及最近公共祖先）
【模板】树上倍增（Python/Java/C++/Go）

树上倍增算法。

简单来说，因为k，或者说是要求经过的路径数太大了，需要对k进行二进制上的拆分，比如14拆成2+4+8；然后预处理求每个节点第2^i个祖先，然后动态规划/递归去求解。

模版如下(需要注意的是，32还是64要看k值范围)：

class TreeAncestor {

    int[][] f;

    public TreeAncestor(int n, int[] parent) {
        int m = 32 - Integer.numberOfLeadingZeros(n);
        f = new int[n][m];
        for (int i = 0; i < n; i++) {
            f[i][0] = parent[i];
        }
        for (int j = 0; j < m - 1; j++) {
            for (int i = 0; i < n; i++) {
                int p = f[i][j];
                if (p == -1) {
                    f[i][j + 1] = -1;
                } else {
                    f[i][j + 1] = f[p][j];
                }
            }
        }
    }
    
    public int getKthAncestor(int node, int k) {
        int m = 32 - Integer.numberOfLeadingZeros(k);
        int cur = node;
        for (int j = 0; j < 32; j++) {
            if (((k >> j) & 1) == 1) {
                cur = f[cur][j];
                if (cur == -1) {
                    break;
                }
            }
        }
        return cur;
    }
}

/**
 * Your TreeAncestor object will be instantiated and called as such:
 * TreeAncestor obj = new TreeAncestor(n, parent);
 * int param_1 = obj.getKthAncestor(node,k);
 */