[COCI 2023/2024 #3] Slučajna Cesta

Luogu

IDLGP10227

Time3000ms

Memory512MB

DifficultyP5

2023COCI（克罗地亚）

Vito 住在一个有 $n$ 个公园的城市，这些公园编号为 $1$ 到 $n$。这些公园被 $n-1$ 条道路相连，满足任意两公园之间都存在一条路径。每个公园均有一个美丽值，第 $i$ 个公园的美丽值为 $v_i$。昨晚 Vito 决定在城市中走走，在他游览完一个公园后，他会等概率随机选择一条路，并游览这条路通往的公园。但在出发前，他透过摩天大楼的窗户看到，每条路上都有一条蓝蛇或红蛇。蓝蛇会攻击所有从编号较小的公园前往编号较大的公园的人，红蛇会攻击所有从编号较大的公园前往编号较小的公园的人。由于 Vito 不想被蛇攻击，他决定改变计划，在随机选择道路时只考虑不会被蛇攻击的道路。因为他喜欢长距离行走，所以在至少有一条路他可以安全通过之前，他不会停下脚步。当 Vito 下楼时，他完全忘记了哪条路上有红蛇或蓝蛇，于是他想知道：「如果每条路上有蓝蛇或红蛇的概率相同，那么我从第 $i$ 个公园开始的路线的美感的期望是多少？」一条路线的美感是在这条路线上经过的公园的美丽值的和。路线美感的期望定义为对于所有可能的路线，路线的美感乘以 Vito 按这条路线走的概率的乘积之和。 ## Input 第一行一个整数 $n\ (2\le n\le 10^6)$，表示公园数量。第二行有 $n-1$ 个整数 $p_i\ (1\le p_i<i)$，表示第 $i+1$ 个公园和第 $p_i$ 个公园之间有一条道路。第三行 $n$ 个整数 $v_i\ (0\le v_i\le 10^6)$，表示第 $i$ 个公园的美丽值。 ## Output 第 $i$ 行输出 Vito 从第 $i$ 个公园开始的路线的美感的期望。如果这个值为 $\frac{a}{b}$（$a,b$ 为整数），则输出 $ab^{-1} \pmod{10^9+7}$，其中 $b^{-1}$ 是 $b$ 在模 $10^9+7$ 意义下的逆元。 [samples] ## Background **译自 [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)」** ## Note ### 样例解释 1 从第一个公园开始的路线的美感的期望是 $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$。 ### 样例解释 2 两条蛇都是红蛇的概率是 $\frac{1}{4}$，这种情况下如果 Vito 从第一个公园出发，他会随机选择走哪条路。 ### 子任务 | 子任务编号 | 附加限制 | 分值 | | :--------: | :--------------------------------: | :--: | | $1$ | $n\le 10$ | $9$ | | $2$ | $n\le 1\ 000$ | $27$ | | $3$ | 序列 $p_i$ 中没有值出现超过 $2$ 次 | $27$ | | $4$ | 无附加限制 | $37$ |

Samples

Input #1

2
1
2 1

Output #1

500000006
2

Input #2

3
1 1
8 8 8

Output #2

14
14
14

Input #3

11
1 1 1 2 3 4 1 2 6 2
1 1000 5 3 18 200 8 9 0 2 2

Output #3

API Response (JSON)

{
  "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 决定在城市中走走，在他游览完一个公园后，他会等概率随机选择一条路，并游览这条路通往的公园。但在出发前，他透过摩天大楼的窗户看到，每条路上都有一条蓝蛇或红蛇。蓝蛇会攻...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments