寻觅（seek.cpp/.in/.out）1s 512MB

题目描述

当你计算上一题的时候，你的心里是非常紧张的，因为你不知道，你所计算的B和答案的差别到底是多少。当时你的心跳都快停止了，如果爆零，那可糟糕了！

就在你的心脏即将停止的时候，你发现，你的解法和正解差别并不大，你终于松了口气。但你还是很紧张，因为不仅助教小明在做梦，你也在梦游。你更不会想到，你竟然将自己的梦境录入到网络上去了。

网上很热闹，因为网上很多人都在关注你的梦境。在你的梦境里，你的偶像李小强制作出了一个神奇的树。

这是一棵有 $n$ 个点的有根树。树根为 $1$ 号节点，每个节点上有一个权值 $w_i$ 。

大家都不知道这些权值有什么含义，很快网上的各种评论就疯狂刷屏了。

"我去，真的假的，我没有眼花吧！" "李小强制作出来的吗？" "卧槽，真的假的啊！这么牛x的吗？" "这是一个什么样的梦啊！" ...... 李小强在看到网友们的反应时，他笑了，他知道这些网友一定不会知道这些权值的含义，他们只会认为这只是梦境里一些胡编乱造的数字。

你的助教小明见到网友们的反应后也是哈哈笑着，因为他知道这些数字是可以用来解谜的。小明知道这个谜题来自学校的最新小说《最佳男主角》，破解这个谜题的人可以找到自己的心上人。

为了帮小明找到他的小红，你熟练地翻到书本的最后一页，看到了解密方法：

“这棵树上本来应该放有魔法石，但现在所有节点上都没有石子

你的手上有一些石子，可以进行两种操作任意多次：

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

你需要知道对于每个 $i$ ，为了在节点 $i$ 上放 $w_i$ 个石子，至少应该准备多少石子。

如果自己孰轻孰重都不知道，又怎么能知道自己对别人来说是什么分量呢？”

说干就干，你操起键盘，开始计算。

输入格式

第一行，一个整数 $id$ ，表示测试点编号

第二行，一个整数 $n$

第三行， $n-1$ 个整数，第 $i-1$ 个整数 $fa_i$ 表示 $i$ 号节点的父亲 $(fa_i<i)$

第四行， $n$ 个整数 $w_i$

输出格式

输出一行， $n$ 个整数 $ans_i$ 表示对于节点 $i$ ，为了在节点 $i$ 上放 $w_i$ 个石子，至少需要的石子数

样例输入

0
5
1 2 2 3
5 6 6 3 5

样例输出

15 15 11 3 5

数据范围

对于所有数据，保证 $n\leq2\times10^5,1\le w_i\le 10^9$

测试点编号	特殊性质
1~2	$n\le 15$
3~4	$n\le 2000$ 且所有节点度数 $\le 2$
5~8	$n\le 2000$ 且除根节点外所有节点度数 $\le 2$
9~10	$n\le 2000$
11~12	所有 $w_i$ 均相同
13~14	$w_i\le w_{i+1}$
15~20	无特殊性质