You are given a tree rooted at node 1. The tree is given in form of an array P where P_{i} denotes the parent of node i, Also P_{1} = -1, as node 1 is the root node. Every node i has a value A_{i} associated with it. At first, you have to choose any node to start with, after that from a node you can go to any of its child nodes. You've to keep moving to a child node until you reach a leaf node. Every time you get to a new node, you write its value. Let us assume that the integer sequence in your path is B.
Let us define a function f over B, which is defined as follows:
f(B) = B_{1} - B_{2} + B_{3} - B_{4} + B_{5}.... + (-1)^{(k-1)}B_{k}.
You have to find the maximum possible value of f(B).
Example 1:
Input:
N = 3,
A = { 1, 2, 3}
P = {-1, 1, 1}
Output:
3
Explanation:
The resulting tree is:
        1(1)
      /     \
     2(2)   3(3)
If we choose our starting node as 3, then the
resulting sequence will be B = { 3 },
which will give the maximum possible value.
Example 2:
Input:
N = 3,
A = { 3, 1, 2}
P = {-1, 1, 2}
Output:
4
Explanation:
The resulting tree is:
  1(3)
  |
  2(1)
  |
  3(2)
If we choose our starting node as 1, then the
resulting sequence will be B = { 3 , 1 , 2 }.
The value which we'll get is, 3-1+2 = 4, which
is the maximum possible value.
Your Task:
The task is to complete the function bestNode() which takes an integer N and two integer arrays A, P as input parameters and returns the maximum possible value possible.
Expected Time Complexity: O(N)
Expected Space Complexity: O(N)
Constraints:
1 ≤  N ≤ 10^{5}
-10^{5} ≤  A_{i} ≤ 10^{5}
-1 ≤  P_{i} ≤ N

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Graph traversal

Starter code: from typing import List





class Solution:

    def bestNode(self, N : int, A : List[int], P : List[int]) -> int:

        # code here

        



Solutions:
from typing import List

class Solution:

	def bestNode(self, N: int, A: List[int], P: List[int]) -> int:

		def _solve(ix):
			if cs[ix]:
				for c in cs[ix]:
					_solve(c)
				dp[ix] = max((A[ix] - A[i] + cmax[i] for i in cs[ix]))
				cmax[ix] = max((dp[i] for i in cs[ix]))
			else:
				dp[ix] = A[ix]
				cmax[ix] = 0
		cs = [[] for _ in range(N)]
		(dp, cmax) = ([0] * N, [0] * N)
		for i in range(1, N):
			cs[P[i] - 1].append(i)
		_solve(0)
		return max(dp)


from typing import List

class Solution:

	def bestNode(self, N: int, A: List[int], P: List[int]) -> int:
		sign = [0 for i in range(N + 1)]
		for i in range(1, N):
			sign[P[i]] += 1
		ans = float('-inf')
		for i in range(1, N + 1):
			if sign[i] == 0:
				j = i
				temp = 0
				while j != -1:
					temp += A[j - 1]
					j = P[j - 1]
					ans = max(ans, temp)
					temp *= -1
		return ans


from typing import List

class TreeNode:

	def __init__(self, val):
		self.val = val
		self.child = []

class Solution:

	def buildTree(self, A, P):
		N = len(A)
		treeMap = {}
		root = None
		for i in range(N):
			val = A[i]
			parent = P[i]
			node = TreeNode(val)
			if parent == -1:
				root = node
			else:
				treeMap[parent - 1].child.append(node)
			treeMap[i] = node
		return root

	def dfs(self, root):
		if len(root.child) == 0:
			self.ans = max(self.ans, root.val)
			return (root.val, -root.val)
		include = exclude = float('-inf')
		for child in root.child:
			res = self.dfs(child)
			include = max(include, res[1])
			exclude = max(exclude, res[0])
		include += root.val
		exclude -= root.val
		self.ans = max(self.ans, include)
		return (include, exclude)

	def bestNode(self, N: int, A: List[int], P: List[int]) -> int:
		root = self.buildTree(A, P)
		self.ans = float('-inf')
		self.dfs(root)
		return self.ans


from typing import List
neg = -10 ** 11

