{"problem":{"name":"[COCI 2023/2024 #3] Slučajna Cesta","description":{"content":"Vito 住在一个有 $n$ 个公园的城市，这些公园编号为 $1$ 到 $n$。这些公园被 $n-1$ 条道路相连，满足任意两公园之间都存在一条路径。每个公园均有一个美丽值，第 $i$ 个公园的美丽值为 $v_i$。 昨晚 Vito 决定在城市中走走，在他游览完一个公园后，他会等概率随机选择一条路，并游览这条路通往的公园。但在出发前，他透过摩天大楼的窗户看到，每条路上都有一条蓝蛇或红蛇。蓝蛇会攻","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10227"},"statements":[{"statement_type":"Markdown","content":"Vito 住在一个有 $n$ 个公园的城市，这些公园编号为 $1$ 到 $n$。这些公园被 $n-1$ 条道路相连，满足任意两公园之间都存在一条路径。每个公园均有一个美丽值，第 $i$ 个公园的美丽值为 $v_i$。\n\n昨晚 Vito 决定在城市中走走，在他游览完一个公园后，他会等概率随机选择一条路，并游览这条路通往的公园。但在出发前，他透过摩天大楼的窗户看到，每条路上都有一条蓝蛇或红蛇。蓝蛇会攻击所有从编号较小的公园前往编号较大的公园的人，红蛇会攻击所有从编号较大的公园前往编号较小的公园的人。由于 Vito 不想被蛇攻击，他决定改变计划，在随机选择道路时只考虑不会被蛇攻击的道路。因为他喜欢长距离行走，所以在至少有一条路他可以安全通过之前，他不会停下脚步。\n\n当 Vito 下楼时，他完全忘记了哪条路上有红蛇或蓝蛇，于是他想知道：「如果每条路上有蓝蛇或红蛇的概率相同，那么我从第 $i$ 个公园开始的路线的美感的期望是多少？」\n\n一条路线的美感是在这条路线上经过的公园的美丽值的和。路线美感的期望定义为对于所有可能的路线，路线的美感乘以 Vito 按这条路线走的概率的乘积之和。\n\n## Input\n\n第一行一个整数 $n\\ (2\\le n\\le 10^6)$，表示公园数量。\n\n第二行有 $n-1$ 个整数 $p_i\\ (1\\le p_i<i)$，表示第 $i+1$ 个公园和第 $p_i$ 个公园之间有一条道路。\n\n第三行 $n$ 个整数 $v_i\\ (0\\le v_i\\le 10^6)$，表示第 $i$ 个公园的美丽值。\n\n## Output\n\n第 $i$ 行输出 Vito 从第 $i$ 个公园开始的路线的美感的期望。如果这个值为 $\\frac{a}{b}$（$a,b$ 为整数），则输出 $ab^{-1} \\pmod{10^9+7}$，其中 $b^{-1}$ 是 $b$ 在模 $10^9+7$ 意义下的逆元。\n\n[samples]\n\n## Background\n\n**译自 [COCI 2023/2024 Contest #3](https://hsin.hr/coci/archive/2023_2024) T5「[Slučajna Cesta](https://hsin.hr/coci/archive/2023_2024/contest3_tasks.pdf)」**\n\n## Note\n\n### 样例解释 1\n\n从第一个公园开始的路线的美感的期望是 $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}$，从第二个公园开始的路线的美感的期望是 $2$。\n\n### 样例解释 2\n\n两条蛇都是红蛇的概率是 $\\frac{1}{4}$，这种情况下如果 Vito 从第一个公园出发，他会随机选择走哪条路。\n\n### 子任务\n\n| 子任务编号 |              附加限制              | 分值 |\n| :--------: | :--------------------------------: | :--: |\n|    $1$     |             $n\\le 10$              | $9$  |\n|    $2$     |           $n\\le 1\\ 000$            | $27$ |\n|    $3$     | 序列 $p_i$ 中没有值出现超过 $2$ 次 | $27$ |\n|    $4$     |             无附加限制             | $37$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10227","tags":["2023","COCI（克罗地亚）"],"sample_group":[["2\n1\n2 1\n","500000006\n2\n"],["3\n1 1\n8 8 8\n","14\n14\n14"],["11\n1 1 1 2 3 4 1 2 6 2\n1 1000 5 3 18 200 8 9 0 2 2\n","968750272\n610352580\n450521029\n536458466\n199219275\n662760680\n190972315\n90277951\n824219264\n941840425\n532552597\n"]],"created_at":"2026-03-03 11:09:25"}}