Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given a tree with $N$ nodes (numbered $1$ through $N$), rooted at node $1$. For each valid $i$, node $i$ has a value $a_{i}$ written on it.

An undirected simple path between any two nodes $u$ and $v$ is said to be vertical if $u=v$ or $u$ is an ancestor of $v$ or $v$ is an ancestor of $u$. Let's define a *vertical partition* of the tree as a set of vertical paths such that each node belongs to exactly one of these paths.

You are also given a sequence of $N$ integers $b_{1}, b_{2}, \ldots, b_{N}$. A vertical partition is *good* if, for each of its paths, we can permute the values written on the nodes in this path, and this can be done in such a way that we reach a state where for each valid $i$, the value written on node $i$ is $b_{i}$.

The difficulty of your task is described by a parameter $S$. If $S=1$, your task is only to determine whether at least one good vertical partition exists. If $S=2$, you are required to find the number of good vertical partitions modulo $1,000,000,007$ ($10^{9}+7$).

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $S$.
Each of the next $N-1$ lines contains two space-separated integers $u$ and $v$ denoting that nodes $u$ and $v$ are connected by an edge.
The next line contains $N$ space-separated integers $a_{1}, a_{2}, \ldots, a_{N}$.
The line after that contains $N$ space-separated integers $b_{1}, b_{2}, \ldots, b_{N}$.

------  Output ------
For each test case, print a single line containing one integer:
If $S=1$, this integer should be $1$ if a good vertical partition exists or $0$ if it does not exist.
If $S=2$, this integer should be the number of good vertical partitions modulo $1,000,000,007$ ($10^{9}+7$).

------  Constraints ------
$1 ≤ T ≤ 10^{6}$
$1 ≤ N ≤ 10^{5}$
$S \in \{1, 2\}$
$1 ≤ u, v ≤ N$
the graph described on the input is a tree
$1 ≤ a_{i}, b_{i} ≤ 10^{6}$ for each valid $i$
the sum of $N$ over all test cases does not exceed $10^{6}$

------  Subtasks ------
Subtask #1 (40 points, time limit 1 seconds): the sum of $N$ over all test cases does not exceed $1,000$

Subtask #2 (30 points, time limit 2 seconds): $S = 1$

Subtask #3 (30 points, time limit 2 seconds): original constraints

----- Sample Input 1 ------ 
4

3 2

1 2

2 3

4 5 6

4 6 5

6 2

1 2

1 3

2 4

3 5

3 6

10 20 30 40 50 60

10 40 50 20 30 60

6 1

1 2

1 3

2 4

3 5

3 6

10 20 30 40 50 60

10 40 50 20 30 60

1 2

1

2
----- Sample Output 1 ------ 
2

3

1

0
----- explanation 1 ------ 
Example case 1: The good vertical partitions are $\{[1], [2, 3]\}$ and $\{[1, 2, 3]\}$.

Example case 2: The good vertical partitions are:
- $\{[1, 2, 4], [3, 5], [6]\}$
- $\{[1], [2, 4], [3, 5], [6]\}$
- $\{[1, 3, 5], [2, 4], [6]\}$

Example case 3: The same as example case 2, but with $S=1$.

Example case 4: There is no good vertical partition.

Difficulty: VERY_HARD
Tags: Graph algorithms

Graph traversal

Greedy algorithms

Tree algorithms

Dynamic programming

Mathematics

Data structures
Skill types: Dynamic programming

Data structures

Greedy algorithms

Starter code:

Solutions:
import sys
sys.setrecursionlimit(100100)

def solve():
	(n, s) = map(int, input().split())
	children = []
	for i in range(n):
		children.append([])
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		children[u - 1].append(v - 1)
		children[v - 1].append(u - 1)
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	vis = [False] * n
	(req, avail, comb) = find_path(0, children, a, b, vis)
	if req or req is None:
		print(0)
	elif s == 1:
		print(1)
	else:
		print(comb % MODULO)
MODULO = 1000000007

def find_path(node, children, a, b, vis):
	connected = False
	vis[node] = True
	(ret_req, ret_avail, children_comb) = (None, None, 1)
	for child in children[node]:
		if vis[child]:
			continue
		(req, avail, comb) = find_path(child, children, a, b, vis)
		if req:
			if connected:
				return (None, None, None)
			connected = True
			if a[node] != b[node]:
				if b[node] in avail:
					if avail[b[node]] == 1:
						del avail[b[node]]
					else:
						avail[b[node]] -= 1
				elif b[node] in req:
					req[b[node]] += 1
				else:
					req[b[node]] = 1
				if a[node] in req:
					if req[a[node]] == 1:
						del req[a[node]]
					else:
						req[a[node]] -= 1
				elif a[node] in avail:
					avail[a[node]] += 1
				else:
					avail[a[node]] = 1
			(ret_req, ret_avail) = (req, avail)
		elif req is None:
			return (None, None, None)
		children_comb = children_comb * comb
	if not connected:
		(ret_req, ret_avail) = ({}, {})
		if a[node] != b[node]:
			ret_req[b[node]] = 1
			ret_avail[a[node]] = 1
		if node != 0:
			children_comb = children_comb * len(children[node])
		else:
			children_comb = children_comb * (len(children[node]) + 1)
	return (ret_req, ret_avail, children_comb)
