In an online game, N blocks are arranged in a hierarchical manner. All the blocks are connected together by a total of N-1 connections. Each block is given an ID from 1 to N. A block may be further connected to other blocks. Each block is also assigned a specific point value.
A player starts from Block 1. She must move forward from each block to a directly connected block until she reaches the final block, which has no further connection. When the player lands on a block, she collects the point value of that block. The players score is calculated as the product of point values that the player collects.
Find the maximum score a player can achieve.
Note: The answer can always be represented with 64 bits.
Example 1:
Input:
     4
    / \
   2   8
  / \ / \
 2  1 3  4
Output: 128
Explanation: Path in the given tree 
goes like 4, 8, 4 which gives the max
score of 4x8x4 = 128.
Example 2:
Input:
     10
   /    \
  7      5
          \
           1
Output: 70
Explanation: The path 10, 7 gives a 
score of 70 which is the maximum possible.
Your Task:
You don't need to take input or print anything. Your task is to complete the function findMaxScore() that takes root as input and returns max score possible.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Tree).
Constraints:
1 ≤ Number of nodes ≤ 10^{3}
1 ≤ Data on node ≤ 10 
It is guaranteed that the answer will always fit in the 64-bit Integer

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Range queries

Starter code: #User function Template for python3



#structure of class Node

'''

class Node:

    def __init__(self, val):

        self.right = None

        self.data = val

        self.left = None

'''



class Solution:

    def findMaxScore(self, root):

        #code here

Solutions:
class Solution:

	def findMaxScore(self, root):

		def answer(root):
			if root == None:
				return 1
			l = answer(root.left)
			r = answer(root.right)
			return max(l * root.data, r * root.data)
		return answer(root)


class Solution:

	def solve(self, p, curr):
		if not p:
			return
		curr *= p.data
		if not p.left and (not p.right):
			self.ans = max(self.ans, curr)
		self.solve(p.left, curr)
		self.solve(p.right, curr)

	def findMaxScore(self, root):
		self.ans = 0
		self.solve(root, 1)
		return self.ans


from collections import deque

class Solution:

	def findMaxScore(self, root):
		q = deque()
		q.append([root, root.data])
		max1 = root.data
		while q:
			(top, val) = q.popleft()
			if top.left:
				q.append([top.left, top.left.data * val])
				max1 = max(max1, top.left.data * val)
			if top.right:
				q.append([top.right, top.right.data * val])
				max1 = max(max1, top.right.data * val)
		return max1


class Solution:

	def findMaxScore(self, root):
		if not root:
			return 1
		return root.data * max(self.findMaxScore(root.left), self.findMaxScore(root.right))


class Solution:

	def dfs(self, root, prod, res):
		if root is None:
			return res
		prod = prod * root.data
		res = max(prod, res)
		left_max = self.dfs(root.left, prod, res)
		right_max = self.dfs(root.right, prod, res)
		return max(res, max(left_max, right_max))

	def findMaxScore(self, root):
		return self.dfs(root, 1, 1)


class Solution:

	def findMaxScore(self, root):

		def dfs(root):
			if root == None:
				return 1
			return max(root.data * dfs(root.left), root.data * dfs(root.right))
		return dfs(root)


class Solution:

	def findMaxScore(self, root):

		def f(root):
			if not root:
				return 1
			l = f(root.left)
			r = f(root.right)
			return root.data * max(l, r)
		return f(root)


class Solution:

	def findMaxScore(self, root):

		def f(root, temp, ans):
			if not root:
				ans[0] = max(ans[0], temp)
			else:
				temp *= root.data
				f(root.left, temp, ans)
				f(root.right, temp, ans)
		ans = [1]
		f(root, 1, ans)
		return ans[0]


class Solution:

	def findMaxScore(self, root):

		def helper(root):
			if root == None:
				return 1
			return root.data * max(helper(root.left), helper(root.right))
		ans = helper(root)
		return ans


class Solution:

	def findMaxScore(self, root):

		def find(root):
			if root is None:
				return 1
			return max(root.data * find(root.left), root.data * find(root.right))
		return find(root)


