#1940. 三角形
三角形
三角形
题目描述
标题: 三角形 - Problem - QOJ.ac
#13618. 三角形
The problem was used in the following contests:
Snuke 有一棵 n 个点的有根树,每个点有权值 wi,初始每个结点上都没有石子。
Snuke 准备了一些石子,并把它们拿在手中。她可以进行以下两种操作任意多次:
- 从手中取 wi 个石子放在结点 i 上,进行该操作要求结点 i 的所有孩子 j 上都有 wj 个石子。
- 将结点 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