t = int(input())
for i in range(t):
	solve()


MOD = int(1000000000.0 + 7)

class TreeNode:

	def __init__(self, val=0, children=[], parent=None):
		self.v = val
		self.c = children
		self.p = parent
		self.a = 0
		self.b = 0
		self.count = 1

	def __repr__(self):
		return self.__str__()

	def __str__(self):
		return str(self.v)

def solve():
	(n, ss) = map(int, input().split())
	nodes = [None]
	for i in range(1, n + 1):
		nodes.append(TreeNode(i, []))
	edges = {}
	for i in range(1, n):
		s = input()
		(u, v) = map(int, s.split())
		if u in edges:
			edges[u].append(v)
		else:
			edges[u] = [v]
		if v in edges:
			edges[v].append(u)
		else:
			edges[v] = [u]
	st = [nodes[1]]
	done = {}
	if len(edges) > 0:
		while len(st) > 0:
			node = st.pop()
			done[node.v] = True
			for c in edges[node.v]:
				if not c in done:
					node.c.append(nodes[c])
					nodes[c].p = node
					st.append(nodes[c])
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	for i in range(1, n + 1):
		nodes[i].a = a[i - 1]
		nodes[i].b = b[i - 1]
	levels = [[nodes[1]]]
	while len(levels[-1]) > 0:
		l = []
		for node in levels[-1]:
			l.extend(node.c)
		levels.append(l)
	levels.pop()
	ans = 1
	passed = {}
	for i in range(len(levels) - 1, -1, -1):
		for node in levels[i]:
			if node.v in passed:
				continue
			ans = ans * (len(node.c) + 1) % MOD
			if node.a == node.b:
				continue
			cur = node
			diff = {}
			while True:
				if cur.v in passed:
					print(0)
					return
				passed[cur.v] = True
				if cur.a in diff:
					diff[cur.a] -= 1
					if diff[cur.a] == 0:
						del diff[cur.a]
				else:
					diff[cur.a] = -1
				if cur.b in diff:
					diff[cur.b] += 1
					if diff[cur.b] == 0:
						del diff[cur.b]
				else:
					diff[cur.b] = 1
				temp_v = cur.v
				if cur.v == 1 and len(diff) > 0:
					print(0)
					return
				cur = cur.p
				if len(diff) == 0:
					break
	if ss == 2:
		print(ans)
	elif ans >= 1:
		print(1)
	else:
		print(0)
t = int(input())
for _ in range(t):
	solve()


from functools import reduce
from collections import deque
from math import gcd

def ints():
	return map(int, input().split())

def bfs(graph, v):
	q = deque()
	vis = set([v])
	q.append(v)
	ans = [v]
	par = {v: -1}
	while q:
		curr = q.popleft()
		for nbr in graph[curr]:
			if nbr not in vis:
				par[nbr] = curr
				vis.add(nbr)
				q.append(nbr)
				ans.append(nbr)
	return (ans[::-1], par)

def find_path(v, par, a, b, vis):
	if a[v] == b[v]:
		return (v, v)
	count = {a[v]: 1, b[v]: -1}
	orig = v
	while True:
		v = par[v]
		if v == -1 or v in vis:
			return False
		vis.add(v)
		if a[v] not in count:
			count[a[v]] = 0
		if b[v] not in count:
			count[b[v]] = 0
		count[a[v]] += 1
		count[b[v]] -= 1
		if count[a[v]] == 0:
			del count[a[v]]
		if b[v] in count and count[b[v]] == 0:
			del count[b[v]]
		if not count:
			return tuple([v, orig])

def main(n, s, graph, a, b):
	(revord, par) = bfs(graph, 0)
	ans = []
	vis = set()
	for v in revord:
		if v not in vis:
			vis.add(v)
			verd = find_path(v, par, a, b, vis)
			if not verd:
				return (0, revord, par)
			ans.append(verd)
	return (ans, revord, par)