class Solution:

	def __init__(self):
		self.m = 0

	def findMaxScore(self, root):
		self.solve(root, 1)
		return self.m

	def solve(self, root, p):
		if root == None:
			return
		if root.left == None and root.right == None:
			self.m = max(self.m, p * root.data)
			return
		self.solve(root.left, p * root.data)
		self.solve(root.right, p * root.data)


class Solution:

	def __init__(self):
		self.ans = 0

	def findMaxScore(self, root):

		def pathProd(root, prod):
			prod *= root.data
			if root.left == None and root.right == None:
				self.ans = max(self.ans, prod)
				return
			if root.left:
				pathProd(root.left, prod)
			if root.right:
				pathProd(root.right, prod)
		pathProd(root, 1)
		return self.ans


class Solution:

	def findMaxScore(self, root):

		def mx(r):
			if not r:
				return 1
			if not r.left and (not r.right):
				return r.data
			return r.data * max(mx(r.left), mx(r.right))
		return mx(root)


class Solution:

	def findMaxScore(self, root):
		self.prod = 1

		def dfs(root, s):
			if root:
				dfs(root.left, s * root.data)
				self.prod = max(self.prod, s * root.data)
				dfs(root.right, s * root.data)
			return self.prod
		return dfs(root, 1)


import numpy

class Solution:

	def findMaxScore(self, root):

		def order(root):
			if root == None:
				return
			else:
				pro[0] = pro[0] * root.data
				li.append(root.data)
				if root.left == None and root.right == None:
					maxx[0] = max(maxx[0], pro[0])
				order(root.left)
				order(root.right)
				ele = li[-1]
				li.pop()
				pro[0] = pro[0] // root.data
		li = []
		pro = [1]
		maxx = [-99999]
		order(root)
		return maxx[0]


class Solution:

	def __init__(self):
		self.prod = []

	def pre(self, root, p):
		if root.left == None and root.right == None:
			self.prod.append(p * root.data)
			return
		if root.left != None:
			self.pre(root.left, p * root.data)
		if root.right != None:
			self.pre(root.right, p * root.data)

	def findMaxScore(self, root):
		self.pre(root, 1)
		return max(self.prod)


class Solution:

	def findMaxScore(self, root):

		def traversal(root):
			nonlocal product, maximum
			if root == None:
				return None
			product = product * root.data
			if root.left == None and root.right == None:
				maximum = max(maximum, product)
			if traversal(root.left) or traversal(root.right):
				return True
			product = product / root.data
			return False
		product = 1
		maximum = -999999
		traversal(root)
		return int(maximum)


class Solution:

	def findMaxScore(self, root):
		maxScore = [0]
		self.findMaxScoreAux(root, maxScore, 1)
		return maxScore[0]

	def findMaxScoreAux(self, root, maxScore, scoreSoFar):
		scoreSoFar *= root.data
		if root.left is None and root.right is None:
			if scoreSoFar > maxScore[0]:
				maxScore[0] = scoreSoFar
		if root.left is not None:
			self.findMaxScoreAux(root.left, maxScore, scoreSoFar)
		if root.right is not None:
			self.findMaxScoreAux(root.right, maxScore, scoreSoFar)


class Solution:

	def findMaxScore(self, root):
		c = 0
		q = [[root, root.data]]
		m = -1
		while c != len(q):
			t = q[c][0]
			g = q[c][1]
			f = 0
			if t.left:
				f = 1
				q.append([t.left, g * t.left.data])
			if t.right:
				f = 1
				q.append([t.right, g * t.right.data])
			c += 1
			if f == 0:
				if g > m:
					m = g
		return m


class Solution:

	def findMaxScore(self, root):
		ans = []
		temp = 1

		def recur(root, temp):
			temp = temp * root.data
			if root.left == None and root.right == None:
				ans.append(temp)
			if root.left:
				recur(root.left, temp)
			if root.right:
				recur(root.right, temp)
		recur(root, temp)
		return max(ans)


