Given a rooted tree of $N$ nodes, where each node is uniquely numbered in between [1..N]. The node 1 is the root of the tree. Each node has an integer value which is initially 0.

You need to perform the following two kinds of queries on the tree:

add t value: Add value to all nodes in subtree rooted at t
max a b: Report maximum value on the path from a to b

Input Format

First line contains N, number of nodes in the tree. Next N-1 lines contain two space separated integers x and y which denote that there is an edge between node x and node y. 

Next line contains Q, the number of queries to process. 

Next Q lines follow with either add or max query per line.

Constraints 

$1\leq N\leq10^5$ 

$1\leq Q\leq10^5$ 

$1\le t,a,b,x,y\le N$ 

$x\neq y$ 

$-10^4\leq value\leq10^4$

Output Format

For each max query output the answer in a separate line.

Sample Input
5
1 2
2 3
2 4
5 1
6
add 4 30
add 5 20
max 4 5
add 2 -20
max 4 5
max 3 4

Sample Output
30
20
10

Explanation

In the test case we have the following tree:

Initially all node values are zero. 

Queries are performed in the following way:

add 4 30 // add 30 to node 4 

add 5 20 // add 20 to node 5 

max 4 5 // maximum of nodes 4,2,1,5 is 30 

add 2 -20 // subtract 20 from nodes 2,3,4 

max 4 5 // maximum of nodes 4,2,1,5 is 20 

max 3 4 // maximum of nodes 3,2,4 is 10

Difficulty: HARD
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
n = int(input())
values = [0 for x in range(n)]
parents = [None for x in range(n)]
levels = [0 for x in range(n)]
connections = [[] for x in range(n)]
for i in range(n - 1):
	(a, b) = [int(x) - 1 for x in input().split()]
	connections[a].append(b)
	connections[b].append(a)
from collections import deque
queue = deque([(0, 0)])
visited = set()
while queue:
	(node, level) = queue.popleft()
	visited.add(node)
	levels[node] = level
	for i in connections[node]:
		if i not in visited:
			parents[i] = node
			queue.append((i, level + 1))

def findcommonancestor(a, b):
	if levels[a] > levels[b]:
		for _ in range(levels[a] - levels[b]):
			a = parents[a]
	elif levels[b] > levels[a]:
		for _ in range(levels[b] - levels[a]):
			b = parents[b]
	while a != b:
		(a, b) = (parents[a], parents[b])
	return a

def findprevvals(a):
	val = 0
	a = parents[a]
	while a is not None:
		val += values[a]
		a = parents[a]
	return val

def findprevmax(a, stop):
	max_a = values[a]
	while a != stop:
		a = parents[a]
		if max_a > 0:
			max_a += values[a]
		else:
			max_a = values[a]
	return max_a

def findmax(a, b):
	common_ancestor = findcommonancestor(a, b)
	ancestor_val = findprevvals(common_ancestor)
	max_a = findprevmax(a, common_ancestor)
	max_b = findprevmax(b, common_ancestor)
	return max(max_a, max_b) + ancestor_val

def addtosubtree(root, n):
	values[root] += n
q = int(input())
for i in range(q):
	inp = input().split()
	if inp[0] == 'add':
		addtosubtree(int(inp[1]) - 1, int(inp[2]))
	else:
		print(findmax(int(inp[1]) - 1, int(inp[2]) - 1))


from collections import deque
n = int(input())
values = [0 for _ in range(n)]
parents = [None for _ in range(n)]
levels = [0 for _ in range(n)]
connections = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = [int(x) - 1 for x in input().split()]
	connections[a].append(b)
	connections[b].append(a)
queue = deque([(0, 0)])
visited = set()
while queue:
	(node, level) = queue.popleft()
	visited.add(node)
	levels[node] = level
	for i in connections[node]:
		if i not in visited:
			parents[i] = node
			queue.append((i, level + 1))

def find_common_ancestor(a, b):
	if levels[a] > levels[b]:
		for _ in range(levels[a] - levels[b]):
			a = parents[a]
	elif levels[b] > levels[a]:
		for _ in range(levels[b] - levels[a]):
			b = parents[b]
	while a != b:
		(a, b) = (parents[a], parents[b])
	return a

