Wandering through folders
A repository has n folders and files, and they form a tree: each, except the root folder, has a parent folder. An indexing robot has lost its map and wanders the tree at random: in one step it moves from the current vertex to a random neighbour, the parent folder or any item of the current folder, all neighbours equally likely.
For each of q queries “from u to v”, find how many steps on average the robot takes, starting at u, until it first arrives at v.
Input
The first line holds n (2 ≤ n ≤ 100,000). The second holds n − 1 numbers: the parents of vertices 2, 3, …, n; vertex 1 is the root. Then q (1 ≤ q ≤ 100,000) and q lines u v (1 ≤ u, v ≤ n).
Output
For each query, the mean number of steps. It is always an integer; if u = v, it is 0.
Examples
Example 1
4 1 1 2 4 4 1 1 4 3 4 2 2
4 8 9 0
Example 2
5 1 2 3 4 3 5 1 1 5 3 1
16 16 12
Limits
- Time · Python
- 8000 ms
- Time · Go
- 2000 ms
- Memory
- 256 MB
- Judging
- 8 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 path between two vertices of a tree is unique, and to get from u to v the robot must traverse all its edges in order. So the answer is the sum of the mean times “move from one vertex of the path to the next”. How long on average does the robot take from a vertex to its parent?
2Hint 2
Call this time H(x) and analyse the first step. From x with degree d the robot goes straight to the parent with probability 1/d, and otherwise descends to a child c, must come back to x (that is H(c)), and start over. Try a leaf, then a vertex with two leaves: what formula emerges?
3The idea
The first-step equation: H(x) = 1 + (1/d)·Σc (H(c) + H(x)), where the sum is over the d − 1 children. Hence H(x)/d = 1 + (1/d)·Σ H(c), that is, H(x) = d + Σ H(c). By induction from the leaves (a leaf has H = 1) we get H(x) = 2·size(x) − 1, where size(x) is the number of vertices in the subtree of x: indeed, d + Σ(2·size(c) − 1) = 1 + 2·Σ size(c) = 2·size(x) − 1. The answer is an integer, as promised.
The time to descend from a parent p to a child c is the same formula if the tree is hung from c: then p is a child of c, and its subtree holds all vertices except the subtree of c, that is, n − size(c). We get 2·(n − size(c)) − 1.
The path from u to v rises to their lowest common ancestor w and descends to v. If the sums up(x) of climbing times and down(x) of descending times along the path from the root to x are computed in advance, the answer is up(u) − up(w) + down(v) − down(w).
4Walkthrough
Traverse the tree from the root breadth-first, compute subtree sizes in reverse order and the up and down sums in forward order. The lowest common ancestor can be found by binary lifting (as in the Go solution) or by Tarjan’s offline algorithm with a disjoint-set union (as in the Python solution: it is faster in an interpreter). Details are in the article on the lowest common ancestor.
The fifth test is the real folders and files of this site: 4701 vertices. From the file routes/web.php the robot reaches the root folder in 8 steps on average: the routes folder is small, and climbing out of it is easy. But back, from the root to this file, takes 18,792 steps: at every fork the robot more often turns the wrong way and wanders through the huge folders resources and app.
4+Solution
5Complexity
O(n) for the sizes and sums, O(n log n) for the lifting table and O(log n) per query; with Tarjan, almost linear in n + q.
6Common mistakes
- 2·size instead of 2·size − 1. A leaf reaches its parent in exactly one step, not two; the answers diverge on the very first example.
- One formula both ways. Climbing and descending one edge cost different amounts: together they give 2(n − 1), but they split evenly only if the subtree is exactly half the tree.
- Simulation. The means here are huge (in the sixth test, on a path of 100,000 vertices, almost 1010 steps from one end to the other), and random strolls will not give an exact integer answer.
- 32 bits, for the same reason.
Algorithms behind it
O(1) per step
2 problems
GRA
Algorithm
Lowest common ancestor
The common ancestor of two tree vertices: binary lifting in O(log n), an Euler tour in O(1), Tarjan off-line.
O(log n) per query
2 problems