class Solution:

	def findMaxScore(self, root):
		if root.left == None and root.right == None:
			return root.data
		elif root.right == None:
			return root.data * self.findMaxScore(root.left)
		elif root.left == None:
			return root.data * self.findMaxScore(root.right)
		else:
			return max(root.data * self.findMaxScore(root.left), root.data * self.findMaxScore(root.right))


class Solution:

	def findMaxScore(self, root):

		def recur(root, sm):
			if not root:
				return
			if not root.left and (not root.right):
				self.mx = max(self.mx, sm * root.data)
				return
			recur(root.left, sm * root.data)
			recur(root.right, sm * root.data)
		self.mx = float('-inf')
		recur(root, 1)
		return self.mx


class Solution:

	def findMaxScore(self, root):
		maxi = [-999999999999999]

		def solve(root, ans):
			if root.left is None and root.right is None:
				ans = ans * root.data
				maxi[0] = max(maxi[0], ans)
				return
			if root.left:
				solve(root.left, ans * root.data)
			if root.right:
				solve(root.right, ans * root.data)
		solve(root, 1)
		return maxi[0]


class Solution:

	def findMaxScore(self, root):

		def f(root, maxi, ans):
			if root.left == None and root.right == None:
				maxi[0] = max(maxi[0], ans)
				return
			if root.left:
				f(root.left, maxi, ans * root.left.data)
			if root.right:
				f(root.right, maxi, ans * root.right.data)
		maxi = [-100000000]
		ans = root.data
		f(root, maxi, ans)
		return maxi[0]


class Solution:

	def findMaxScore(self, root):
		s = 1
		l = []
		self.dfs(root, s, l)
		return max(l)

	def dfs(self, root, s, l):
		if root == None:
			return
		s = s * root.data
		l.append(s)
		self.dfs(root.left, s, l)
		self.dfs(root.right, s, l)


class Solution:

	def __init__(self):
		self.result = 1

	def findMaxScore(self, root):

		def fxn(node, back_value):
			if node:
				if node.left is None and node.right is None:
					self.result = max(self.result, node.data * back_value)
				fxn(node.left, node.data * back_value)
				fxn(node.right, node.data * back_value)
		fxn(root, 1)
		return self.result


def preorder(root, mul, mx):
	if root == None:
		return
	mul *= root.data
	if root.left == None and root.right == None:
		mx[0] = max(mx[0], mul)
	preorder(root.left, mul, mx)
	preorder(root.right, mul, mx)

class Solution:

	def findMaxScore(self, root):
		res = [0]
		preorder(root, 1, res)
		return res[0]
from collections import deque

class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		ob = Solution()
		print(ob.findMaxScore(root))


def recur(root):
	if root.left or root.right:
		n1 = -99999
		n2 = -99999
		if root.left:
			n1 = recur(root.left) * root.data
		if root.right:
			n2 = recur(root.right) * root.data
		return max(n1, n2)
	else:
		return root.data

class Solution:

	def findMaxScore(self, root):
		return recur(root)


class Solution:

	def findMaxScore(self, root):
		q = []
		q.append(root)
		while q != []:
			cur = q.pop(0)
			if cur.left != None:
				q.append(cur.left)
				cur.left.data = cur.left.data * cur.data
			if cur.right != None:
				q.append(cur.right)
				cur.right.data = cur.right.data * cur.data
		ma = 0
		z = []
		z.append(root)
		while z != []:
			cur = z.pop(0)
			ma = max(ma, cur.data)
			if cur.left != None:
				z.append(cur.left)
			if cur.right != None:
				z.append(cur.right)
		return ma


class Solution:

	def helper(self, root, l, m):
		if root == None:
			return None
		l = l * root.data
		if root.left == None and root.right == None:
			m.append(l)
			l = 1
		self.helper(root.left, l, m)
		self.helper(root.right, l, m)

	def findMaxScore(self, root):
		l = 1
		m = []
		max = 0
		self.helper(root, l, m)
		for i in m:
			if i > max:
				max = i
		return max


