#1940. 三角形

三角形

三角形

题目描述

标题: 三角形 - 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

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

0
3
1 2
1 1 1
2 2 1

样例 2

0
3
1 1
1 1 1
3 1 1