35331번 - Dynamic Instability 다국어

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<i$). For each $2 \le i \le N$, there is an edge between nodes $i$ and $p_i$.

Each of the next $Q$ lines contains integers $x$ and $y$ representing the nodes for that query.

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$.