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

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


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)


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)


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


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


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


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


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
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(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 = 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)}
bhutiya = []
for i in range(n):
	if p[i] != -1:
		j = p[i] - 1
		maxi = a[i]
		while p[j] != -1:
			if a[j] > maxi:
				maxi = a[j]
			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, 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)