class Solution:
	l = 1
	m = []
	max = 0

	def findMaxScore(self, root):
		if root == None:
			return 1
		left = root.data * self.findMaxScore(root.left)
		right = root.data * self.findMaxScore(root.right)
		return max(left, right)


class Solution:

	def findMaxScore(self, root):

		def findMaxProduct(root, product):
			product[0] *= root.data
			if root.left:
				findMaxProduct(root.left, product)
			if root.right:
				findMaxProduct(root.right, product)
			if not root.left and (not root.right):
				self.max_prod = max(self.max_prod, product[0])
			product[0] = product[0] // root.data
		self.max_prod = 0
		findMaxProduct(root, [1])
		return self.max_prod


class Solution:

	def findMaxScore(self, root):
		max_score = self.traverse(root, 0)
		return max_score

	def traverse(self, node, score):
		if node is None:
			return 1
		left = self.traverse(node.left, score)
		right = self.traverse(node.right, score)
		return node.data * max(left, right)


class Solution:

	def findMaxScore(self, root):
		score_right = score_left = 1
		if root.right is not None:
			score_right = self.findMaxScore(root.right)
		if root.left is not None:
			score_left = self.findMaxScore(root.left)
		return root.data * max(score_right, score_left)


class Solution:

	def findMaxScore(self, root):
		if root is None:
			return 1
		else:
			if root.left is not None:
				lScore = self.findMaxScore(root.left)
			else:
				lScore = 1
			if root.right is not None:
				rScore = self.findMaxScore(root.right)
			else:
				rScore = 1
			return max(root.data * lScore, root.data * rScore)


class Solution:

	def findMaxScore(self, root):
		ans = [1, 1]
		self.preorder(root, ans)
		return ans[0]

	def preorder(self, root, ans):
		if root == None:
			return
		if root.left == root.right == None:
			ans[0] = max(ans[0], ans[1] * root.data)
			return
		ans[1] = ans[1] * root.data
		self.preorder(root.left, ans)
		self.preorder(root.right, ans)
		ans[1] = ans[1] // root.data


class Solution:

	def findMaxScore(self, root):

		def getans(root):
			if root is None:
				return 0
			leftbranch = getans(root.left)
			rightbranch = getans(root.right)
			branchmax = max(rightbranch, leftbranch)
			value = root.data
			summax = max(value * branchmax, value)
			return summax
		ans = getans(root)
		return ans


class Solution:

	def findMaxScore(self, root):

		def solve(root, maxi, psf):
			if not root:
				return 1
			psf *= root.data
			if psf > maxi[0]:
				maxi[0] = psf
			solve(root.left, maxi, psf)
			solve(root.right, maxi, psf)
		maxi = [float('-inf')]
		solve(root, maxi, 1)
		return maxi[0]


class Solution:

	def dfs(self, n, p):
		if n == None:
			self.max_p = max(p, self.max_p)
		else:
			self.dfs(n.left, p * n.data)
			self.dfs(n.right, p * n.data)

	def findMaxScore(self, root):
		self.max_p = 1
		self.dfs(root, 1)
		return self.max_p


import math

class Solution:

	def findMaxScore(self, root):
		if not root:
			return 1
		res_l = root.data
		res_r = res_l
		if root.left:
			res_l *= self.findMaxScore(root.left)
		if root.right:
			res_r *= self.findMaxScore(root.right)
		return max(res_l, res_r)


class Solution:

	def findMaxScore(self, root):
		t = 1

		def util(root):
			t = 1
			if root == None:
				return
			if root.left == None and root.right == None:
				return root.data
			if root.left == None:
				return root.data * util(root.right)
			if root.right == None:
				return root.data * util(root.left)
			t *= root.data * max(util(root.left), util(root.right))
			return t
		return util(root)


class Solution:

	def findMaxScore(self, root):
		return self.step(root, 1)

	def step(self, node, val):
		if not node:
			return val
		sol1 = self.step(node.left, val * node.data)
		sol2 = self.step(node.right, val * node.data)
		return max(sol1, sol2)


