插线板

问题一句话

把所有插排看成一棵以 1 号为根的树。 每个节点 i 上有 a[i] 个充电器。 问：对每个节点 i，它要给它整棵子树里的所有充电器供电，总数是多少？

具体说明

• 一共有 n 个插排（编号 1..n），1 号插排接在墙上的唯一插座上。
• 对于 i=2..n，给定一个 u[i]（并保证 u[i] < i），表示"编号 i 的插排插在 u[i] 的插排上"。 这就形成了一棵有根树：父亲是 u[i]，根是 1。
• a[i] 表示第 i 个插排上直接插着的充电器数量。
• 定义"插排 i 向某个充电器供电" ：从根 1 出发的电流要通到这个充电器，路径中经过了插排 i。 因而，插排 i 供电的充电器个数 = 它的整棵子树里所有 a[j] 的总和。

直观理解：电流从 1 往下流，经过哪个插排，那个插排就要"负责"它下面所有插排上的充电器。

你需要做什么

输出 n 个数，第 i 个数是插排 i 供电的充电器总数（即以 i 为根的子树上所有 a[j] 之和）。

输入格式

• 第 1 行：整数 n（插排数量）。
• 第 2 行：n-1 个整数 u[2], u[3], ..., u[n]（每个 u[i] < i）。
• 第 3 行：n 个整数 a[1], a[2], ..., a[n]（每个插排上直接插着的充电器数量）。

输出格式

• 一行 n 个整数，用空格分隔。 第 i 个数为插排 i 供电的充电器数量。

样例

输入

6
1 2 1 4 5
1 2 3 1 2 4

输出

13 5 3 7 6 4

解释 树的结构（父亲 → 儿子）：

• 2 接在 1 上，3 接在 2 上，4 接在 1 上，5 接在 4 上，6 接在 5 上。 各点子树和：
• 6：只有自己 → 4
• 5：自己 2 + 子(6) 4 → 6
• 4：自己 1 + 子(5) 6 → 7
• 3：自己 3 → 3
• 2：自己 2 + 子(3) 3 → 5
• 1：自己 1 + 子(2) 5 + 子(4) 7 → 13

数据范围

• \(2 \le n \le 1e6\)
• \(0 \le a[i] \le 1e9\)
• \(1 \le u[i] < i\)（保证形成一棵以 1 为根的树）