[AdditionalFile5600.zip](file://AdditionalFile5600.zip?type=additional_file)

#5600. 「USACO 2026 Second Platinum」Dynamic Instability

标签: 传统 | 时间限制: 2000 ms | 内存限制: 256 MiB |

题目描述

题目译自 USACO 2026 Second Contest, Platinum Problem 3. Dynamic Instability

Nhoj 农夫将 Bessie 困在一棵包含 $N$（$2 \le N \le 2 \cdot 10^5$）个节点的有根树上，其中节点 $1$ 为根。既惊恐又孤独的 Bessie 每秒钟会进行如下移动：

• 如果 Bessie 当前所在的节点没有子节点，那么她将移动到当前节点的一个随机祖先节点（不包括该节点本身）。
• 否则，Bessie 将移动到当前节点的一个随机子节点。

最初，Bessie 位于节点 $x$，而她唯一的出路是位于节点 $y$（$1\le x,y\le N$）的出口。对于 $Q$（$1 \le Q \le 2 \cdot 10^5$）个关于 $x$ 和 $y$ 的独立询问，请计算 Bessie 从节点 $x$ 出发首次到达节点 $y$ 所需的期望秒数，结果对 $10^9+7$ 取模。

输入格式

第一行包含 $N$ 和 $Q$。

下一行包含 $N-1$ 个整数 $p_2, \ldots p_N$，描述这棵树（$1\le p_i<i$）。对于每个 $2 \le i \le N$，在节点 $i$ 和 $p_i$ 之间有一条边。

接下来的 $Q$ 行，每行包含整数 $x$ 和 $y$，代表该次询问的节点。

输出格式

对于每次询问，输出 Bessie 从节点 $x$ 出发首次到达节点 $y$ 所需的期望秒数，结果对 $10^9+7$ 取模。

样例 1

输入

13 10
1 2 2 4 3 1 5 6 4 7 8 10
1 12
10 6
5 12
1 13
13 10
6 4
7 12
3 1
12 8
2 1

输出

166666700
21
2
166666701
500000023
18
166666704
750000018
800000021
500000018

在第 $1$ 个询问中，从节点 $1$ 到达其自身的期望时间为 $0$。

在第 $3$ 个询问中，经过 $1$ 秒后，Bessie 有 $\frac{1}{2}$ 的概率位于节点 $1$，有 $\frac{1}{2}$ 的概率位于节点 $2$。由于从节点 $2$ 到达节点 $1$ 的期望时间是 $4$，因此 Bessie 从节点 $3$ 出发到达节点 $1$ 的期望时间是 $1 + \frac{1}{2} \cdot 0 + \frac{1}{2} \cdot 4 = 3$。

样例 2

输入

5 5
1 2 2 1
1 1
1 2
1 3
1 4
1 5

输出

0
3
500000011
500000011
6

在第 $3$ 个询问中，从节点 $1$ 到达节点 $3$ 的期望时间是 $\frac{15}{2}$。

样例 3

输入

13 10
1 2 2 4 3 1 5 6 4 7 8 10
1 12
10 6
5 12
1 13
13 10
6 4
7 12
3 1
12 8
2 1

输出

166666700
21
2
166666701
500000023
18
166666704
750000018
800000021
500000018

数据范围与提示

• 测试点 4-8：对于所有询问，满足 $y=1$
• 测试点 9-13：对于所有询问，满足 $x=1$
• 测试点 14-18：对于每个 $2 \le i \le N$，$p_i$ 是从范围 $[1, i-1]$ 中均匀随机选择的
• 测试点 19-23：无额外约束

供题：Avnith Vijayram