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;
    }
}