You are given a tree with n nodes numbered from 0 to n - 1 in the form of a parent array parent where parent[i] is the parent of ith node. The root of the tree is node 0. Find the kth ancestor of a given node.

The kth ancestor of a tree node is the kth node in the path from that node to the root node.

Implement the TreeAncestor class:


	TreeAncestor(int n, int[] parent) Initializes the object with the number of nodes in the tree and the parent array.
	int getKthAncestor(int node, int k) return the kth ancestor of the given node node. If there is no such ancestor, return -1.


&nbsp;
Example 1:

Input
["TreeAncestor", "getKthAncestor", "getKthAncestor", "getKthAncestor"]
[[7, [-1, 0, 0, 1, 1, 2, 2]], [3, 1], [5, 2], [6, 3]]
Output
[null, 1, 0, -1]

Explanation
TreeAncestor treeAncestor = new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]);
treeAncestor.getKthAncestor(3, 1); // returns 1 which is the parent of 3
treeAncestor.getKthAncestor(5, 2); // returns 0 which is the grandparent of 5
treeAncestor.getKthAncestor(6, 3); // returns -1 because there is no such ancestor

&nbsp;
Constraints:


	1 &lt;= k &lt;= n &lt;= 5 * 104
	parent.length == n
	parent[0] == -1
	0 &lt;= parent[i] &lt; n for all 0 &lt; i &lt; n
	0 &lt;= node &lt; n
	There will be at most 5 * 104 queries.


from math import ceil, log2
from typing import List

NO_PARENT = -1

class TreeAncestor:
    def __init__(self, n: int, parent: List[int]):
        self.parent = [[NO_PARENT] * n for _ in range(ceil(log2(n + 1)))]
        self.__initialize(parent)

    def __initialize(self, parent: List[int]):
        self.parent[0], prev = parent, parent

        for jump_pow in range(1, len(self.parent)):
            cur = self.parent[jump_pow]

            for i, p in enumerate(prev):
                if p != NO_PARENT:
                    cur[i] = prev[p]

            prev = cur

    def getKthAncestor(self, node: int, k: int) -> int:
        jump_pow = self.jump_pow

        while k > 0 and node != NO_PARENT:
            jumps = 1 << jump_pow

            if k >= jumps:
                node = self.parent[jump_pow][node]
                k -= jumps
            else:
                jump_pow -= 1

        return node

    @property
    def jump_pow(self) -> int:
        return len(self.parent) - 1
class TreeAncestor {
    int n;
    int[] parent;
    List<Integer>[] nodeInPath;
    int[] nodeIdxInPath;

    public TreeAncestor(int n, int[] parent) {
        this.n = n;
        this.parent = parent;
        nodeInPath = new ArrayList[n];
        nodeIdxInPath = new int[n];
        fill();
    }

    private void fill() {
        boolean[] inner = new boolean[n];
        for (int i = 1; i < n; i++) {
            inner[parent[i]] = true;
        }

        for (int i = 1; i < n; i++) {
            if (inner[i] || nodeInPath[i] != null) {
                continue;
            }
            List<Integer> path = new ArrayList<>();
            int k = i;
            while (k != -1) {
                path.add(k);
                k = parent[k];
            }
            int m = path.size();
            for (int j = 0; j < m; j++) {
                int node = path.get(j);
                if (nodeInPath[node] != null) break;
                nodeInPath[node] = path;
                nodeIdxInPath[node] = j;
            }
        }
    }

    public int getKthAncestor(int node, int k) {
        List<Integer> path = nodeInPath[node];
        int idx = nodeIdxInPath[node] + k;
        return idx >= path.size() ? -1 : path.get(idx);
    }
}
class TreeAncestor {
public:
    //go up by only powers of two
    vector<vector<int>> lift ;
    TreeAncestor(int n, vector<int>& parent) {
        lift.resize(n,vector<int>(21,-1)) ;
        //every node's first ancestor is parent itself
        for(int i = 0 ; i < n ; ++i ) lift[i][0] = parent[i] ;

        for(int i = 0 ; i < n ; ++i ){
            for(int j = 1 ; j <= 20 ; ++j ){
                if(lift[i][j-1] == -1) continue ;
                lift[i][j] = lift[lift[i][j-1]][j-1] ;
            }
        }
    }

    int getKthAncestor(int node, int k) {

        for(int i = 0 ; i <= 20 ; ++i ){
            if(k & (1 << i)){
                node = lift[node][i] ;
                if(node == -1) break;
            }
        }
        return node ;
    }
};
/**
 * @param {number} n
 * @param {number[]} parent
 */
var TreeAncestor = function(n, parent) {
    this.n = n;
    this.parent = parent;
};

/** 
 * @param {number} node 
 * @param {number} k
 * @return {number}
 */

/*
Qs:
1. Is the given tree a binary tree or n-ary tree?
2. Can k be greater than possible (the total number of ancestors of given node)?

Every node has a parent except the root.
1. Check if given node has a parent. If not, return -1.
2. Set given node as the current ancestor and start a while loop which continues while k is greater than 0.
At each iteration, we set `ancestor` to the parent of current `ancestor` and decrement k. If k is still greater
than 0 but ancestor is -1, that means k is greater than possible. Hence, we return -1. Else, while loop will
end when we are at the correct k-th ancestor. We return ancestor.
*/
TreeAncestor.prototype.getKthAncestor = function(node, k) {
    // check if given node has a parent
    if (this.parent[node] === -1) return -1;
    let ancestor = node;
    while (k > 0) {
        if (ancestor === -1) return -1; // k is greater than total number of ancestors of given node
        ancestor = this.parent[ancestor];
        k--;
    }
    return ancestor;
    // T.C: O(k)
};
Kth Ancestor of a Tree Node