class Solution:

	def bestNode(self, N: int, A: List[int], P: List[int]) -> int:
		leafs = set([i for i in range(1, N + 1)])
		ans = [neg for i in range(N + 1)]
		for i in P:
			if i in leafs:
				leafs.remove(i)
		for i in leafs:
			pointer = i
			sumo = 0
			while pointer != -1:
				sumo = A[pointer - 1] - sumo
				ans[pointer] = max(sumo, ans[pointer])
				pointer = P[pointer - 1]
		return max(ans)


from typing import List

class Solution:

	def bestNode(self, N: int, A: List[int], P: List[int]) -> int:
		S = {0}
		T = {0}
		T.remove(0)
		max = A[N - 1]
		n = len(A) - 1
		while n >= 0:
			S.add(P[n])
			n = n - 1
		n = len(A) - 1
		while n >= 0:
			if n + 1 in S:
				pass
			else:
				T.add(n)
			n = n - 1
		for m in T:
			u = A[m]
			U = [u]
			if u > max:
				max = u
			while P[m] > 0:
				m = P[m] - 1
				U.insert(0, A[m])
				iMax = 0
				sign = 1
				for k in U:
					iMax = iMax + k * sign
					sign = sign * -1
				if iMax > max:
					max = iMax
		return max


from typing import List
from collections import defaultdict

class Solution:

	def bestNode(self, N: int, A: List[int], P: List[int]) -> int:
		g = defaultdict(list)
		for (i, parent) in enumerate(P):
			g[parent].append(i + 1)
		ans = float('-inf')

		def dfs(n):
			nonlocal g, ans, A
			if not g[n]:
				ans = max(ans, A[n - 1])
				return (A[n - 1], A[n - 1])
			(maxv, minv) = (float('-inf'), float('inf'))
			for nxt in g[n]:
				(ma, mi) = dfs(nxt)
				maxv = max(maxv, A[n - 1] - mi)
				minv = min(minv, A[n - 1] - ma)
			ans = max(ans, maxv)
			return (maxv, minv)
		dfs(1)
		return ans


from typing import List
from collections import defaultdict

class Solution:

	def bestNode(self, N: int, A: List[int], P: List[int]) -> int:
		adj = defaultdict(list)
		for i in range(1, N):
			adj[P[i] - 1].append(i)

		def soln(i):
			(pos, neg) = (A[i], -A[i])
			mxp = mxn = float('-inf')
			for child in adj[i]:
				(p, n) = soln(child)
				mxp = max(mxp, pos + n)
				mxn = max(mxn, neg + p)
			if mxp == mxn == float('-inf'):
				mxp = pos
				mxn = neg
			soln.res = max(soln.res, mxp)
			return (mxp, mxn)
		soln.res = float('-inf')
		(p, n) = soln(0)
		return soln.res


from typing import List

class Solution:

	def __init__(self) -> None:
		self.max_score = None

	def build_tree(self, N, A, P):
		tree = [[i + 1, [], None] for i in range(N)]
		for i in range(1, N):
			tree[P[i] - 1][1] += [i + 1]
		for i in range(N):
			tree[i][2] = A[i]
		return tree

	def dfs(self, tree, v, step, score):
		score += tree[v][2] * pow(-1, step - 1)
		if tree[v][1] == []:
			if self.max_score is None or score > self.max_score:
				self.max_score = score
			return
		for w in tree[v][1]:
			self.dfs(tree, w, step + 1, score)

	def bestNode(self, N: int, A: List[int], P: List[int]) -> int:
		tree = [None] + self.build_tree(N, A, P)
		for i in range(1, N + 1):
			self.dfs(tree, i, 1, 0)
		return self.max_score


from typing import List

class Solution:

	def bestNode(self, n: int, a: List[int], p: List[int]) -> int:
		d = {}
		for i in range(n):
			d[i] = 1
		for i in range(1, n):
			if p[i] - 1 in d:
				del d[p[i] - 1]
		ans = -99999
		for i in d:
			s = 0
			x = i + 1
			while x != -1:
				s = -s
				s += a[x - 1]
				ans = max(s, ans)
				x = p[x - 1]
		return ans


from typing import List

