#PQJ2398x13618. QOJ 2398_13618

    ID: 2808 传统题 3000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:IOI 2019 集训动态规划递推

QOJ 2398_13618

标题: 三角形 - Problem - QOJ.ac

#13618. 三角形

Statistics

The problem was used in the following contests:

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

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

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

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

输入格式

从标准输入读入数据。

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

第二行一个正整数 n 。(n≤2×105)

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

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

输出格式

输出到标准输出。

输出一行 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≤2×105
  • 1≤pi<i
  • 1≤wi≤109

子任务编号特殊性质分值1n≤1592n≤2000193所有w相同64wi≤wi+1125n≤2000 且所有点度数 ≤256除根结点外所有点度数 ≤2137无特殊限制36