Dynamic Instability
Farmer Nhoj has trapped Bessie on a rooted tree with N (2≤N≤2⋅105) nodes, where node 1 is the root. Scared and alone, Bessie makes the following move each second:
- If Bessie's current node has no children, then she will move to a random ancestor of the current node (excluding the node itself).
- Otherwise, Bessie will move to a random child of the current node.
Initially, Bessie is at node x, and her only way out is the exit located at node y (1≤x,y≤N). For Q (1≤Q≤2⋅105) independent queries of x and y, compute the expected number of seconds it would take Bessie to reach node y for the first time if she started at node x, modulo 109+7.
In the 1st query, the expected time to reach node 1 from itself is 0.
In the 3rd query, after 1 second, Bessie will be at node 1 with probability 21 and at node 2 with probability 21. Since the expected time to reach node 1 from node 2 is 4, the expected time for Bessie to reach node 1 starting at node 3 is 1+21⋅0+21⋅4=3.
In the 3rd query, the expected time to reach node 3 from node 1 is 215.
SCORING:
- Inputs 4-8: For all queries, y=1.
- Inputs 9-13: For all queries, x=1.
- Inputs 14-18: For each 2≤i≤N, pi is uniformly randomly chosen from the range [1,i−1].
- Inputs 19-23: No additional constraints.
Problem credits: Avnith Vijayram
Source: USA Computing Olympiad.
Input Format
The first line contains N and Q.
The next line contains N−1 integers p2,…pN describing the tree (1≤pi<i). For each 2≤i≤N, there is an edge between nodes i and pi.
Each of the next Q lines contains integers x and y representing the nodes for that query.
Output Format
For each query, output the expected number of seconds for Bessie to reach node y for the first time starting at node x, modulo 109+7.