def make_graph(v, graph, par, newgraph, nextv, vis):
	vis.add(v[0])
	for nbr in graph[v[1]]:
		if nbr == par[v[1]]:
			continue
		newgraph[v].append((nbr, nextv[nbr]))
		make_graph((nbr, nextv[nbr]), graph, par, newgraph, nextv, vis)
mod = 10 ** 9 + 7

def mult(x, y):
	return x * y % mod
t = int(input())
for _ in range(t):
	(n, s) = ints()
	graph = {i: [] for i in range(n)}
	for __ in range(n - 1):
		(a, b) = ints()
		(a, b) = (a - 1, b - 1)
		graph[a].append(b)
		graph[b].append(a)
	a = list(ints())
	b = list(ints())
	(ans, rev, par) = main(n, s, graph, a, b)
	if not ans:
		print(0)
	else:
		nextv = {v[0]: v[1] for v in ans}
		newgraph = {i: [] for i in ans}
		vis = set()
		for v in reversed(rev):
			if v not in vis and v in nextv:
				make_graph((v, nextv[v]), graph, par, newgraph, nextv, vis)
		fin = reduce(mult, [len(newgraph[x]) + 1 for x in newgraph])
		if s == 1:
			print(1)
		else:
			print(fin)


import sys
sys.setrecursionlimit(10 ** 6)
from collections import deque
from queue import PriorityQueue
from math import gcd
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7

def dfs(u, p):
	t = 0
	leaf = True
	fl = True
	sub = False
	count = 0
	n1 = {}
	n2 = {}
	ans = 1
	xy = 1
	for i in adj[u]:
		if i == p:
			continue
		leaf = False
		mn = dfs(i, u)
		count += 1
		if mn[0][1] == False:
			return mn
		elif mn[0][0] == False:
			if t == 1:
				return [[False, False, {}, {}], -1]
			else:
				m1 = mn[0][2]
				m2 = mn[0][3]
				t = 1
				xy = mn[1]
				m1[a[u]] = m1.get(a[u], 0) + 1
				m2[b[u]] = m2.get(b[u], 0) + 1
				sub = True
				for j in m1:
					if m2.get(j):
						if m2[j] != m1[j]:
							fl = False
							n1 = m1
							n2 = m2
							break
					else:
						fl = False
						n1 = m1
						n2 = m2
						break
		else:
			ans = ans * mn[1] % mod
	if leaf:
		if a[u] == b[u]:
			return [[True, True, {a[u]: 1}, {b[u]: 1}], 1]
		else:
			return [[False, True, {a[u]: 1}, {b[u]: 1}], 1]
	if fl == True:
		if sub == False:
			if a[u] == b[u]:
				return [[True, True], ans * (count + 1) % mod]
			else:
				return [[False, True, {a[u]: 1}, {b[u]: 1}], ans * (count + 1) % mod]
		return [[True, True], ans * xy % mod]
	else:
		return [[False, True, n1, n2], ans * xy % mod]
for _ in range(ii()):
	(n, s) = il()
	adj = [[] for i in range(n + 1)]
	for _ in range(n - 1):
		(x, y) = il()
		ap(adj, x, y)
		ap(adj, y, x)
	a = [0] + il()
	b = [0] + il()
	mn = dfs(1, 0)
	if mn[0][0] and mn[0][1]:
		if s == 1:
			print(1)
		else:
			print(mn[1])
	else:
		print(0)


import sys
sys.setrecursionlimit(10 ** 6)
N = 10 ** 5 + 10
global n, s
mod = 10 ** 9 + 7
global ok
graph = [[] for i in range(N)]
spec = [0 for i in range(N)]
(a, b) = ([0 for i in range(N)], [0 for i in range(N)])
dp = [0 for i in range(N)]
bal = [{} for i in range(N)]
dummy = {}

def dfs1(node, par, cntr, freq):
	global ok
	cnt = 0
	for to in graph[node]:
		if to == par:
			continue
		(tempo, t_freq) = dfs1(to, node, bal[to], 0)
		if not ok:
			return (dummy, -1)
		if t_freq == 0:
			spec[to] = 1
			tempo.clear()
		else:
			cnt += 1
			cntr = tempo
			freq = t_freq
	if cnt > 1:
		ok = False
		return (dummy, -1)
	aa = a[node]
	bb = b[node]
	if cntr.get(aa, 0) == 0:
		freq += 1
		cntr[aa] = cntr.get(aa, 0) - 1
	else:
		cntr[aa] = cntr.get(aa, 0) - 1
		if cntr.get(aa, 0) == 0:
			freq -= 1
	if cntr.get(bb, 0) == 0:
		freq += 1
		cntr[bb] = cntr.get(bb, 0) + 1
	else:
		cntr[bb] = cntr.get(bb, 0) + 1
		if cntr.get(bb, 0) == 0:
			freq -= 1
	return (cntr, freq)

