You are given an undirected weighted tree, in which 1 is the root node. Control value of each node denoted by c_i.

Let's take two nodes (V,U ) such that V is the ancestor of U. V controls U if the distance between U and V is less than or equal to the control value of U

Find the number of vertices controlled by each node.

Task:

Print N integers — the i-th of these numbers should be equal to the number of vertices that the i-th vertex controls.

Note

• Assume 1-based indexing.

Example:

Assumptions

• N = 3
• c = {2,7,5}
• p = {1,1}
• w = {5,4}

Approach

• Node 1 controls 2 because distance between 1 and 2 is 5 which less than control value of 2, which is 7
• Node 1 controls 3 because distance between 1 and 3 is 4 which is less than control value of 3, which is 5

Thus, answer is {2,0,0}

Function Description :

Complete the solve function provided in the editor. This function takes the following 4 parameters and returns the required answer:-

• N: Integer denoting the number of nodes
• c: Integer array denoting control values of each node
• p: Parent array, where p_i  denotes the parent of the (i+1)-th node in the tree
• w: Integer array, where w_i  denotes weight of the edge between p_i and (i+1)

The function must return  -

• array of N integers — the i-th integer equal to number of nodes that the i-th node controls.

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

• The first line contains single integer N
• The second line contains N  integers c_i — the control value of i-th node.
• The third line contains (N−1) integers. p_i   — the parent of the (i+1)-th node in the tree
• The fourth line contains (N−1) integers.  w_i  — weight of the edge between pi and (i+1)

Output format

• Print N integers — the i-th of these integers equal to the number of nodes that the i-th node controls.

Constraints

\(1 \leq N \leq 2 * 10^5\)

\(1 \leq c_i \leq 10 ^{9}\)

\(1 \leq p_i \leq N\)

\(1 \leq w_i \leq 10 ^{9}\)

Code snippets (also called starter code/boilerplate code) 

This question has code snippets for C, CPP, Java, and Python.