class Solution:

	def findMaxScore(self, root):
		self.ans = 1

		def helper(root):
			if root == None:
				return 1
			l = helper(root.left)
			r = helper(root.right)
			temp = root.data * max(l, r)
			self.ans = max(self.ans, temp)
			return temp
		helper(root)
		return self.ans


class Solution:

	def MaxScore(self, root, score=0, high=0):
		if score == 0:
			score = root.data
		else:
			score *= root.data
		if root.left or root.right:
			if root.left:
				z = self.MaxScore(root.left, score, high)
				if z > high:
					high = z
			if root.right:
				z = self.MaxScore(root.right, score, high)
				if z > high:
					high = z
			score /= root.data
		else:
			if score > high:
				high = score
			score /= root.data
		return high

	def findMaxScore(self, root):
		a = self.MaxScore(root)
		return a


class Solution:

	def findMaxScore(self, root):
		lis = []
		val = 1

		def rec(root, val):
			val = val * root.data
			if root.left == None and root.right == None:
				lis.append(val)
			if root.right:
				rec(root.right, val)
			if root.left:
				rec(root.left, val)
		rec(root, val)
		return max(lis)


class Solution:

	def findMaxScore(self, root):
		k = []
		r = []
		value = []
		value1 = []
		max1 = -10000
		k.append(root)
		if root.data > max1:
			max1 = root.data
		value.append(max1)
		while k != []:
			l = k.pop(0)
			m = value.pop(0)
			if l.left:
				if l.left.data * m > max1:
					max1 = l.left.data * m
				r.append(l.left)
				value1.append(l.left.data * m)
			if l.right:
				if l.right.data * m > max1:
					max1 = l.right.data * m
				r.append(l.right)
				value1.append(l.right.data * m)
			if k == []:
				k = r
				value = value1
				r = []
				value1 = []
		return max1


class Solution:

	def findMaxScore(self, root):

		def tra(root):
			if root:
				return max(tra(root.left), tra(root.right)) * root.data
			else:
				return 1
		return tra(root)


class Solution:
	ans = -float('inf')

	def tra(self, root):
		if root:
			return max(self.tra(root.left), self.tra(root.right)) * root.data
		else:
			return 1

	def findMaxScore(self, root):
		return self.tra(root)


class Solution:

	def findMaxScore(self, root):
		if root == None:
			return 0
		if root.left == None and root.right == None:
			return root.data
		return root.data * max(self.findMaxScore(root.left), self.findMaxScore(root.right))


class Solution:

	def findMaxScore(self, root):
		self.x = 1
		self.maxer = -100000000000

		def paths(root):
			if root is None:
				return
			self.x = self.x * root.data
			if root.left is None and root.right is None:
				if self.x > self.maxer:
					self.maxer = self.x
			paths(root.left)
			paths(root.right)
			self.x = int(self.x // root.data)
		paths(root)
		return self.maxer


class Solution:

	def findMaxScore(self, root):
		if root == None:
			return 1
		a = root.data * self.findMaxScore(root.left)
		b = root.data * self.findMaxScore(root.right)
		return max(a, b)


class Solution:

	def findMaxScore(self, root):
		return self.max_score(root, 1)

	def max_score(self, root, current_score):
		if root is None:
			return current_score
		update_score = current_score * root.data
		return max(self.max_score(root.left, update_score), self.max_score(root.right, update_score))


import collections

class Solution:

	def findMaxScore(self, root):
		max_score = float('-inf')
		bfs_que = collections.deque()
		bfs_que.append([root, root.data])
		while bfs_que:
			(node, score) = bfs_que.popleft()
			max_score = max(max_score, score)
			if node.left:
				bfs_que.append([node.left, score * node.left.data])
			if node.right:
				bfs_que.append([node.right, score * node.right.data])
		return max_score


class Solution:

	def findMaxScore(self, root):
		if root is None:
			return 1
		lh = root.data * self.findMaxScore(root.left)
		rh = root.data * self.findMaxScore(root.right)
		if lh > rh:
			return lh
		else:
			return rh