UOJ Logo Universal Online Judge

UOJ

#418. 【集训队作业2018】三角形

附件下载 统计

Snuke 有一棵 $n$ 个点的有根树,每个点有权值 $w_i$,初始每个结点上都没有石子。

Snuke 准备了一些石子,并把它们拿在手中。她可以进行以下两种操作任意多次:

  1. 从手中取 $w_i$ 个石子放在结点 $i$ 上,进行该操作要求结点 $i$ 的所有孩子 $j$ 上都有 $w_j$ 个石子。
  2. 将结点 $i$ 上的所有石子收回手中。

Takahashi 想知道对于每个 $i$,为了在结点 $i$ 上放 $w_i$ 个石子,Snuke 至少需要准备多少石子。

输入格式

从标准输入读入数据。

第一行一个数字 $T$ 表示这个子任务的编号。

第二行一个正整数 $n$ 。$(n \leq 2 \times 10^5)$

第三行 $n-1$ 个正整数,第 $i-1$ 个数 $p_i$ 表示 $i$ 的父亲。$(p_i < i)$

第四行 $n$ 个正整数,第 $i$ 个数为 $w_i$ 。

输出格式

输出到标准输出。

输出一行 $n$ 个正整数,第 $i$ 个数为结点 $i$ 的答案。

样例一

input

0
3
1 2
1 1 1

output

2 2 1

样例二

input

0
3
1 1
1 1 1

output

3 1 1

限制及约定

对于所有数据,保证:

  • $n \leq 2 \times 10^5$
  • $1 \le p_i < i$
  • $1 \le w_i \le 10^9$
子任务编号特殊性质分值
1$n \leq 15$9
2$n \leq 2000$19
3所有$w$相同6
4$w_i \leq w_{i+1}$12
5$n \leq 2000$ 且所有点度数 $\leq 2$5
6除根结点外所有点度数 $\leq 2$13
7无特殊限制36

时间限制:$3\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载