문제
Vito는 1부터 n까지 번호가 매겨진 n개의 공원이 있는 도시에 살고 있습니다. 이 공원들은 어떤 두 공원 간에도 경로가 있는 방식으로 n - 1개의 도로로 연결되어 있습니다. 각각의 공원은 아름다움 값이 있으며, i번째 공원의 아름다움 값은 vi입니다.
어젯밤 Vito는 도시 주변을 방황하기로 결정했습니다. 공원을 방문한 후에는 같은 확률로 무작위 도로를 선택하고 해당 도로가 이끄는 공원을 방문합니다. 그러나 여정을 시작하기 전에 그는 자신의 고층 건물 창문을 통해 내다보았고 모든 도로에는 파란색 또는 빨간색 뱀이 있다는 것을 알아냈습니다. 파란색 뱀은 낮은 레이블의 공원에서 높은 레이블의 공원으로 이동하는 모든 사람을 공격하고, 빨간색 뱀은 높은 레이블의 공원에서 낮은 레이블의 공원으로 이동하는 모든 사람을 공격합니다. Vito는 뱀에게 공격당하고 싶지 않기 때문에 임의의 도로를 선택할 때 뱀에게 공격받지 않을 도로만 고려하고자 계획을 바꾸기로 했습니다. 그는 긴 산책을 좋아하므로 적어도 하나의 안전한 도로가 있는 경우에만 여정을 멈추기로 했습니다.
Vito는 자신의 고층 건물의 계단을 내려가면서 어떤 도로에 빨간색 또는 파란색 뱀이 있는지 완전히 잊어버렸기 때문에 그는 궁금해졌습니다. 모든 도로에 파란색 또는 빨간색 뱀이 나타날 확률이 동일하다면, i번째 공원에서 시작하는 내 여정의 기대 아름다움은 무엇일까요?
경로의 아름다움은 해당 여정에서 방문한 공원들의 아름다움 값의 합입니다. 여정의 기대 아름다움은 각각의 가능한 경로에 대한 해당 경로의 아름다움 값과 Vito가 그 경로를 선택할 확률의 곱의 합으로 정의됩니다.
입력
첫 번째 줄에는 정수 n이 있습니다 (2 ≤ n ≤ 1,000,000) - 공원의 수
두 번째 줄에는 n - 1개의 정수 pi (1 ≤ pi < i)가 있습니다 - (i + 1)-번째 공원과 pi-번째 공원을 연결하는 도로
세 번째 줄에는 n개의 정수 vi (0 ≤ vi ≤ 1,000,000)가 있습니다 - i번째 공원의 아름다움 값
출력
만약 i번째 공원에서 시작하는 Vito의 여정의 기대 아름다움이 a/b라면, 출력의 i번째 줄에는 ab−1(mod 109 + 7)이 출력됩니다. 여기서 b−1은 b에 대한 모듈러 역원(mod 109 + 7)입니다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 10점 | |
| #2 | 30점 | |
| #3 | 30점 | |
| #4 | 30점 | 추가 제약 조건 없음 |
예제 #1
2
1
2 1
500000006
2
첫 번째 공원에서 시작하는 여정의 기대 아름다움은 2.5 (mod 10^9+7) = 5/2 (mod 10^9+7) = 5·2^−1 (mod 10^9 + 7) = 5 · 500000004 (mod 10^9 + 7) = 500000006 (mod 10^9 + 7)이며, 두 번째 공원에서 시작하는 경우에는 2입니다.
예제 #2
3
1 1
8 8 8
14
14
14
양쪽 뱀이 모두 빨간색인 경우의 확률은 1/4 이며, 이 경우 Vito가 첫 번째 공원에서 시작하면 무작위로 어떤 도로를 선택할지 결정합니다.
예제 #3
11
1 1 1 2 3 4 1 2 6 2
1 1000 5 3 18 200 8 9 0 2 2
968750272
610352580
450521029
536458466
199219275
662760680
190972315
90277951
824219264
941840425
532552597
로그인해야 코드를 작성할 수 있어요.