{"id":"05142786-2a60-4db4-b7ec-761739554915","name":"K'th Ancestor","description":"You are given a tree of n nodes numbered from 0 to n-1 and is rooted at 0.\r\nYou are given an array parent of length n where parent[i] denotes parent of i'th node (in case of root it's parent is itself).\r\n\r\nNow you have to answer q queries of format:\r\na k\r\nanswer to this query is k'th ancistor of node a if k'th ancistor does not exist simply print root.\r\nIn simple words you have to find k'th ancistor of a node.\r\n\r\nTask: could u do it in log(n) or better time complexity.","inputFormat":"n\r\np1\r\np2\r\np3\r\n... n numbers till pn\r\nq\r\na1 k1\r\na2 k2\r\n... q queries till a(q) k(q)","outputFormat":"for each query print in single line value of k'th ancistor","constraints":"1. 2 &lt;= n &lt;= 10^5\r\n2. parent[0] = 0\r\n3. 1 &lt;= q &lt;= 10^5\r\n4. 0 &lt;= a &lt;= n-1\r\n5. 1 &lt;= k &lt;= n","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader read = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n int n = Integer.parseInt(read.readLine());\r\n\r\n int[] parent = new int[n];\r\n\r\n for (int i = 0; i < n; i++) {\r\n parent[i] = Integer.parseInt(read.readLine());\r\n }\r\n int q = Integer.parseInt(read.readLine());\r\n // write your code here\r\n\r\n\r\n }\r\n}\r\n"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"7\r\n0\r\n0\r\n0\r\n1\r\n3\r\n2\r\n3\r\n6\r\n5 1\r\n6 2\r\n3 2\r\n3 3\r\n6 3\r\n4 1\r\n","sampleOutput":"2\r\n1\r\n0\r\n0\r\n0\r\n3\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"ebd4bd7d-3745-4e3b-9603-da905237841b","name":"Binary Lifting For Experts","slug":"binary-lifting-for-experts-971","type":0},{"id":"bbdb8e13-0914-49d9-afd5-e8fa05d493e5","name":"K'th Ancestor","slug":"k-th-ancestor","type":1}],"next":{"id":"c3e66693-4622-4eb6-aa76-1d162b164516","name":"Lca - Lowest Common Ancestor","type":1,"slug":"lca-lowest-common-ancestor"},"prev":null}}

K'th Ancestor

You are given a tree of n nodes numbered from 0 to n-1 and is rooted at 0. You are given an array parent of length n where parent[i] denotes parent of i'th node (in case of root it's parent is itself). Now you have to answer q queries of format: a k answer to this query is k'th ancistor of node a if k'th ancistor does not exist simply print root. In simple words you have to find k'th ancistor of a node. Task: could u do it in log(n) or better time complexity.

{"id":"05142786-2a60-4db4-b7ec-761739554915","name":"K'th Ancestor","description":"You are given a tree of n nodes numbered from 0 to n-1 and is rooted at 0.\r\nYou are given an array parent of length n where parent[i] denotes parent of i'th node (in case of root it's parent is itself).\r\n\r\nNow you have to answer q queries of format:\r\na k\r\nanswer to this query is k'th ancistor of node a if k'th ancistor does not exist simply print root.\r\nIn simple words you have to find k'th ancistor of a node.\r\n\r\nTask: could u do it in log(n) or better time complexity.","inputFormat":"n\r\np1\r\np2\r\np3\r\n... n numbers till pn\r\nq\r\na1 k1\r\na2 k2\r\n... q queries till a(q) k(q)","outputFormat":"for each query print in single line value of k'th ancistor","constraints":"1. 2 &lt;= n &lt;= 10^5\r\n2. parent[0] = 0\r\n3. 1 &lt;= q &lt;= 10^5\r\n4. 0 &lt;= a &lt;= n-1\r\n5. 1 &lt;= k &lt;= n","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader read = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n int n = Integer.parseInt(read.readLine());\r\n\r\n int[] parent = new int[n];\r\n\r\n for (int i = 0; i < n; i++) {\r\n parent[i] = Integer.parseInt(read.readLine());\r\n }\r\n int q = Integer.parseInt(read.readLine());\r\n // write your code here\r\n\r\n\r\n }\r\n}\r\n"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"7\r\n0\r\n0\r\n0\r\n1\r\n3\r\n2\r\n3\r\n6\r\n5 1\r\n6 2\r\n3 2\r\n3 3\r\n6 3\r\n4 1\r\n","sampleOutput":"2\r\n1\r\n0\r\n0\r\n0\r\n3\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"ebd4bd7d-3745-4e3b-9603-da905237841b","name":"Binary Lifting For Experts","slug":"binary-lifting-for-experts-971","type":0},{"id":"bbdb8e13-0914-49d9-afd5-e8fa05d493e5","name":"K'th Ancestor","slug":"k-th-ancestor","type":1}],"next":{"id":"c3e66693-4622-4eb6-aa76-1d162b164516","name":"Lca - Lowest Common Ancestor","type":1,"slug":"lca-lowest-common-ancestor"},"prev":null}}
plane

Editor

Loading...

K'th Ancestor

medium

You are given a tree of n nodes numbered from 0 to n-1 and is rooted at 0. You are given an array parent of length n where parent[i] denotes parent of i'th node (in case of root it's parent is itself). Now you have to answer q queries of format: a k answer to this query is k'th ancistor of node a if k'th ancistor does not exist simply print root. In simple words you have to find k'th ancistor of a node. Task: could u do it in log(n) or better time complexity.

Constraints

1. 2 <= n <= 10^5 2. parent[0] = 0 3. 1 <= q <= 10^5 4. 0 <= a <= n-1 5. 1 <= k <= n

Format

Input

n p1 p2 p3 ... n numbers till pn q a1 k1 a2 k2 ... q queries till a(q) k(q)

Output

for each query print in single line value of k'th ancistor

Example

Sample Input

7 0 0 0 1 3 2 3 6 5 1 6 2 3 2 3 3 6 3 4 1

Sample Output

2 1 0 0 0 3

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode