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

Difficulty: interview

Starter code:

Solutions:
import sys
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

arr=[int(x) for x in input().split()]

if arr[0]==1:
    print(0)
    return

p=[None]
for i in range(1,arr[0]+1):
    p.append(arr[i])
    
a=[None]
for i in range(arr[0]+1,2*arr[0]+1):
    a.append(arr[i])

graph=defaultdict(list)

n=len(a)-1
for i in range(1,n+1):
    if a[i]==-1:
        source=i
        continue
    graph[a[i]].append((i,(p[a[i]]-p[i])))

def func(node):
    nonlocal res
    
    if len(graph[node])==0:
        return -10**9
    
    curr=-10**9
    for child in graph[node]:
        x=max(child[1],(func(child[0])+child[1]))
        curr=max(curr,x)
        res=max(curr,res)
    
    return curr    

res=-10**9
curr=func(source)
print(res)        
        
        
        


li = list(map(int, input().split()))

n, d = li[0], dict()
wealths = [None]+li[1:n+1]
parents = li[n+1:]

for k in list(range(1, n+1)):
    d[k] = []
    
max_diff = -200000000
root = None

for i in range(len(parents)):
    if parents[i] != -1:
        d[parents[i]].append(i+1)
    else:
        root = i+1

q = [root]
indices = [0 for x in range(n+1)]

while len(q) > 0:
    last = q[-1]
    curr = d[last]
    
    if indices[last] < len(curr) and len(curr) >= 1:
        rn = curr[indices[last]]
        indices[last] += 1
        q.append(rn)
        
        for num in q:
            if num != rn:
                if wealths[num]-wealths[rn] > max_diff:
                    max_diff = wealths[num]-wealths[rn];
    else:
        q.pop(-1)

print(max_diff)

li = list(map(int, input().split()))
n, d = li[0], dict()
wealths = [None]+li[1:n+1]
parents = li[n+1:]

for k in list(range(1, n+1)):
    d[k] = []
    
max_diff = -2 * int(1e8)
root = None

for i in range(len(parents)):
    if parents[i] != -1:
        d[parents[i]].append(i+1)
    else:
        root = i+1

q = [root]
indices = [0 for x in range(n+1)]

while len(q) > 0:
    curr = d[q[-1]]
    
    if indices[q[-1]] < len(curr) and len(curr) >= 1:
        rn = curr[indices[q[-1]]]
        indices[q[-1]] += 1
        q.append(rn)
        
        for num in q:
            if num != rn:
                if wealths[num]-wealths[rn] > max_diff:
                    max_diff = wealths[num]-wealths[rn];
    else:
        q.pop(-1)

print(max_diff)

# cook your dish here
from collections import defaultdict
from collections import deque
a = list(map(int,input().split()))
n = a[0]
v = a[1:n+1]
p = a[n+1:]
ans = -1000000000
boss = 1
graph = defaultdict(set)
for i in range(n):
    if p[i] == -1:
        boss = i+1
        continue
    else:
        graph[p[i]].add(i+1)
        
def bfs(boss, graph, n):
    nonlocal ans
    que = deque([])
    que.append(boss)
    while que:
        key = que.popleft()
        for item in graph[key]:
            que.append(item)
            z = v[key-1] - v[item-1]
            if(ans<z):
                ans = z 
            if v[key-1] > v[item-1]:
                v[item-1] = v[key-1]
bfs(boss, graph, n)
print(ans)

        
    


# cook your dish here
inputs = list(map(int, input().split()))
n = inputs[0]
A = inputs[1:n+1]
P = inputs[n+1:]
arr = [[] for _ in range(n)]

boss = None
for j, i in enumerate(P):
    if i == -1:
        boss = j
    else:
        arr[i-1].append(j)

def BFS(array, start):
    queue = []
    queue.append(boss)
    maxi = -10000000000000000000000
    while queue:
        cur = queue.pop(0)
        val = A[cur]
        for i in arr[cur]:
            queue.append(i)
            cur_val = A[i]
            check = val-cur_val
            
            if check>maxi:
                maxi= check
            if val>cur_val:
                A[i] = val
    return maxi

if n==1:
    print(0)
else:
    print(BFS(arr,boss))

# cook your dish here
from collections import defaultdict
from operator import itemgetter
from collections import deque

def visit(v):
    height[v][1]=0
    i=0
    coda=deque()
    coda.append(v)
    while len(coda)>0:
        num=len(coda)
        i+=1
        for _ in range(num):
            u=coda.popleft()
            for son in sons[u]:
                height[son][1]=i
                coda.append(son)
    return 