def find_prev_vals(a):
	val = 0
	a = parents[a]
	while a is not None:
		val += values[a]
		a = parents[a]
	return val

def find_prev_max(a, stop):
	max_a = values[a]
	while a != stop:
		a = parents[a]
		if max_a > 0:
			max_a += values[a]
		else:
			max_a = values[a]
	return max_a

def findmax(a, b):
	common_ancestor = find_common_ancestor(a, b)
	ancestor_val = find_prev_vals(common_ancestor)
	max_a = find_prev_max(a, common_ancestor)
	max_b = find_prev_max(b, common_ancestor)
	return max(max_a, max_b) + ancestor_val

def addtosubtree(root, n):
	values[root] += n
q = int(input())
for i in range(q):
	inp = input().split()
	if inp[0] == 'add':
		addtosubtree(int(inp[1]) - 1, int(inp[2]))
	else:
		print(findmax(int(inp[1]) - 1, int(inp[2]) - 1))


n = int(input())
values = [0 for x in range(n)]
parents = [None for x in range(n)]
levels = [0 for x in range(n)]
connections = [[] for x in range(n)]
for i in range(n - 1):
	(a, b) = [int(x) - 1 for x in input().split()]
	connections[a].append(b)
	connections[b].append(a)
from collections import deque
queue = deque([(0, 0)])
visited = set()
while queue:
	(node, level) = queue.popleft()
	visited.add(node)
	levels[node] = level
	for i in connections[node]:
		if i not in visited:
			parents[i] = node
			queue.append((i, level + 1))

def findcommonancestor(a, b):
	if levels[a] > levels[b]:
		for _ in range(levels[a] - levels[b]):
			a = parents[a]
	elif levels[b] > levels[a]:
		for _ in range(levels[b] - levels[a]):
			b = parents[b]
	while a != b:
		(a, b) = (parents[a], parents[b])
	return a

def findprevvals(a):
	val = 0
	a = parents[a]
	while a is not None:
		val += values[a]
		a = parents[a]
	return val

def findprevmax(a, stop):
	max_a = values[a]
	while a != stop:
		a = parents[a]
		if max_a > 0:
			max_a += values[a]
		else:
			max_a = values[a]
	return max_a

def findmax(a, b):
	common_ancestor = findcommonancestor(a, b)
	ancestor_val = findprevvals(common_ancestor)
	max_a = findprevmax(a, common_ancestor)
	max_b = findprevmax(b, common_ancestor)
	return max(max_a, max_b) + ancestor_val

def addtosubtree(root, n):
	values[root] += n
q = int(input())
for i in range(q):
	inp = input().split()
	if inp[0] == 'add':
		addtosubtree(int(inp[1]) - 1, int(inp[2]))
	else:
		print(findmax(int(inp[1]) - 1, int(inp[2]) - 1))


n = int(input())
values = [0 for x in range(n)]
parents = [None for x in range(n)]
levels = [0 for x in range(n)]
connections = [[] for x in range(n)]
for i in range(n - 1):
	(a, b) = [int(x) - 1 for x in input().split()]
	connections[a].append(b)
	connections[b].append(a)
from collections import deque
queue = deque([(0, 0)])
visited = set()
while queue:
	(node, level) = queue.popleft()
	visited.add(node)
	levels[node] = level
	for i in connections[node]:
		if i not in visited:
			parents[i] = node
			queue.append((i, level + 1))

def findcommonancestor(a, b):
	if levels[a] > levels[b]:
		for _ in range(levels[a] - levels[b]):
			a = parents[a]
	elif levels[b] > levels[a]:
		for _ in range(levels[b] - levels[a]):
			b = parents[b]
	while a != b:
		(a, b) = (parents[a], parents[b])
	return a

def findprevvals(a):
	val = 0
	a = parents[a]
	while a is not None:
		val += values[a]
		a = parents[a]
	return val

def findprevmax(a, stop):
	max_a = values[a]
	while a != stop:
		a = parents[a]
		if max_a > 0:
			max_a += values[a]
		else:
			max_a = values[a]
	return max_a

def findmax(a, b):
	common_ancestor = findcommonancestor(a, b)
	ancestor_val = findprevvals(common_ancestor)
	max_a = findprevmax(a, common_ancestor)
	max_b = findprevmax(b, common_ancestor)
	return max(max_a, max_b) + ancestor_val

