P15265 [USACO26JAN2] Dynamic Instability P

Farmer Nhoj has trapped Bessie on a rooted tree with $N$ ($2 \le N \le 2 \cdot 10^5$) 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\le x,y\le N$). For $Q$ ($1 \le Q \le 2 \cdot 10^5$) 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 $10^9+7$.

The first line contains $N$ and $Q$. The next line contains $N-1$ integers $p_2, \ldots p_N$ describing the tree ($1\le p_i

For each query, output the expected number of seconds for Bessie to reach node $y$ for the first time starting at node $x$, modulo $10^9+7$.

#### Sample 1 Explanation - In the $1$st query, the expected time to reach node $1$ from itself is $0$. - In the $3$rd query, after $1$ second, Bessie will be at node $1$ with probability $\frac{1}{2}$ and at node $2$ with probability $\frac{1}{2}$. 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 + \frac{1}{2} \cdot 0 + \frac{1}{2} \cdot 4 = 3$. #### Sample 2 Explanation In the $3$rd query, the expected time to reach node $3$ from node $1$ is $\frac{15}{2}$. SCORING: - Inputs 4-8: For all queries, $y=1$. - Inputs 9-13: For all queries, $x=1$. - Inputs 14-18: For each $2 \le i \le N$, $p_i$ is uniformly randomly chosen from the range $[1, i-1]$. - Inputs 19-23: No additional constraints.