# HackerEarth The family tree of Bob problem solution

In this HackerEarth The family tree of Bob problem solution Bob wants to know about his ancestors, therefore, he draws a graph of his family. In that graph, root is the eldest-known family member. The leaf node is a member who has no children.

You are given a Q query and N family members. They have to just print the kth ancestors with respect to that query. A member can have only one parent.

Note: Print -1 if the query is incorrect, that is, if the kth ancestor is not available. The root of the tree is 1.

## HackerEarth The family tree of Bob problem solution.

`#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 5e5 + 14, lg = 19;int n, h[maxn], par[lg][maxn];vector<int> g[maxn];void dfs(int v = 0, int p = -1){    for(int u : g[v])        if(u != p){            par[0][u] = v;            h[u] = h[v] + 1;            dfs(u, v);        }}int parat(int v, int h){    for(int i = 0; i < lg; i++)        if(h >> i & 1)            v = par[i][v];    return v;}int main(){    ios::sync_with_stdio(0), cin.tie(0);    int q;    cin >> n >> q;    for(int i = 0; i < n - 1; i++){        int v, u;        cin >> v >> u;        v--, u--;        g[v].push_back(u);        g[u].push_back(v);    }    dfs();    for(int k = 1; k < lg; k++)        for(int i = 0; i < n; i++)            par[k][i] = par[k - 1][ par[k - 1][i] ];    while(q--){        int v, k;        cin >> v >> k;        v--;        cout << (h[v] < k ? -1 : parat(v, k) + 1) << '\n';    }}`

### Second solution

`import java.io.*;import java.util.*; public class Main implements Runnable{    int depth = 0;    public static void main(String args[]) throws Exception    {        new Thread(null, new Main(), "Main", 1<<26).start();    }    public void run()     {        try        {            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));            String s1[] = br.readLine().trim().split(" ");            int n = Integer.parseInt(s1[0]);            int m = Integer.parseInt(s1[1]);            ArrayList<Integer>[] g = new ArrayList[n];            for (int i = 0; i < n; i++)                 g[i] =new ArrayList<Integer>();                         for(int i = 0; i < n - 1; i++)            {                String s2[] = br.readLine().trim().split(" ");                int u = Integer.parseInt(s2[0])-1;                int v = Integer.parseInt(s2[1])-1;                g[u].add(v);                g[v].add(u);            }                        ArrayList<Query>[] qu = new ArrayList[n];            for (int i = 0; i < n; i++)                 qu[i] =new ArrayList<Query>();                             for(int i = 0; i < m; i++)            {                String s2[] = br.readLine().trim().split(" ");                int x = Integer.parseInt(s2[0])-1;                int y = Integer.parseInt(s2[1]);                qu[x].add(new Query(y, i));            }                        int ans[] = new int[n+5];            int sol[] = new int[m];            depth = 0;            dfs(g, qu, 0, -1, ans, sol);                        for(int i = 0; i < m; i++)                bw.write(sol[i]+1 + "\n");            bw.flush();        }        catch(Exception e)        {            System.out.println("Error!"+"\n");            e.printStackTrace();             System.exit(0);        }           }        public void dfs(ArrayList<Integer>[] g, ArrayList<Query> qu[], int s, int par, int ans[], int sol[])    {        ans[depth++] = s;        for(int i = 0; i < qu[s].size(); i++)            if((depth - qu[s].get(i).x - 1) < 0)                sol[qu[s].get(i).id] = -2;            else                sol[qu[s].get(i).id] = ans[depth - qu[s].get(i).x - 1];                for(int i = 0; i < g[s].size(); i++)            if(g[s].get(i) != par)                dfs(g, qu, g[s].get(i), s, ans, sol);                depth--;        } }class Query{    int x;    int id;    Query(int x, int id)    {        this.x = x;        this.id = id;    }}`