Description

现在有一棵 $n$ 个节点的有根二叉树。

凡人与神明在这棵树上进行一个游戏。凡人需要从根投下若干个球，每个球带 $1$ 单位正电荷或带 $1$ 单位负电荷。

树上每一个点有容量，第 $i$ 个点可以容纳 $c_i$ 个球。初始每一个点容纳的球数为 $0$。我们称一个点被充满当且仅当它容纳的球的个数等于它的容量。

每一次一个球下落到一个点时：

• 如果该点没有孩子节点或者所有孩子节点上都已经充满球，则停止，该点容纳的球的个数 $+1$；
• 如果该点恰有一个孩子节点未充满，则向那个孩子下落；
• 如果有 $2$ 个孩子节点均未充满：
  • 如果左侧子树中所有球的电荷代数和大于右侧子树所有球的电荷代数和，则如果当前球带正电则向右下落，否则向左下落；
  • 如果左侧子树中所有球的电荷代数和小于右侧子树所有球的电荷代数和，则如果当前球带正电则向左下落，否则向右下落；
  • 如果左侧子树中所有球的电荷代数和等于右侧子树所有球的电荷代数和，则由神明决定向哪个方向下落。

其中，电荷代数和指的是正电荷的数量减去负电荷的数量。

在游戏开始前，双方约定目标点 $u$。在一个回合中，凡人选择这次投下的球的电性，神明按上述规则控制球的下落过程。当 $u$ 被充满时，游戏结束。

凡人希望游戏回合数尽量少，神明希望游戏回合数尽量多。假设双方足够聪明。

对所有：$1\leq u\leq n$，求游戏轮数 $r_u$。

Input Format

第一行，一个正整数 $n$。

第二行，$n-1$ 个整数 $f_2, f_3, \ldots, f_n$，其中 $f_i$ 代表 $i$ 的父亲的编号。

第三行，$n$ 个整数 $c_1, c_2, \ldots, c_n$。

Output Format

输出一行，$n$ 个整数 $r_1, r_2, \ldots, r_n$。

5
1 1 2 2
1 1 1 1 1

5 4 2 3 3

Hint

【数据范围】

本题采用捆绑测试。

• 特殊性质 A：树退化成一条以 $1$ 为一端的链。
• 特殊性质 B：$c_i = 1$。

对于 $100\%$ 的数据，$2 \le n \le 1000$，满足树是以 $1$ 为根的二叉树，$1 \le f_i < i$，$1 \le c_i \le {10}^{12}$。