inp=list(map(int, input().split()))
n=inp[0]
wealth=inp[1:n+1]
father=[i-1 if i>0 else i for i in inp[n+1:]]
sons=defaultdict(lambda:[])
for i in range(n):
    if father[i]!=-1:
        sons[father[i]].append(i)
    else:
        boss=i

height=[[i,0] for i in range(n)]
visit(boss)

height.sort(key=itemgetter(1), reverse=True)
minimi=[0]*n
diff=[0]*n

for el in height:
    v=el[0]
    if len(sons[v])==0:
        minimi[v]=wealth[v]
        diff[v]=-float('Inf')
    else:
        minimo=min([minimi[u] for u in sons[v]]) 
        minimi[v]=min(minimo, wealth[v])
        diff[v]=max(max([diff[u] for u in sons[v]]), wealth[v]-minimo)

print(diff[boss])
    


# cook your dish here
from multiprocessing import SimpleQueue as queue
from collections import defaultdict
from operator import itemgetter

def visit(v, i):
    height[v][1]=i
    for u in sons[v]:
        visit(u, i+1)
    return 

inp=list(map(int, input().split()))
n=inp[0]
wealth=inp[1:n+1]
father=[i-1 if i>0 else i for i in inp[n+1:]]
sons=defaultdict(lambda:[])
for i in range(n):
    if father[i]!=-1:
        sons[father[i]].append(i)
    else:
        boss=i
height=[[i,0] for i in range(n)]
visit(boss, 0)
height.sort(key=itemgetter(1), reverse=True)
minimi=[0]*n
diff=[0]*n
for el in height:
    v=el[0]
    if len(sons[v])==0:
        minimi[v]=wealth[v]
        diff[v]=-float('Inf')
    else:
        minimo=min([minimi[u] for u in sons[v]]) 
        minimi[v]=min(minimo, wealth[v])
        diff[v]=max(max([diff[u] for u in sons[v]]), wealth[v]-minimo)
print(diff[boss])
    

'''
coda=queue()
for i in range(n):
    if len(sons[i])==0:
        coda.put(i)
        visited[i]=1
while len(coda)>0:
    '''

import sys
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

arr=[int(x) for x in input().split()]

if arr[0]==1:
    print(0)
    return

p=[None]
for i in range(1,arr[0]+1):
    p.append(arr[i])
    
a=[None]
for i in range(arr[0]+1,2*arr[0]+1):
    a.append(arr[i])

graph=defaultdict(list)

n=len(a)-1
for i in range(1,n+1):
    if a[i]==-1:
        source=i
        continue
    graph[a[i]].append((i,(p[a[i]]-p[i])))

def func(node):
    nonlocal res
    
    if len(graph[node])==0:
        return -10**9
    
    curr=-10**9
    for child in graph[node]:
        x=max(child[1],(func(child[0])+child[1]))
        curr=max(curr,x)
        res=max(curr,res)
    
    return curr    

res=-10**9
curr=func(source)
print(res)        
        
        
        


from collections import defaultdict
from sys import stdin
input = stdin.readline

graph=defaultdict(list)

arr=[int(x) for x in input().split()]
if arr[0]==1:
    print(0)
    return

p=[None]
for i in range(1,arr[0]+1):
    p.append(arr[i])
a=[None]
for i in range(arr[0]+1,2*arr[0]+1):
    a.append(arr[i])

n=len(a)-1
# print(a)
# print(p)
for i in range(1,n+1):
    if a[i]==-1:
        source=i
        continue
    graph[a[i]].append((i,(p[a[i]]-p[i])))

# print(graph)

def func(node):
    nonlocal res
    
    if len(graph[node])==0:
        return -10**9
    
    curr=-10**9
    for child in graph[node]:
        x=max(child[1],(func(child[0])+child[1]))
        curr=max(curr,x)
        res=max(curr,res)
    
    return curr    

res=-10**9
curr=func(source)
print(res)        
        
        
        


from collections import defaultdict
from sys import stdin
input = stdin.readline

graph=defaultdict(list)

arr=[int(x) for x in input().split()]

p=[None]
for i in range(1,arr[0]+1):
    p.append(arr[i])
a=[None]
for i in range(arr[0]+1,2*arr[0]+1):
    a.append(arr[i])

n=len(a)-1
# print(a)
# print(p)
for i in range(1,n+1):
    if a[i]==-1:
        source=i
        continue
    graph[a[i]].append((i,(p[a[i]]-p[i])))