def addtosubtree(root, n):
	values[root] += n
q = int(input())
for i in range(q):
	inp = input().split()
	if inp[0] == 'add':
		addtosubtree(int(inp[1]) - 1, int(inp[2]))
	else:
		print(findmax(int(inp[1]) - 1, int(inp[2]) - 1))


n = int(input())
values = [0 for x in range(n)]
parents = [None for x in range(n)]
levels = [0 for x in range(n)]
connections = [[] for x in range(n)]
for i in range(n - 1):
	(a, b) = [int(x) - 1 for x in input().split()]
	connections[a].append(b)
	connections[b].append(a)
from collections import deque
queue = deque([(0, 0)])
visited = set()
while queue:
	(node, level) = queue.popleft()
	visited.add(node)
	levels[node] = level
	for i in connections[node]:
		if i not in visited:
			parents[i] = node
			queue.append((i, level + 1))

def findcommonancestor(a, b):
	if levels[a] > levels[b]:
		for _ in range(levels[a] - levels[b]):
			a = parents[a]
	elif levels[b] > levels[a]:
		for _ in range(levels[b] - levels[a]):
			b = parents[b]
	while a != b:
		(a, b) = (parents[a], parents[b])
	return a

def findprevvals(a):
	val = 0
	a = parents[a]
	while a is not None:
		val += values[a]
		a = parents[a]
	return val

def findprevmax(a, stop):
	max_a = values[a]
	while a != stop:
		a = parents[a]
		if max_a > 0:
			max_a += values[a]
		else:
			max_a = values[a]
	return max_a

def findmax(a, b):
	common_ancestor = findcommonancestor(a, b)
	ancestor_val = findprevvals(common_ancestor)
	max_a = findprevmax(a, common_ancestor)
	max_b = findprevmax(b, common_ancestor)
	return max(max_a, max_b) + ancestor_val

def addtosubtree(root, n):
	values[root] += n
q = int(input())
for i in range(q):
	inp = input().split()
	if inp[0] == 'add':
		addtosubtree(int(inp[1]) - 1, int(inp[2]))
	else:
		print(findmax(int(inp[1]) - 1, int(inp[2]) - 1))


n = int(input())
values = [0 for x in range(n)]
parents = [None for x in range(n)]
levels = [0 for x in range(n)]
connections = [[] for x in range(n)]
for i in range(n - 1):
	(a, b) = [int(x) - 1 for x in input().split()]
	connections[a].append(b)
	connections[b].append(a)
from collections import deque
queue = deque([(0, 0)])
visited = set()
while queue:
	(node, level) = queue.popleft()
	visited.add(node)
	levels[node] = level
	for i in connections[node]:
		if i not in visited:
			parents[i] = node
			queue.append((i, level + 1))

def findcommonancestor(a, b):
	if levels[a] > levels[b]:
		for _ in range(levels[a] - levels[b]):
			a = parents[a]
	elif levels[b] > levels[a]:
		for _ in range(levels[b] - levels[a]):
			b = parents[b]
	while a != b:
		(a, b) = (parents[a], parents[b])
	return a

def findprevvals(a):
	val = 0
	a = parents[a]
	while a is not None:
		val += values[a]
		a = parents[a]
	return val

def findprevmax(a, stop):
	max_a = values[a]
	while a != stop:
		a = parents[a]
		if max_a > 0:
			max_a += values[a]
		else:
			max_a = values[a]
	return max_a

def findmax(a, b):
	common_ancestor = findcommonancestor(a, b)
	ancestor_val = findprevvals(common_ancestor)
	max_a = findprevmax(a, common_ancestor)
	max_b = findprevmax(b, common_ancestor)
	return max(max_a, max_b) + ancestor_val

def addtosubtree(root, n):
	values[root] += n
q = int(input())
for i in range(q):
	inp = input().split()
	if inp[0] == 'add':
		addtosubtree(int(inp[1]) - 1, int(inp[2]))
	else:
		print(findmax(int(inp[1]) - 1, int(inp[2]) - 1))