class Solution:

	def bestNode(self, N: int, A: List[int], P: List[int]) -> int:
		if N == 1:
			return A[0]
		leaf = [0] * N
		for i in range(N):
			if P[i] == -1:
				continue
			else:
				leaf[P[i] - 1] = 1
		for i in range(N):
			if leaf[i] == 0:
				bmax = A[i]
				break
			else:
				continue
		for i in range(N):
			if leaf[i] == 0:
				b = A[i]
				if b > bmax:
					bmax = b
				while P[i] != -1:
					i = P[i] - 1
					b = A[i] - b
					if b > bmax:
						bmax = b
		return bmax


from typing import List

class Solution:

	def create_graph(self, parent):
		adj_list = {}
		for (idx, val) in enumerate(parent):
			if val - 1 in adj_list:
				adj_list[val - 1].append(idx)
			else:
				adj_list[val - 1] = [idx]
		return adj_list

	def best_node_val_helper(self, node, adj_list, arr):
		if node not in adj_list:
			self.ans = max(self.ans, arr[node])
			return [arr[node], -arr[node]]
		best_val = [float('-inf'), float('-inf')]
		if node in adj_list:
			for child in adj_list[node]:
				child_best_val = self.best_node_val_helper(child, adj_list, arr)
				best_val[0] = max(best_val[0], arr[node] + child_best_val[1])
				best_val[1] = max(best_val[1], -arr[node] + child_best_val[0])
		self.ans = max(self.ans, best_val[0])
		return best_val

	def bestNode(self, N: int, A: List[int], P: List[int]) -> int:
		self.ans = float('-inf')
		adj_list = self.create_graph(P)
		self.best_node_val_helper(0, adj_list, A)
		return self.ans


from typing import List
from collections import namedtuple
Costs = namedtuple('Costs', 'global_max max min')

class Solution:

	def dfs(self, adj: List[List[int]], A: List[int], u: int) -> Costs:
		w = A[u]
		if not adj[u]:
			return Costs(w, w, w)
		curr_global_max = curr_max = float('-inf')
		curr_min = float('inf')
		for v in adj[u]:
			(v_global_max, v_max, v_min) = self.dfs(adj, A, v)
			curr_global_max = max(curr_global_max, v_global_max)
			curr_max = max(curr_max, w - v_min)
			curr_min = min(curr_min, w - v_max)
		curr_global_max = max(curr_global_max, curr_max)
		return Costs(curr_global_max, curr_max, curr_min)

	def bestNode(self, N: int, A: List[int], P: List[int]) -> int:
		adj = [[] for _ in range(N)]
		for i in range(1, N):
			p = P[i] - 1
			adj[p].append(i)
		costs = self.dfs(adj, A, 0)
		return costs.global_max


from typing import List
import sys

class Solution:

	def __init__(self):
		self.ans = -sys.maxsize
		self.nums = []

	def helper2(self) -> int:
		if len(self.nums) == 1:
			return self.nums[0]
		res = -sys.maxsize
		sum1 = self.nums[-2]
		sum2 = self.nums[-1]
		res = max(res, sum2)
		res = max(res, sum1 - sum2)
		i = len(self.nums) - 3
		while i >= 0:
			sum2 += self.nums[i]
			i -= 1
			res = max(res, sum2 - sum1)
			if i < 0:
				break
			sum1 += self.nums[i]
			i -= 1
			res = max(res, sum1 - sum2)
		return res

	def helper1(self, src: int, adj: List[List[int]], a: List[int]) -> None:
		self.nums.append(a[src])
		is_leaf = True
		for x in adj[src]:
			is_leaf = False
			self.helper1(x, adj, a)
		if is_leaf:
			self.ans = max(self.ans, self.helper2())
		self.nums.pop()

	def bestNode(self, N: int, A: List[int], P: List[int]) -> int:
		adj = [[] for _ in range(N)]
		for i in range(N):
			if P[i] == -1:
				continue
			adj[P[i] - 1].append(i)
		self.helper1(0, adj, A)
		return self.ans


from typing import List

class Solution:

	def bestNode(self, N: int, A: List[int], P: List[int]) -> int:

		def solve(node):
			if t[node]:
				for c in t[node]:
					solve(c)
				dp[node] = max((A[node] - A[i] + cmax[i] for i in t[node]))
				cmax[node] = max((dp[i] for i in t[node]))
			else:
				dp[node] = A[node]
				cmax[node] = 0
		t = [[] for _ in range(N)]
		(dp, cmax) = ([0] * N, [0] * N)
		for i in range(1, N):
			t[P[i] - 1].append(i)
		solve(0)
		return max(dp)


