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.
- 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\)
1 2 3
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.