A walk through the tree of life
Guided tours are run on the tree of life: from one taxon to another, always by the shortest way, up to their common ancestor and down to the second. At each step the guide talks about the taxon the group is standing at. Where will the group be after k steps?
The tree is given by parents: vertex 1 is the root, and every other vertex v has a parent pv < v. The third test is the tree of life from the article: all the mammal species from the NCBI taxonomy and a dozen landmarks from the rest of life, 7865 taxa in preorder, the root being “cellular organisms”.
Input
The first line holds n (1 ≤ n ≤ 100,000). The second holds n − 1 numbers p2, …, pn (1 ≤ pv < v); for n = 1 the line is empty. The third holds the number of tours q (1 ≤ q ≤ 50,000), then come q lines u v k (1 ≤ u, v ≤ n, 0 ≤ k ≤ 2n).
Output
For each tour, the number of the vertex where the group will be after k steps of the shortest path from u to v (for k = 0 that is u itself), or −1 if the path is shorter than k steps.
Examples
Example 1
7 1 1 2 2 3 6 4 4 7 0 4 7 2 4 7 5 5 5 1
4 1 7 -1
Example 2
7 1 2 3 3 5 1 5 6 2 3 2 6 3 7 4 4 4 7 6 5 5 0
2 6 4 -1 5
Limits
- Time · Python
- 4000 ms
- Time · Go
- 2000 ms
- Memory
- 256 MB
- Judging
- 6 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
The shortest path from u to v in a tree goes through their lowest common ancestor c. How many steps does it have, and how many of them go up?
2Hint 2
If the k-th step falls on the descent to v, it is more convenient to count it from the other end: how many steps above v is it?
3Hint 3
In the fifth test the tree is tens of thousands of levels high. Climbing one step at a time for each question is billions of steps. What do you need to be able to do quickly, besides the common ancestor?
4The idea
The path is a = depth(u) − depth(c) steps up and b = depth(v) − depth(c) steps down. If k ≤ a, the answer is the ancestor of u k steps up. If a < k ≤ a + b, the answer lies on the descent, and it is the ancestor of v a + b − k steps up. Otherwise −1. Both operations, the common ancestor and “the ancestor s steps up”, come from one binary lifting table: climbing by s is a jump for each one bit of s.
5Walkthrough
Parents come before children, so the depths and the table up[j][v], the ancestor 2j steps up, are computed by simple passes over the array, without a depth-first walk. Make the root its own parent: a jump above the root leads to the root, and the table does not go off the edge. The function climb(v, s) jumps by the one bits of s; lca(u, v) raises the deeper vertex with climb by the difference in depth and jumps with both while the ancestors differ. Then the three cases from the idea.
In the example the path 4 → 7 goes through 4, 2, 1, 3, 6, 7: two steps up to 1 and three down. Step 2 is vertex 1 itself, step 5 is 7, and there is no step 6.
5+Solution
6Complexity
Preparation O(n log n), each question O(log n): a common ancestor and one climb.
7Common mistakes
- Climbing one step at a time. Correct, but on deep trees each question costs as many steps as the tree has levels; the fifth test does not let such a solution through in time.
- The descent counted from the common ancestor. There is no way to go down the tree: a vertex has many children. A step on the descent is found by climbing from v.
- The end of the path. At k = a + b the answer is v itself, and at k = a the common ancestor itself; −1 only for k > a + b.