INOI 2016: Wealth Disparity
Computer Science Level pendingIn a company, there are \(N\) employees labelled \(1,2,3 \ldots , N\). The organizational structure of the company forms a treelike 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 

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.
Already have an account? Log in here.