n = int(input())
values = [0 for x in range(n)]
parents = [None for x in range(n)]
levels = [0 for x in range(n)]
connections = [[] for x in range(n)]
for i in range(n - 1):
	(a, b) = [int(x) - 1 for x in input().split()]
	connections[a].append(b)
	connections[b].append(a)
from collections import deque
queue = deque([(0, 0)])
visited = set()
while queue:
	(node, level) = queue.popleft()
	visited.add(node)
	levels[node] = level
	for i in connections[node]:
		if i not in visited:
			parents[i] = node
			queue.append((i, level + 1))

def findcommonancestor(a, b):
	if levels[a] > levels[b]:
		for _ in range(levels[a] - levels[b]):
			a = parents[a]
	elif levels[b] > levels[a]:
		for _ in range(levels[b] - levels[a]):
			b = parents[b]
	while a != b:
		(a, b) = (parents[a], parents[b])
	return a

def findprevvals(a):
	val = 0
	a = parents[a]
	while a is not None:
		val += values[a]
		a = parents[a]
	return val

def findprevmax(a, stop):
	max_a = values[a]
	while a != stop:
		a = parents[a]
		if max_a > 0:
			max_a += values[a]
		else:
			max_a = values[a]
	return max_a

def findmax(a, b):
	common_ancestor = findcommonancestor(a, b)
	ancestor_val = findprevvals(common_ancestor)
	max_a = findprevmax(a, common_ancestor)
	max_b = findprevmax(b, common_ancestor)
	return max(max_a, max_b) + ancestor_val

def addtosubtree(root, n):
	values[root] += n
q = int(input())
for i in range(q):
	inp = input().split()
	if inp[0] == 'add':
		addtosubtree(int(inp[1]) - 1, int(inp[2]))
	else:
		print(findmax(int(inp[1]) - 1, int(inp[2]) - 1))


n = int(input())
values = [0 for x in range(n)]
parents = [None for x in range(n)]
levels = [0 for x in range(n)]
connections = [[] for x in range(n)]
for i in range(n - 1):
	(a, b) = [int(x) - 1 for x in input().split()]
	connections[a].append(b)
	connections[b].append(a)
from collections import deque
queue = deque([(0, 0)])
visited = set()
while queue:
	(node, level) = queue.popleft()
	visited.add(node)
	levels[node] = level
	for i in connections[node]:
		if i not in visited:
			parents[i] = node
			queue.append((i, level + 1))

def findcommonancestor(a, b):
	if levels[a] > levels[b]:
		for _ in range(levels[a] - levels[b]):
			a = parents[a]
	elif levels[b] > levels[a]:
		for _ in range(levels[b] - levels[a]):
			b = parents[b]
	while a != b:
		(a, b) = (parents[a], parents[b])
	return a

def findprevvals(a):
	val = 0
	a = parents[a]
	while a is not None:
		val += values[a]
		a = parents[a]
	return val

def findprevmax(a, stop):
	max_a = values[a]
	while a != stop:
		a = parents[a]
		if max_a > 0:
			max_a += values[a]
		else:
			max_a = values[a]
	return max_a

def findmax(a, b):
	common_ancestor = findcommonancestor(a, b)
	ancestor_val = findprevvals(common_ancestor)
	max_a = findprevmax(a, common_ancestor)
	max_b = findprevmax(b, common_ancestor)
	return max(max_a, max_b) + ancestor_val

def addtosubtree(root, n):
	values[root] += n
q = int(input())
for i in range(q):
	inp = input().split()
	if inp[0] == 'add':
		addtosubtree(int(inp[1]) - 1, int(inp[2]))
	else:
		print(findmax(int(inp[1]) - 1, int(inp[2]) - 1))


from collections import deque

class Node:

	def __init__(self, node_id, value=0):
		self.node_id = node_id
		self.value = value
		self.children = []

