Background

Translated from COCI 2023/2024 Contest #3 T5 “Slučajna Cesta”.

Problem Description

Vito lives in a city with $n$ parks, numbered from $1$ to $n$. The parks are connected by $n-1$ roads, and there is a path between every pair of parks. Each park has a beauty value; the beauty value of park $i$ is $v_i$.

Last night, Vito decided to take a walk in the city. After he visits a park, he randomly chooses one road with equal probability and visits the park that the road leads to. However, before leaving, he looked out of a skyscraper window and saw that every road has either a blue snake or a red snake. Blue snakes attack everyone who travels from a park with a smaller number to a park with a larger number, while red snakes attack everyone who travels from a park with a larger number to a park with a smaller number. Since Vito does not want to be attacked by snakes, he decided to change his plan: when choosing a road at random, he only considers roads that he can pass safely without being attacked by snakes. Because he likes long walks, he will not stop as long as there is at least one road he can safely take.

When Vito went downstairs, he completely forgot which road had a red snake and which had a blue snake, so he wants to know: “If each road is equally likely to have a blue snake or a red snake, what is the expected beauty of my route if I start from park $i$?”

The beauty of a route is the sum of the beauty values of the parks visited along that route. The expected beauty of a route is defined as the sum, over all possible routes, of (the route beauty) multiplied by (the probability that Vito walks along that route).

Input Format

The first line contains an integer $n\ (2\le n\le 10^6)$, the number of parks.

The second line contains $n-1$ integers $p_i\ (1\le p_i<i)$, meaning there is a road between park $i+1$ and park $p_i$.

The third line contains $n$ integers $v_i\ (0\le v_i\le 10^6)$, where $v_i$ is the beauty value of park $i$.

Output Format

On the $i$-th line, output the expected beauty of Vito’s route starting from park $i$. If this value is $\frac{a}{b}$ (where $a,b$ are integers), output $ab^{-1} \pmod{10^9+7}$, where $b^{-1}$ is the modular inverse of $b$ modulo $10^9+7$.

2
1
2 1

500000006
2

3
1 1
8 8 8

14
14
14

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

Hint

Sample Explanation 1

The expected beauty of the route starting from the first park is $2.5\pmod{10^9+7}=\frac{5}{2}\pmod{10^9+7}=5\cdot 2^{-1}\pmod{10^9+7}=5\cdot 500000004\pmod{10^9+7}=500000006\pmod{10^9+7}$, and the expected beauty of the route starting from the second park is $2$.

Sample Explanation 2

The probability that both snakes are red snakes is $\frac{1}{4}$. In this case, if Vito starts from the first park, he will randomly choose which road to take.

Subtasks

Translated by ChatGPT 5