Dynamic Instability
다이아몬드 IV의견: 0
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\).
Problem credits: Avnith Vijayram
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.
Problem credits: Avnith Vijayram
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
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\).
5 5
1 2 2 1
1 1
2 1
3 1
4 1
5 10
4
3
3
1In 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\).
5 5
1 2 2 1
1 1
1 2
1 3
1 4
1 50
3
500000011
500000011
6In the \(3\)rd query, the expected time to reach node \(3\) from node \(1\) is
\(\frac{15}{2}\).
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 1166666700
21
2
166666701
500000023
18
166666704
750000018
800000021
500000018riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > Second Contest > Platinum
평가 및 의견
Dynamic Instability
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Dynamic Instability