class Tree:

	def __init__(self, N):
		self.root = None
		self.tails = None
		self.graph = None
		self.values = [0] * (N + 1)
		self.parents = [None for x in range(N + 1)]
		self.levels = [0 for x in range(N + 1)]
		self.treepaths = {}

	def insert(self, target_id, node_id):
		if not self.root:
			self.root = target_id
			self.graph = {}
			self.graph[target_id] = [node_id]
			self.graph[node_id] = [target_id]
			return self.root
		else:
			self.insert_node(target_id, node_id)

	def insert_node(self, target_id, node_id):
		if target_id in self.graph:
			self.graph[target_id].append(node_id)
		else:
			self.graph[target_id] = [node_id]
		if node_id in self.graph:
			self.graph[node_id].append(target_id)
		else:
			self.graph[node_id] = [target_id]

	def buildTreepaths(self):
		completed = set()
		nodestack = deque([[self.root, 0]])
		while nodestack:
			(node, level) = nodestack.popleft()
			self.levels[node] = level
			completed.add(node)
			for child in self.graph[node]:
				if child not in completed:
					self.parents[child] = node
					nodestack.append([child, level + 1])

	def findcommonancestor(self, a, b):
		if self.levels[a] > self.levels[b]:
			for _ in range(self.levels[a] - self.levels[b]):
				a = self.parents[a]
		elif self.levels[b] > self.levels[a]:
			for _ in range(self.levels[b] - self.levels[a]):
				b = self.parents[b]
		while a != b:
			(a, b) = (self.parents[a], self.parents[b])
		return a

	def findprevvals(self, a):
		val = 0
		a = self.parents[a]
		while a is not None:
			val += self.values[a]
			a = self.parents[a]
		return val

	def findprevmax(self, a, stop):
		max_a = self.values[a]
		while a != stop:
			a = self.parents[a]
			if max_a > 0:
				max_a += self.values[a]
			else:
				max_a = self.values[a]
		return max_a

	def findmax(self, a, b):
		common_ancestor = self.findcommonancestor(a, b)
		ancestor_val = self.findprevvals(common_ancestor)
		max_a = self.findprevmax(a, common_ancestor)
		max_b = self.findprevmax(b, common_ancestor)
		return max(max_a, max_b) + ancestor_val

	def addtosubtree(self, root, n):
		self.values[root] += n
N = int(input())
T = Tree(N)
for i in range(N - 1):
	(n1, n2) = list(map(int, input().split()))
	T.insert(n1, n2)
T.buildTreepaths()
Q = int(input())
queries = []
count = 0
for i in range(Q):
	q = input().split()
	if q[0] == 'add':
		T.addtosubtree(int(q[1]), int(q[2]))
	elif q[0] == 'max':
		res = T.findmax(int(q[1]), int(q[2]))
		print(res)
		count += 1


n = int(input())
values = [0 for x in range(n)]
parents = [None for x in range(n)]
levels = [0 for x in range(n)]
connections = [[] for x in range(n)]
for i in range(n - 1):
	(a, b) = [int(x) - 1 for x in input().split()]
	connections[a].append(b)
	connections[b].append(a)
from collections import deque
queue = deque([(0, 0)])
visited = set()
while queue:
	(node, level) = queue.popleft()
	visited.add(node)
	levels[node] = level
	for i in connections[node]:
		if i not in visited:
			parents[i] = node
			queue.append((i, level + 1))

def findcommonancestor(a, b):
	if levels[a] > levels[b]:
		for _ in range(levels[a] - levels[b]):
			a = parents[a]
	elif levels[b] > levels[a]:
		for _ in range(levels[b] - levels[a]):
			b = parents[b]
	while a != b:
		(a, b) = (parents[a], parents[b])
	return a

def findprevvals(a):
	val = 0
	a = parents[a]
	while a is not None:
		val += values[a]
		a = parents[a]
	return val

def findprevmax(a, stop):
	max_a = values[a]
	while a != stop:
		a = parents[a]
		if max_a > 0:
			max_a += values[a]
		else:
			max_a = values[a]
	return max_a

def findmax(a, b):
	common_ancestor = findcommonancestor(a, b)
	ancestor_val = findprevvals(common_ancestor)
	max_a = findprevmax(a, common_ancestor)
	max_b = findprevmax(b, common_ancestor)
	return max(max_a, max_b) + ancestor_val

def addtosubtree(root, n):
	values[root] += n
q = int(input())
for i in range(q):
	inp = input().split()
	if inp[0] == 'add':
		addtosubtree(int(inp[1]) - 1, int(inp[2]))
	else:
		print(findmax(int(inp[1]) - 1, int(inp[2]) - 1))