1483. Kth Ancestor of a Tree Node

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.

class TreeAncestor {
    vector<vector<int>> boost;
    vector<int> ancs;
    void init(vector<int>& path, vector<vector<int>>& child, int n, int cnt) {
        ancs[n] = cnt;
        for(int i = 1; i <= path.size(); i<<=1) {
            boost[n].push_back(path[path.size() - i]);
        }
        path.push_back(n);
        for(auto ch : child[n]) {
            init(path,child,ch,cnt + 1);
        }
        path.pop_back();
        
    }
public:
    TreeAncestor(int n, vector<int>& parent) {
        boost = vector<vector<int>>(n,vector<int>());
        ancs = vector<int>(n);
        vector<vector<int>> child(n);
        
        for(int i = 1; i < parent.size(); i++)
            child[parent[i]].push_back(i);
        
        vector<int> path;
        init(path, child, 0, 0);
    }
    
    int getKthAncestor(int node, int k) {
        if(!k) return node;
        if(ancs[node] < k) return -1;
        int jump = 0;
        
        while(1<<(jump + 1) <= k)
            jump++;
        
        
        return getKthAncestor(boost[node][jump], k - (1<<jump));
    }
};

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