# INOI 2016: Wealth Disparity

In a company, there are $$N$$ employees labelled $$1,2,3 \ldots , N$$. The organizational structure of the company forms a tree-like hierarchy.

• $$P_i$$ denotes the manager of employee $$i$$.
• For each employee $$i$$, $$A_i$$ denotes the wealth of employee $$i$$.

We say that employee $$j$$ is the subordinate of employee, $$i$$ if employee $$j$$ appears in a subtree rooted at $$i$$.

Your task is to find a pair of employees $$(i,j)$$, $$j$$ a subordinate of $$i$$, such that $$A_i - A_j$$ is maximized. Enter your answer as the value of $$A_i - A_j$$.

Here is the data.

## Input Format

• The first line contains $$N$$.
• The second line contains $$A_1, A_2, \ldots A_N$$.
• The third line contains $$P_1, P_2, \ldots P_N$$. If $$i$$ is the boss of the company, he has no manager, i.e, $$P_i = -1$$

## Example

• Input:
 1 2 3 4 5 10 6 12 2 -1 4 2 

• Expected Output: 6

• Explanation: In this case, the possible choices to consider are (2,1) with a difference in wealth of of 5, (2,3) with 4, (2,4) with -2 and (4,3) with 6. So the answer is 6.

×

Problem Loading...

Note Loading...

Set Loading...