from typing import List

class Solution:

	def bestNode(self, N: int, A: List[int], P: List[int]) -> int:

		def _solve(ix):
			if cs[ix]:
				for c in cs[ix]:
					_solve(c)
				dp[ix] = max((A[ix] - A[i] + cmax[i] for i in cs[ix]))
				cmax[ix] = max((dp[i] for i in cs[ix]))
			else:
				dp[ix] = A[ix]
				cmax[ix] = 0
		cs = [[] for _ in range(N)]
		(dp, cmax) = ([0] * N, [0] * N)
		for i in range(1, N):
			cs[P[i] - 1].append(i)
		_solve(0)
		return max(dp)

class IntArray:

	def __init__(self) -> None:
		pass

	def Input(self, n):
		arr = [int(i) for i in input().strip().split()]
		return arr

	def Print(self, arr):
		for i in arr:
			print(i, end=' ')
		print()


from typing import List
from collections import defaultdict

class Solution:

	def dfs(self, u, adj, visited, path, final):
		visited.add(u)
		flag = True
		for v in adj[u]:
			self.dfs(v, adj, visited, path + [v], final)
			flag = False
		if flag:
			final.append(path)

	def bestNode(self, N: int, A: List[int], P: List[int]) -> int:
		adj = defaultdict(list)
		for i in range(N):
			if P[i] != -1:
				adj[P[i] - 1].append(i)
		ans = float('-inf')
		visited = set()
		all_path = []
		for i in range(N):
			if i not in visited:
				path = []
				self.dfs(i, adj, visited, [i], path)
				for p in path:
					all_path.append(p)
		for path in all_path:
			for s in range(len(path)):
				f = False
				cost = 0
				for i in path[s:]:
					if f:
						cost -= A[i]
					else:
						cost += A[i]
					f = not f
				ans = max(ans, cost)
		return ans


from typing import List

class Solution:

	def bestNode(self, N: int, A: List[int], p: List[int]) -> int:
		g = {}
		for i in range(1, len(p)):
			if p[i] - 1 not in g:
				g[p[i] - 1] = []
			g[p[i] - 1].append(i)
		ans = [float('-inf')]

		def dfs(i):
			if i not in g:
				ans[0] = max(ans[0], A[i])
				return (A[i], A[i])
			a = float('-inf')
			b = float('inf')
			for child in g[i]:
				prone = dfs(child)
				a = max(a, A[i] - prone[0])
				b = min(b, A[i] - prone[1])
			ans[0] = max(ans[0], a)
			return (b, a)
		dfs(0)
		return ans[0]


from typing import List

class Solution:

	def bestNode(self, N: int, A: List[int], P: List[int]) -> int:
		s = set(P)
		leafNodes = [i for i in range(1, N + 1) if i not in s]
		ans = float('-inf')
		for node in leafNodes:
			fb = 0
			while node != -1:
				fb *= -1
				fb += A[node - 1]
				node = P[node - 1]
				ans = max(ans, fb)
		return ans


from typing import List

class Solution:

	def findLeafNodes(self, N: int, P: List[int]) -> List[int]:
		avlNodes = [False] * len(P)
		for i in range(0, N):
			if P[i] > -1:
				avlNodes[P[i] - 1] = True
		leafNodes = []
		for i in range(0, N):
			if not avlNodes[i]:
				leafNodes.append(i + 1)
		return leafNodes

	def bestNode(self, N: int, values: List[int], parent: List[int]) -> int:
		if N == 1:
			return values[0]
		leafNodes = self.findLeafNodes(N, parent)
		mx = values[leafNodes[0] - 1]
		for i in leafNodes:
			childIndex = i - 1
			curIndex = i - 1
			childValue = 0
			curValue = values[childIndex]
			while True:
				ans = curValue - childValue
				if mx < ans:
					mx = ans
				childIndex = curIndex
				curIndex = parent[curIndex] - 1
				childValue = ans
				curValue = values[curIndex]
				if curIndex <= -1:
					break
		return mx


from typing import List