# print(graph)

def func(node):
    nonlocal res
    
    if len(graph[node])==0:
        return -10**9
    
    curr=-10**9
    for child in graph[node]:
        x=max(child[1],(func(child[0])+child[1]))
        curr=max(curr,x)
        res=max(curr,res)
    
    return curr    

res=-10**9
curr=func(source)
print(res)        
        
        
        


x = [int(w) for w in input().split()]
n = x[0]
x = x[1:]
a = {(i+1):x[i] for i in range(n)}
p = {(i+1):x[n+i] for i in range(n)}
mgr = {i:1 for i in p}
if -1 in mgr:
    mgr[-1] = 0

d = []
for i in range(1,n+1):
    t = [float('-inf')]
    par = p[i]
    while mgr.get(par,0):
        t.append(a[par])
        par = p[par]
    p[i] = -1
    d.append(max(t)-a[i])
    a[i] = max(t)
print(max(d))

# cook your dish here
# cook your dish here
from collections import defaultdict
list1 = list(map(int,input().split()))
N = list1[0]
list1.pop(0)
wealth=[]
parent= {}
children=defaultdict(list)
for i in range(N):
    wealth.append(list1[0])
    list1.pop(0)
root=0
for j in range(N):
    if list1[j] != -1:
        parent[j] = list1[j]-1
        children[list1[j]-1].append(j)
    else:
        root = j
leaves=[]
dowegoup={}
tobevisited=[root]
while len(tobevisited)>0:
    temp = tobevisited.pop()
    if len(children[temp])==0:
        leaves.append(temp)
    else:
        for i in range(len(children[temp])):
            tobevisited.append(children[temp][i])
            if wealth[children[temp][i]]>wealth[temp]:
                dowegoup[children[temp][i]] = False
            else:
                dowegoup[children[temp][i]] = True
#print("wealth: ", wealth, "parents: ", parent, "children; ", children, "leaves: ", leaves, "dowegoup: ", dowegoup)
visited={}
disparity={}
answer=-10**10
for j in range(len(leaves)):
    disparity[leaves[j]]=0
while len(leaves)>0:
    temp = leaves.pop(0)
    if parent[temp] not in disparity:
        disparity[parent[temp]] = wealth[parent[temp]] - wealth[temp]
        if disparity[temp]>0:
            disparity[parent[temp]] += disparity[temp]
    else:
        if disparity[temp]>0:
            gladiator = wealth[parent[temp]]-wealth[temp] +disparity[temp]
        else:
            gladiator = wealth[parent[temp]]-wealth[temp]
        disparity[parent[temp]] = max(gladiator,disparity[parent[temp]])
    if parent[temp]!=root:
        visited[parent[temp]] = True
        leaves.append(parent[temp])
    if disparity[parent[temp]]>answer:
        answer = disparity[parent[temp]]
#print("disparity: ", disparity)
print(answer)

import sys
from collections import defaultdict
sys.setrecursionlimit(1000000)
def dfs(i,maxVal,maxDiff):
    visited[i]=True
    if not graph[i]:
        return maxDiff
    else:
        stack=[]
        for j in graph[i]:
            if not visited[j]:
                diff=max(maxDiff,maxVal-a[j])
                val=max(maxVal,a[j])
                stack.append(dfs(j,val,diff))
        return max(stack)

s=list(map(int,input().split()))
n=s[0]
a=s[1:n+1]
p=s[n+1:]
graph=defaultdict(list)
for i in range(n):
    graph[p[i]-1].append(i)
boss=graph[-2][0]
visited=[False]*n
print(dfs(boss,a[boss],0))

x = [int(w) for w in input().split()]
n = x[0]
x = x[1:]
a = {(i+1):x[i] for i in range(n)}
p = {(i+1):x[n+i] for i in range(n)}
mgr = {i:1 for i in p}
if -1 in mgr:
    mgr[-1] = 0

d = []
for i in range(1,n+1):
    t = [float('-inf')]
    par = p[i]
    while mgr.get(par,0):
        t.append(a[par])
        par = p[par]
    p[i] = -1
    d.append(max(t)-a[i])
    a[i] = max(t)
print(max(d))

x = list(map(int, input().split()))

n   = x[0]
x = x[1:]
a = {(i):x[i] for i in range(n)}
p = {(i):x[n+i] for i in range(n)}
#vis = [0]*n
#print(a,p)
#vis[p.index(-1)] = 2

bhutiya = []

