White Falcon has a tree with $N$ nodes. Each node contains a linear function. Let's denote by $f_u(x)$ the linear function contained in the node $\mbox{u}$.  

Let's denote the path from node $\mbox{u}$ to node $\boldsymbol{\nu}$ like this: $p_1,p_2,p_3,\ldots,p_k$, where $p_1=u$ and $p_k=v$, and $p_i$ and ${p}_{i+1}$ are connected.  

White Falcon also has $\mbox{Q}$ queries. They are in the following format:  

$\mbox{1}$ $\mbox{u}$ $\boldsymbol{\nu}$ $\boldsymbol{a}$ $\boldsymbol{b}$. Assign $ax+b$ as the function of all the nodes on the path from $\mbox{u}$ to $\boldsymbol{\nu}$, i.e., $f_{p_i}(x)$ is changed to $ax+b$ where $p_1,p_2,p_3,\ldots,p_k$ is the path from $\mbox{u}$ to $\boldsymbol{\nu}$.

$2$ $\mbox{u}$ $\boldsymbol{\nu}$ $\boldsymbol{x}$. Calculate $f_{p_k}(f_{p_{k-1}}(f_{p_{k-2}}(...f_{p_1}(x)))$ modulo $(10^9+7)$

Input Format

The first line contains $N$, the number of nodes. The following $N$ lines each contain two integers $\boldsymbol{a}$ and $\boldsymbol{b}$ that describe the function $ax+b$.  

Following $N-1$ lines contain edges of the tree. 

The next line contains $\mbox{Q}$, the number of queries. Each subsequent line contains one of the queries described above.

Output Format

For every query of the second kind, print one line containing an integer, the answer for that query.  

Constraints 

$1\leq N\leq50000$ (Number of nodes) 

$1\leq Q\leq50000$ (Number of queries) 

$0\leq a,b,x<10^9+7$

Sample Input
2
1 1
1 2
1 2
2
1 2 2 1 1
2 1 2 1

Sample Output
3

Explanation

$f_1(1)=2$ 

$f_2(2)=3$

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Data structures


Solutions:
import sys

class Node:

	def __init__(self, a, b):
		self.set_function(a, b)
		self.edges = []
		self.func = None
		self.set_function(a, b)

	def set_function(self, a, b):
		self.func = lambda x: a * x + b

	def add_edge(self, edge):
		self.edges.append(edge)

	def calculate(self, x):
		return self.func(x)

class WhiteFalcon:

	def __init__(self, nodes, edges):
		self.nodes = {}
		self.edges = {}
		self.divisor = 10 ** 9 + 7
		self.known_path = {}
		self.predecessor = {}
		for (i, [a, b]) in enumerate(nodes):
			self.nodes[i + 1] = Node(a, b)
		for [n1, n2] in edges:
			self.nodes[n1].add_edge(n2)
			self.nodes[n2].add_edge(n1)
			if n2 in self.predecessor:
				raise Exception(f'n2 {n2} already has predecessor {self.predecessor[n2]} attempted another {n1}')
			self.predecessor[n2] = n1

	def find_path(self, u, v):
		if (u, v) in self.known_path:
			return self.known_path[u, v]
		v_path = [v]
		n = v
		while n in self.predecessor:
			p = self.predecessor[n]
			v_path.append(p)
			if p == u:
				v_path.reverse()
				self.known_path[u, v] = v_path
				return v_path
			n = p
		v_path.reverse()
		u_path = [u]
		n = u
		while n in self.predecessor:
			p = self.predecessor[n]
			u_path.append(p)
			if p == u:
				self.known_path[u, v] = u_path
				return u_path
			if p in v_path:
				v_path_ind = v_path.index(p)
				path = u_path + v_path[v_path_ind + 1:]
				self.known_path[u, v] = path
				return path
			n = p
		raise Exception(f'Path from {u} to {v} not found. So far: {path}')

	def set_function(self, u, v, a, b):
		path = self.find_path(u, v)
		for n in path:
			self.nodes[n].set_function(a, b)

	def run_functions(self, u, v, x):
		path = self.find_path(u, v)
		for n in path:
			x = self.nodes[n].calculate(x)
		return x % self.divisor
inp = sys.stdin
exp = 3
node_count = int(inp.readline())
functions = []
for _ in range(node_count):
	functions.append(list(map(int, inp.readline().rstrip().split())))
source_edges = []
for _ in range(node_count - 1):
	source_edges.append(list(map(int, inp.readline().rstrip().split())))
query_count = int(inp.readline())
queries = []
for _ in range(query_count):
	queries.append(list(map(int, inp.readline().rstrip().split())))
wf = WhiteFalcon(functions, source_edges)
for q in queries:
	if q[0] == 1:
		[t, u, v, a, b] = q
		wf.set_function(u, v, a, b)
	elif q[0] == 2:
		[t, u, v, x] = q
		print(wf.run_functions(u, v, x))
inp = sys.stdin


import sys

class Node:

	def __init__(self, a, b):
		self.set_function(a, b)
		self.edges = []
		self.func = None
		self.set_function(a, b)

	def set_function(self, a, b):
		self.func = lambda x: a * x + b

	def add_edge(self, edge):
		self.edges.append(edge)

	def calculate(self, x):
		return self.func(x)

class WhiteFalcon:

	def __init__(self, nodes, edges):
		self.nodes = {}
		self.edges = {}
		self.divisor = 10 ** 9 + 7
		self.known_path = {}
		self.predecessor = {}
		for (i, [a, b]) in enumerate(nodes):
			self.nodes[i + 1] = Node(a, b)
		for [n1, n2] in edges:
			self.nodes[n1].add_edge(n2)
			self.nodes[n2].add_edge(n1)
			if n2 in self.predecessor:
				raise Exception(f'n2 {n2} already has predecessor {self.predecessor[n2]} attempted another {n1}')
			self.predecessor[n2] = n1

	def find_path(self, u, v):
		if (u, v) in self.known_path:
			return self.known_path[u, v]
		v_path = [v]
		n = v
		while n in self.predecessor:
			p = self.predecessor[n]
			v_path.append(p)
			if p == u:
				v_path.reverse()
				self.known_path[u, v] = v_path
				return v_path
			n = p
		v_path.reverse()
		u_path = [u]
		n = u
		while n in self.predecessor:
			p = self.predecessor[n]
			u_path.append(p)
			if p == u:
				self.known_path[u, v] = u_path
				return u_path
			if p in v_path:
				v_path_ind = v_path.index(p)
				path = u_path + v_path[v_path_ind + 1:]
				self.known_path[u, v] = path
				return path
			n = p
		raise Exception(f'Path from {u} to {v} not found. So far: {path}')

	def set_function(self, u, v, a, b):
		path = self.find_path(u, v)
		for n in path:
			self.nodes[n].set_function(a, b)

	def run_functions(self, u, v, x):
		path = self.find_path(u, v)
		for n in path:
			x = self.nodes[n].calculate(x)
		return x % self.divisor
inp = sys.stdin
exp = 3
node_count = int(inp.readline())
functions = []
for _ in range(node_count):
	functions.append(list(map(int, inp.readline().rstrip().split())))
source_edges = []
for _ in range(node_count - 1):
	source_edges.append(list(map(int, inp.readline().rstrip().split())))
query_count = int(inp.readline())
queries = []
for _ in range(query_count):
	queries.append(list(map(int, inp.readline().rstrip().split())))
wf = WhiteFalcon(functions, source_edges)
for q in queries:
	if q[0] == 1:
		[t, u, v, a, b] = q
		wf.set_function(u, v, a, b)
	elif q[0] == 2:
		[t, u, v, x] = q
		print(wf.run_functions(u, v, x))
inp = sys.stdin


import sys

class Node:

	def __init__(self, a, b):
		self.set_function(a, b)
		self.edges = []
		self.func = None
		self.set_function(a, b)

	def set_function(self, a, b):
		self.func = lambda x: a * x + b

	def add_edge(self, edge):
		self.edges.append(edge)

	def calculate(self, x):
		return self.func(x)

class WhiteFalcon:

	def __init__(self, nodes, edges):
		self.nodes = {}
		self.edges = {}
		self.divisor = 10 ** 9 + 7
		self.known_path = {}
		self.predecessor = {}
		for (i, [a, b]) in enumerate(nodes):
			self.nodes[i + 1] = Node(a, b)
		for [n1, n2] in edges:
			self.nodes[n1].add_edge(n2)
			self.nodes[n2].add_edge(n1)
			if n2 in self.predecessor:
				raise Exception(f'n2 {n2} already has predecessor {self.predecessor[n2]} attempted another {n1}')
			self.predecessor[n2] = n1

	def find_path(self, u, v):
		if (u, v) in self.known_path:
			return self.known_path[u, v]
		v_path = [v]
		n = v
		while n in self.predecessor:
			p = self.predecessor[n]
			v_path.append(p)
			if p == u:
				v_path.reverse()
				self.known_path[u, v] = v_path
				return v_path
			n = p
		v_path.reverse()
		u_path = [u]
		n = u
		while n in self.predecessor:
			p = self.predecessor[n]
			u_path.append(p)
			if p == u:
				self.known_path[u, v] = u_path
				return u_path
			if p in v_path:
				v_path_ind = v_path.index(p)
				path = u_path + v_path[v_path_ind + 1:]
				self.known_path[u, v] = path
				return path
			n = p
		raise Exception(f'Path from {u} to {v} not found. So far: {path}')

	def set_function(self, u, v, a, b):
		path = self.find_path(u, v)
		for n in path:
			self.nodes[n].set_function(a, b)

	def run_functions(self, u, v, x):
		path = self.find_path(u, v)
		for n in path:
			x = self.nodes[n].calculate(x)
		return x % self.divisor
inp = sys.stdin
exp = 3
node_count = int(inp.readline())
functions = []
for _ in range(node_count):
	functions.append(list(map(int, inp.readline().rstrip().split())))
source_edges = []
for _ in range(node_count - 1):
	source_edges.append(list(map(int, inp.readline().rstrip().split())))
query_count = int(inp.readline())
queries = []
for _ in range(query_count):
	queries.append(list(map(int, inp.readline().rstrip().split())))
wf = WhiteFalcon(functions, source_edges)
for q in queries:
	if q[0] == 1:
		[t, u, v, a, b] = q
		wf.set_function(u, v, a, b)
	elif q[0] == 2:
		[t, u, v, x] = q
		print(wf.run_functions(u, v, x))
inp = sys.stdin