레이팅 미적용농부 노조는 베시를 노드 \(1\)이 루트인 \(N\) (\(2 \le N \le 2 \cdot 10^5\))개의 노드를 가진 루트 트리에 가두었다. 겁에 질려 홀로 남은 베시는 매초 다음과 같이 이동한다.
- 베시의 현재 노드에 자식이 없으면, 현재 노드의 조상 중 하나로 무작위로 이동한다 (현재 노드 자신은 제외).
- 그렇지 않으면, 베시는 현재 노드의 자식 중 하나로 무작위로 이동한다.
처음에 베시는 노드 \(x\)에 있고, 유일한 탈출구는 노드 \(y\) (\(1\le x,y\le N\))에 있다. \(x\)와 \(y\)에 대한 \(Q\) (\(1 \le Q \le 2 \cdot 10^5\))개의 독립적인 쿼리 각각에 대해, 베시가 노드 \(x\)에서 출발했을 때 노드 \(y\)에 처음 도달하기까지 걸리는 시간(초)의 기댓값을 \(10^9+7\)로 나눈 나머지로 계산하시오.
문제 제공: Avnith Vijayram
채점 방식
- 입력 4-8: 모든 쿼리에서 \(y=1\).
- 입력 9-13: 모든 쿼리에서 \(x=1\).
- 입력 14-18: 각 \(2 \le i \le N\)에 대해 \(p_i\)는 범위 \([1, i-1]\)에서 균등하게 무작위로 선택된다.
- 입력 19-23: 추가 제약 조건이 없다.
문제 제공: Avnith Vijayram
첫째 줄에 \(N\)과 \(Q\)가 주어진다.
다음 줄에 트리를 나타내는 \(N-1\)개의 정수 \(p_2, \ldots p_N\)이 주어진다 (\(1\le p_i
다음 \(Q\)개의 줄 각각에 해당 쿼리의 노드를 나타내는 정수 \(x\)와 \(y\)가 주어진다.
각 쿼리마다, 베시가 노드 \(x\)에서 출발하여 노드 \(y\)에 처음 도달하기까지 걸리는 시간(초)의 기댓값을 \(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