for i in range(n):
	if p[i] != -1:
		#vis[i] = 1
		#rem = []
		#rem.append(a[i])
		j = p[i]-1
		maxi = a[i]
		#print("j:",j)
		while p[j] != -1:
			if a[j] > maxi:	maxi = a[j]
			#rem.append(a[j])
			#vis[j] = 1
			j = p[j]-1
		
		if a[j] > maxi:	maxi = a[j]
		
		bhutiya.append(maxi-a[i])

print(max(bhutiya))




x = list(map(int, input().split()))

n   = x[0]
a   = x[1:n+1]
p   = x[n+1:]
#vis = [0]*n

parent = a[p.index(-1)]
#vis[p.index(-1)] = 2

bhutiya = []

for i in range(n):
	if p[i] != -1:
		#vis[i] = 1
		#rem = []
		#rem.append(a[i])
		j = p[i]-1
		maxi = a[i]

		while p[j] != -1:
			if a[j] > maxi:	maxi = a[j]
			#rem.append(a[j])
			#vis[j] = 1
			j = p[j]-1
		
		if a[j] > maxi:	maxi = a[j]
		
		bhutiya.append(maxi-a[i])

print(max(bhutiya))




x = list(map(int, input().split()))

n   = x[0]
a   = x[1:n+1]
p   = x[n+1:]
vis = [0]*n

parent = a[p.index(-1)]
vis[p.index(-1)] = 2

bhutiya = []

for i in range(n):
	if vis[i] != 2:
		#vis[i] = 1
		#rem = []
		#rem.append(a[i])
		j = p[i]-1
		maxi = a[i]

		while vis[j] != 2:
			if a[j] > maxi:	maxi = a[j]
			#rem.append(a[j])
			#vis[j] = 1
			j = p[j]-1
		
		if a[j] > maxi:	maxi = a[j]
		
		bhutiya.append(maxi-a[i])

print(max(bhutiya))




x = list(map(int, input().split()))

n   = x[0]
a   = x[1:n+1]
p   = x[n+1:]
vis = [0]*n

parent = a[p.index(-1)]
vis[p.index(-1)] = 2

bhutiya = []

for i in range(n):
	if vis[i] != 2:
		vis[i] = 1
		rem = []
		rem.append(a[i])
		j = p[i]-1

		while vis[j] != 2:
			rem.append(a[j])
			vis[j] = 1
			j = p[j]-1
		
		rem.append(a[j])
		bhutiya.append(max(rem)-a[i])

print(max(bhutiya))




x = [int(w) for w in input().split()]
n = x[0]
x = x[1:]
a = {(i+1):x[i] for i in range(n)}
p = {(i+1):x[n+i] for i in range(n)}
mgr = {i:1 for i in p}
if -1 in mgr:
    mgr[-1] = 0

d = []
for i in range(1,n+1):
    t = [float('-inf')]
    par = p[i]
    while mgr.get(par,0):
        t.append(a[par])
        par = p[par]
    p[i] = -1
    d.append(max(t)-a[i])
    a[i] = max(t)
print(max(d))

x = [int(w) for w in input().split()]
n = x[0]
x = x[1:]
a,p = x[:n],x[n:]
x = [[] for i in range(n)]
q = []
for i in range(n):
    if p[i] == -1:
        q.append([i,a[i]])
    else:
        x[p[i]-1].append(i)
ans = float('-inf')
while q:
    i,mx = q[-1]
    q.pop()
    ans = max(ans,mx-a[i])
    mx = max(mx,a[i])
    for j in x[i]:
        q.append([j,mx])
print(ans)

x = [int(w) for w in input().split()]
n = x[0]
x = x[1:]
a = {(i+1):x[i] for i in range(n)}
p = {(i+1):x[n+i] for i in range(n)}
mgr = {i:1 for i in p}
if -1 in mgr:
    mgr[-1] = 0

d = []
for i in range(1,n+1):
    t = [0]
    par = p[i]
    while mgr.get(par,0):
        t.append(a[par])
        par = p[par]
    d.append(max(t)-a[i])

print(max(d))

x = [int(w) for w in input().split()]
n = x[0]
x = x[1:]
a,p = x[:n],x[n:]

mgr = {i:1 for i in p}
if -1 in mgr:
    mgr[-1] = 0

d = []
for i in range(n):
    t = [0]
    par = p[i]
    while mgr.get(par,0):
        t.append(a[par-1])
        par = p[par-1]
    d.append(max(t)-a[i])

print(max(d))