[R47F]消除电荷 - 代码源竞赛平台

时空限制

1S/512M

题目描述

apiadu 种了一棵树，为了防止树受到伤害，他需要帮助这棵树消除电荷。

这棵树有 $n$ 个点，点的编号为 $1$ 到 $n$，根为 $1$ 号节点，$i$ 号节点（$2 \le i \le n$）的父亲为 $p_i$。初始时，每个点都有一个电荷量，第 $i$ 号节点电荷量为 $a_i$（众所周知，电荷有正负之分，因此 $a_i$ 可正可负可为零）。

apiadu 可以消除一个节点的电荷，假设被他消除电荷的节点为 $u$，那么 $a_u$ 会变为 $0$。

假设 $s_i$ 表示操作后 $i$ 号节点子树内的所有节点 $x$ 的电荷量 $a_x$ 之和，定义这棵树的健康程度为 $\sum_{i=1}^n |s_i|$。

apiadu 没有决定好该消除哪个节点的电荷，因此对于每个 $1 \le u \le n$，请你求出消除节点 $u$ 的电荷后树的健康程度。

格式

输入格式

第一行包含一个整数 $n$，表示树的节点个数。

第二行包含 $n-1$ 个整数 $p_2,p_3,\dots,p_n$，表示每个节点的父亲节点。

第三行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示每个节点初始时的电荷量。

输出格式

输出一行 $n$ 个整数，第 $i$ 个整数表示 $u=i$ 时的答案，即消除节点 $i$ 的电荷后树的健康程度。

样例

样例输入 #1

5
1 2 2 4
-4 4 -7 5 2

样例输出 #1

24 20 27 17 16

样例输入 #2

3
1 1
4 -2 -2

样例输出 #2

8 4 4

样例输入 #3

10
1 1 3 1 2 1 7 1 3
-3 -2 4 3 0 0 5 -2 0 6

样例输出 #3

43 40 32 31 40 40 34 42 40 22

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据：$1 \le n \le 2 \times 10^5$，$1 \le p_i < i$，$|a_i| \le 5 \times 10^7$。

子任务编号	分数	$n \le$	$\lvert a_i \rvert \le$
$1$	$20$	$3000$	$5 \times 10^7$
$2$	$30$	$2 \times 10^5$	$5$
$3$	$50$		$5 \times 10^7$