Indian National Olympiad in Informatics 2016
	Boing Inc, has N employees, numbered 1 ... N. Every employee other than Mr. Hojo (the head of the company) has a manager (P[i] denotes the manager of employee i). Thus an employee may manage any number of other employees but he reports only to one manager, so that the organization forms a tree with Mr. Hojo at the root. We say that employee B is a subordinate of employee A if B appears in the subtree rooted at A.

	Mr. Hojo, has hired Nikhil to analyze data about the employees to suggest how to identify faults in Boing Inc. Nikhil, who is just a clueless consultant, has decided to examine wealth disparity in the company. He has with him the net wealth of every employee (denoted A[i] for employee i). Note that this can be negative if the employee is in debt. He has already decided that he will present evidence that wealth falls rapidly as one goes down the organizational tree. He plans to identify a pair of employees i and j, j a subordinate of i, such A[i] - A[j] is maximum. Your task is to help him do this.

	Suppose, Boing Inc has 4 employees and the parent (P[i]) and wealth information (A[i]) for each employee are as follows:

i		1	2	3	4
A[i]		5	10	6	12
P[i]		2	-1	4	2

P[2] = -1 indicates that employee 2 has no manager, so employee 2 is Mr. Hojo.

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


-----Input format-----
	There will be one line which contains (2*N + 1) space-separate integers. The first integer is N, giving the number of employees in the company. The next N integers A[1], .., A[N] give the wealth of the N employees. The last N integers are P[1], P[2], .., P[N], where P[i] identifies the manager of employee i. If Mr. Hojo is employee i then, P[i] = -1, indicating that he has no manager.


-----Output format-----
	One integer, which is the needed answer.


-----Test data-----
-108 ≤ A[i] ≤ 108, for all i.
Subtask 1 (30 Marks) 1 ≤ N ≤ 500.
Subtask 2 (70 Marks) 1 ≤ N ≤ 105.


-----Sample Input-----
4 5 10 6 12 2 -1 4 2

-----Sample Output-----
6

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '# cook your dish here\n# cook your dish here\nfrom collections import defaultdict\nlist1 = list(map(int,input().split()))\nN = list1[0]\nlist1.pop(0)\nwealth=[]\nparent= {}\nchildren=defaultdict(list)\nfor i in range(N):\n    wealth.append(list1[0])\n    list1.pop(0)\nroot=0\nfor j in range(N):\n    if list1[j] != -1:\n        parent[j] = list1[j]-1\n        children[list1[j]-1].append(j)\n    else:\n        root = j\nleaves=[]\ndowegoup={}\ntobevisited=[root]\nwhile len(tobevisited)>0:\n    temp = tobevisited.pop()\n    if len(children[temp])==0:\n        leaves.append(temp)\n    else:\n        for i in range(len(children[temp])):\n            tobevisited.append(children[temp][i])\n            if wealth[children[temp][i]]>wealth[temp]:\n                dowegoup[children[temp][i]] = False\n            else:\n                dowegoup[children[temp][i]] = True\n#print("wealth: ", wealth, "parents: ", parent, "children; ", children, "leaves: ", leaves, "dowegoup: ", dowegoup)\nvisited={}\ndisparity={}\nanswer=-10**10\nfor j in range(len(leaves)):\n    disparity[leaves[j]]=0\nwhile len(leaves)>0:\n    temp = leaves.pop(0)\n    if parent[temp] not in disparity:\n        disparity[parent[temp]] = wealth[parent[temp]] - wealth[temp]\n        if disparity[temp]>0:\n            disparity[parent[temp]] += disparity[temp]\n    else:\n        if disparity[temp]>0:\n            gladiator = wealth[parent[temp]]-wealth[temp] +disparity[temp]\n        else:\n            gladiator = wealth[parent[temp]]-wealth[temp]\n        disparity[parent[temp]] = max(gladiator,disparity[parent[temp]])\n    if parent[temp]!=root:\n        visited[parent[temp]] = True\n        leaves.append(parent[temp])\n    if disparity[parent[temp]]>answer:\n        answer = disparity[parent[temp]]\n#print("disparity: ", disparity)\nprint(answer)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14939