def dfs2(node, par):
	global ok
	dp[node] = 1
	cnt = 0
	temp = True
	for to in graph[node]:
		if to == par:
			continue
		if not spec[to]:
			temp = False
		dfs2(to, node)
		dp[node] *= dp[to]
		dp[node] %= mod
		cnt += 1
	if temp:
		dp[node] *= cnt + 1
		dp[node] %= mod
for _ in range(int(input())):
	global ok
	(n, s) = [int(i) for i in input().split()]
	ok = True
	for i in range(n - 1):
		(u, v) = [int(i) for i in input().split()]
		u -= 1
		v -= 1
		graph[u].append(v)
		graph[v].append(u)
	t1 = [int(i) for i in input().split()]
	t2 = [int(i) for i in input().split()]
	for i in range(n):
		a[i] = t1[i]
		b[i] = t2[i]
	(not_req, freq) = dfs1(0, -1, bal[0], 0)
	if freq != 0:
		ok = False
	else:
		spec[0] = True
	if not ok:
		print(0)
	elif s == 1:
		print(1)
	else:
		dfs2(0, -1)
		print(dp[0])
	for i in range(n):
		graph[i].clear()
		dp[i] = 0
		spec[i] = 0
		bal[i].clear()


from collections import defaultdict, deque
from sys import stdin
input = stdin.readline
MODULO = 1000000007

def buildtree(parents, graph, N):
	queue = [(1, 0)]
	while queue:
		(u, parent) = queue.pop()
		for v in graph[u]:
			if v != parent:
				parents[v] = u
				queue.append((v, u))
	if N == 1:
		leaves = deque([1])
	else:
		leaves = deque([])
		for u in range(2, N + 1):
			if len(graph[u]) == 1:
				leaves.append(u)
	return leaves

def buildpartition(graph, parents, leaves, A, B, N):
	partition = [0] * (N + 1)
	increment = 1
	while leaves:
		u = leaves.pop()
		count = defaultdict(int)
		nonzero = 0
		while u != 0 and partition[u] == 0:
			if A[u] != B[u]:
				if count[A[u]] == 0:
					count[A[u]] = 1
					nonzero += 1
				else:
					count[A[u]] += 1
					if count[A[u]] == 0:
						nonzero -= 1
				if count[B[u]] == 0:
					count[B[u]] = -1
					nonzero += 1
				else:
					count[B[u]] -= 1
					if count[B[u]] == 0:
						nonzero -= 1
			partition[u] = increment
			if nonzero == 0:
				break
			u = parents[u]
		if u == 0 or partition[u] != increment:
			return None
		increment += 1
		u = parents[u]
		if u != 0 and partition[u] == 0:
			ok = True
			for v in graph[u]:
				if v != parents[u] and partition[v] == 0:
					ok = False
					break
			if ok:
				leaves.append(u)
	return partition

def F(u, graph2):
	answer = 1 + len(graph2[u])
	for v in graph2[u]:
		answer = answer * F(v, graph2) % MODULO
	return answer

def solve(parents, N, S, graph, A, B):
	leaves = buildtree(parents, graph, N)
	partition = buildpartition(graph, parents, list(leaves), A, B, N)
	if partition == None:
		return 0
	if S == 1:
		return 1
	graph2 = {u: [] for u in partition[1:]}
	roots = []
	visited = set([])
	while leaves:
		node = leaves.pop()
		while parents[node] != 0 and partition[parents[node]] == partition[node]:
			node = parents[node]
		if node == 1:
			roots.append(partition[node])
		else:
			parent = parents[node]
			ok = True
			for v in graph[parent]:
				if v != parents[parent] and partition[v] == partition[parent]:
					ok = False
					break
			if ok:
				graph2[partition[parent]].append(partition[node])
				if parent not in visited:
					leaves.appendleft(parent)
					visited.add(parent)
			else:
				roots.append(partition[node])
	answer = 1
	for root in roots:
		answer = answer * F(root, graph2) % MODULO
	return answer
T = int(input().strip())
parents = [0] * (10 ** 5 + 1)
for problem in range(1, T + 1):
	(N, S) = [int(x) for x in input().strip().split()]
	graph = {u: [] for u in range(1, N + 1)}
	for i in range(N - 1):
		(u, v) = [int(x) for x in input().strip().split()]
		graph[u].append(v)
		graph[v].append(u)
	A = [None] + [int(x) for x in input().strip().split()]
	B = [None] + [int(x) for x in input().strip().split()]
	print(solve(parents, N, S, graph, A, B))