题目描述

贵树忆起明里曾对樱花树有过一番独特的审美：将整棵樱花树抽象成一棵以 $1$ 为根大小为 $n$ 的二叉树，每个节点有一朵樱花。将每朵樱花都赋予一个美丽度 $w_i$ ，那么定义樱花树上的一条路径 $p_1\rightarrow \ldots \rightarrow p_m$ （ $m \ge 1$ ）的美丽值为 $m - mex\{ w_{p_1} , w_{p_2} , \ldots , w_{p_m} \}$ 。 $mex$ 为可重集中最小的未出现在可重集内的自然数。

看着眼前的樱花树，贵树想知道对于树上所有路径的美丽值的最大值，以评估整棵树的美丽程度。由于他忘记携带笔记本出行，于是他将这个问题抛给了你。

因为你不是新海诚，所以你需要对于每个节点的子树解决上述问题。

输入格式

第一行一个正整数 $n$ ，表示樱花树的大小。 第二行 $n$ 个数，第 $i$ 个数为 $w_i$ ，表示树中节点 $i$ 上的樱花的美丽度。 第三行 $n-1$ 个数，第 $i$ 个数表示树中节点 $i+1$ 的父亲编号 $fa_{i+1}$ 。

输出格式

输出一行 $n$ 个数。第 $i$ 个数表示 $i$ 节点子树的美丽程度。

数据范围

对于所有数据， $1 \le n \le 3 \times 10^5 , 0 \le w_i < n, 1 \le fa_i < i$ ，给出的树是二叉树。

输入样例 1

15
0 5 1 1 1 3 1 4 0 0 1 3 2 4 1
1 1 2 2 5 6 3 8 7 8 11 11 12 12

输出样例 1

9 5 5 1 3 2 1 4 0 0 4 3 1 1 1

样例解释

以 $1, 8$ 两个节点为例子， $1$ 子树内一条合法的美丽值最大的路径为： $10 \rightarrow 7 \rightarrow 6 \rightarrow 5 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 8 \rightarrow 11 \rightarrow 12 \rightarrow 15$ 。 该路径的长度为 $11$ ， $mex$ 为 $2$ 。 $8$ 子树内一条合法的美丽值最大的路径为： $13 \rightarrow 11 \rightarrow 12 \rightarrow 15$ 。 该路径的长度为 $4$ ， $mex$ 为 $0$ 。