class Solution:

	def bestNode(self, N: int, A: List[int], P: List[int]) -> int:
		from collections import defaultdict
		from math import inf
		adj = defaultdict(list)
		for i in range(1, N):
			adj[P[i] - 1].append(i)

		def itr(node):
			if node not in adj:
				return (A[node], A[node], A[node])
			(omx, mx, mn) = (-inf, -inf, inf)
			for i in adj[node]:
				(comx, cmn, cmx) = itr(i)
				mn = min(cmn, mn)
				mx = max(mx, cmx)
				omx = max(omx, comx)
			return (max(omx, A[node] - mn), A[node] - mx, A[node] - mn)
		res = itr(0)
		return res[0]
		return 0


from typing import List
import sys

class Solution:

	def bestNode(self, N: int, A: List[int], P: List[int]) -> int:
		result = [-sys.maxsize for _ in range(N)]
		max_arr = [-sys.maxsize for _ in range(N)]
		min_arr = [sys.maxsize for _ in range(N)]
		tree = [[] for _ in range(N)]
		for i in range(1, N):
			parent = P[i]
			tree[parent - 1].append(i)
		flag = 0
		for i in range(N):
			(min_arr[i], max_arr[i]) = (0, 0)

		def DFS(index):
			if len(tree[index]) > 0:
				for x in tree[index]:
					DFS(x)
				min_arr[index] = max((A[index] - A[i] + max_arr[i] for i in tree[index]))
				max_arr[index] = max((min_arr[i] for i in tree[index]))
			else:
				min_arr[index] = A[index]
				max_arr[index] = 0
		DFS(0)
		return max(min_arr)


from typing import List

class Solution:

	def bestNode(self, N: int, A: List[int], P: List[int]) -> int:
		nonLeafNode = set()
		for node in P:
			nonLeafNode.add(node)
		leafNode = []
		for i in range(1, N + 1):
			if i not in nonLeafNode:
				leafNode.append(i)
		ans = float('-inf')
		for node in leafNode:
			s = 0
			while node != -1:
				s = -s
				s += A[node - 1]
				ans = max(s, ans)
				node = P[node - 1]
		return ans


from typing import List

class Solution:

	def bestNode(self, N: int, A: List[int], P: List[int]) -> int:
		maxi = [-1000000000.0]
		dict = {-1: [A[0]]}
		for i in range(1, len(A)):
			if P[i] - 1 not in dict:
				dict[P[i] - 1] = [i]
			else:
				dict[P[i] - 1] += [i]

		def dfs(flag, sum, nod):
			sum1 = A[nod]
			if flag == 0:
				sum1 = -A[nod]
			sum11 = -1000000000.0
			if nod in dict:
				for i in dict[nod]:
					sum11 = max(sum11, dfs(abs(flag - 1), 0, i))
			if nod not in dict:
				sum11 = 0
			if flag == 1:
				maxi[0] = max(maxi[0], sum11 + sum1)
			return sum11 + sum1
		dfs(1, 0, 0)
		dfs(0, 0, 0)
		return maxi[0]


from typing import List
import math

class Solution:

	def bestNode(self, N: int, A: List[int], P: List[int]) -> int:
		non_leaf = set(P)
		leaf = []
		ans = -math.inf
		for i in range(1, len(P) + 1):
			if i not in non_leaf:
				leaf.append(i)
		for l in leaf:
			cur = l
			s = 0
			while cur != -1:
				s = -s
				s += A[cur - 1]
				ans = max(ans, s)
				cur = P[cur - 1]
		return ans


from math import inf
from typing import List

class Solution:

	def dfs(self, tree, A, u):
		if not tree[u]:
			return (A[u], A[u], A[u])
		(overall_max, max_path, min_path) = (-inf, -inf, inf)
		for v in tree[u]:
			(coverall_max, cmin_path, cmax_path) = self.dfs(tree, A, v)
			min_path = min(min_path, cmin_path)
			max_path = max(max_path, cmax_path)
			overall_max = max(overall_max, coverall_max)
		return (max(overall_max, A[u] - min_path), A[u] - max_path, A[u] - min_path)

	def bestNode(self, N: int, A: List[int], P: List[int]) -> int:
		tree = [[] for _ in range(N)]
		for (ind, p) in enumerate(P[1:]):
			tree[p - 1].append(ind + 1)
		return self.dfs(tree, A, 0)[0]