Longest Valid Ancestral Chain in a Tree

You are given a tree with n nodes. Each node has an associated weight and a parameter. For node i, its weight is \(w_i\) and its parameter is \(c_i\). The node 1 is the root of the tree.

For every node \(u\) (\(1 \le u \le n\)), find the longest chain of nodes \(v_1, v_2, \dots, v_m\) satisfying the following conditions:

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

If even \(w_u\) is greater than \(c_u\), then the chain is considered invalid and its length is 0. For every node \(u\), output the maximum possible length of such a chain.

inputFormat

The input consists of the following:

• The first line contains an integer n (the number of nodes in the tree).
• The second line contains n space-separated integers: \(w_1, w_2, \dots, w_n\) representing the weight of each node.
• The third line contains n space-separated integers: \(c_1, c_2, \dots, c_n\) representing the parameter for each node.
• The fourth line contains n-1 space-separated integers: for i = 2 \dots n, the i-th integer represents the parent of node i in the tree. Node 1 is the root and does not have a parent.

outputFormat

Output a single line containing n space-separated integers. The u-th integer denotes the maximum length of the valid chain for node u.

sample

5
1 1 2 2 3
3 3 5 6 7
1 1 2 2

1 2 2 3 3