题目描述

译自 COCI 2023/2024 Contest #3 T5「Slučajna Cesta」。

Vito 住在一个有 $n$ 个公园的城市，这些公园编号为 $1$ 到 $n$。这些公园被 $n-1$ 条道路相连，满足任意两公园之间都存在一条路径（即构成一棵树）。每个公园均有一个美丽值，第 $i$ 个公园的美丽值为 $v_i$。

昨晚 Vito 决定在城市中走走，原计划是：游览完一个公园后，等概率随机选择一条路，游览这条路通往的公园。但出发前他发现，每条路上都有一条蓝蛇或红蛇：

• 蓝蛇会攻击所有从编号较小的公园前往编号较大的公园的人；
• 红蛇会攻击所有从编号较大的公园前往编号较小的公园的人。

由于 Vito 不想被蛇攻击，他修改了计划：随机选择道路时，只考虑不会被蛇攻击的道路。只要有至少一条安全道路，他就会继续行走（不会停下）。

Vito 忘记了每条路上蛇的颜色，因此他想知道：如果每条路上有蓝蛇或红蛇的概率相同（各为 $\frac{1}{2}$），那么从第 $i$ 个公园开始的路线的美感的期望是多少？

一条路线的美感是路线上经过的所有公园的美丽值的和（每个公园无论经过多少次，每次经过都计算一次美丽值）。路线美感的期望定义为：所有可能的路线的美感乘以 Vito 按这条路线行走的概率的乘积之和。

输入格式

第一行一个整数 $n$（$2 \le n \le 10^6$），表示公园数量。

第二行有 $n-1$ 个整数 $p_i$（$1 \le p_i < i$），表示第 $i+1$ 个公园和第 $p_i$ 个公园之间有一条道路（即树的父节点数组，公园 $i+1$ 的父节点为 $p_i$）。

第三行 $n$ 个整数 $v_i$（$0 \le v_i \le 10^6$），表示第 $i$ 个公园的美丽值。

输出格式

共 $n$ 行，第 $i$ 行输出 Vito 从第 $i$ 个公园开始的路线的美感的期望。

如果期望的值为 $\frac{a}{b}$（$a,b$ 为整数，且 $\gcd(a,b)=1$），则输出 $a \cdot b^{-1} \pmod{10^9+7}$，其中 $b^{-1}$ 是 $b$ 在模 $10^9+7$ 意义下的乘法逆元。

样例 1

输入

2
1
2 1

输出

500000006
2

样例解释

• 道路（1-2）有两种可能：蓝蛇或红蛇，概率各为 $\frac{1}{2}$。
• 从公园 1 出发：
  • 若为蓝蛇：道路禁止从 1→2（1<2，蓝蛇攻击），无安全道路，路线仅包含公园 1，美感为 $2$；
  • 若为红蛇：道路允许从 1→2（红蛇仅攻击 2→1），Vito 走到公园 2；到达公园 2 后，道路禁止从 2→1（2>1，红蛇攻击），无安全道路，路线美感为 $2+1=3$；
  • 期望：$\frac{2 + 3}{2} = 2.5 = \frac{5}{2}$，模 $10^9+7$ 下为 $5 \times 500000004 \equiv 500000006$。
• 从公园 2 出发：
  • 若为蓝蛇：道路允许从 2→1（蓝蛇仅攻击 1→2），Vito 走到公园 1；到达公园 1 后无安全道路，美感为 $1+2=3$；
  • 若为红蛇：道路禁止从 2→1（红蛇攻击），无安全道路，路线仅包含公园 2，美感为 $1$；
  • 期望：$\frac{3 + 1}{2} = 2$，直接输出 $2$。

样例 2

输入

3
1 1
8 8 8

输出

14
14
14

样例解释

两条道路（1-2、1-3）各有红蛇/蓝蛇两种可能，共 $2^2=4$ 种情况，每种概率为 $\frac{1}{4}$。无论蛇的颜色组合如何，从任意公园出发的路线美感期望均为 $14$（所有公园美丽值相同，对称性导致期望一致）。

样例 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

数据范围与提示

详细子任务附加限制及分值如下表所示：

子任务编号	附加限制	分值
1	$n \le 10$	9
2	$n \le 1000$	27
3	序列 $p_i$ 中没有值出现超过 2 次（即树为二叉树）
4	无附加限制	37

评分说明

• 如果程序输出的第一行（从公园 1 出发的期望）正确，但后续输出有误，可在对应测试点获得 $50\%$ 的分数。
• 子任务得分取该子任务下所有测试点的最低分。