Description

Given a tree with $n$ nodes. Each node has a weight and a parameter. For node $i$, its weight is $w_i$ and its parameter is $c_i$. Node $1$ is the root.

Now, for each node $u$ ($1 \leq u \leq n$), find the longest chain $v_1, v_2, \dots v_m$ on the tree that satisfies the following conditions:

1. $v_1 = u$.
2. For $2 \leq i \leq m$, $v_i$ is the parent of $v_{i - 1}$.
3. The sum of weights on the chain does not exceed $c_u$, i.e., $\sum_{j = 1}^m w_{v_j} \leq c_u$.

Input Format

The first line contains an integer $n$, the number of nodes in the tree.
The second line contains $n - 1$ integers $p_2, p_3, \dots p_n$, where $p_i$ denotes the parent of node $i$.
The third line contains $n$ integers; the $i$-th integer is the weight $w_i$ of node $i$.
The fourth line contains $n$ integers; the $i$-th integer is the parameter $c_i$ of node $i$.

Output Format

Output one line with $n$ space-separated integers. The $i$-th integer denotes the maximum length of the chain corresponding to node $i$.

5
1 1 2 2
1 2 3 4 5
1 3 3 6 8

1 2 1 2 3

Hint

Constraints

For all testdata, it is guaranteed that $1 \leq u, v \leq n \leq 10^5$，$1 \leq p_i \lt i$，$1 \leq w_i \leq c_i \leq 10^9$.

Translated by ChatGPT 5