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\)


  • Input:
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...