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

You are given a tree of $N$ nodes rooted at node $1$. Each node $u$ initially has a positive value $a_{u}$ associated with it.

You randomly choose one node in the tree and change its value to zero. If any node $u$ has a value equal to $0$, a random node $v$ will be chosen in the subtree of $u$ ($u \neq v$), and the values $a_{u}$ and $a_{v}$ will be swapped, hence the value of the node $v$ will become zero and the process will continue until the zero is on a leaf node. At this point, we will call the tree a final tree.

Note: there is exactly one node with a value equal to zero in a final tree and that node is a leaf node.

Your task is to tell how many different final trees are possible. Two final trees are different if there exists at least one node $u$, such that the value of the node $u$ in one final tree differs from the value of the node $u$ in the other final tree. Since the answer can be large, print it modulo $10^{9} +7$.

------ Input ------

The first line contains an integer $T$, the number of test cases. Then the test cases follow. 
The first line of each test case contains an integer $N$, the number of nodes.
Each of the next $N-1$ lines contains two integers $u$ and $v$, denoting that there is an undirected edge between the node $u$ and the node $v$.
The next line contains $N$ integers $a_{1},\ldots, a_{N}$.

------ Output ------
For each test case, output on a new line, number of different final trees possible, modulo $10^{9}+7$.

------ Constraints  ------
$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ u, v ≤ N$
$1≤ a_{i}≤ 10^{9}$
The edges form a tree structure.
The sum of $N$ over all test cases does not exceed $10^{6}$.

------ Sample Input ------

3
1
1
4
1 2
2 3
2 4
1 1 1 2
7
1 2
1 3
2 4
2 5
3 6
3 7
1 2 3 4 1 2 1

------ Sample Output ------

1
4
14

------ Explanation ------
For the first test case, the only possible final tree is when node $1$ is chosen and its value becomes 0.
For the second test case, the four possible final trees are:
- [ 1, 1, 1, 0 ]
- [ 1, 1, 0, 2 ]
- [ 1, 2, 1, 0 ]
- [ 2, 1, 1, 0 ]

( The $i$-th number in the array denotes the value of node $i$ in the final tree).

Difficulty: VERY_HARD
Tags: Graph algorithms

Graph traversal

Combinatorics

Mathematics

Spanning trees

Starter code:

Solutions:
from collections import deque

def merge(x, y):
	if len(x) > len(y):
		(x, y) = (y, x)
	for i in x:
		y[i] = y[i] + x[i] if i in y else x[i]
	return (y, y)

def NC_Dij(lis, start):
	ret = [float('inf')] * len(lis)
	ret[start] = 0
	q = deque([start])
	plis = [i for i in range(len(lis))]
	while len(q) > 0:
		now = q.popleft()
		for nex in lis[now]:
			if ret[nex] > ret[now] + 1:
				ret[nex] = ret[now] + 1
				plis[nex] = now
				q.append(nex)
	return (ret, plis)
mod = 10 ** 9 + 7
for loop in range(int(input())):
	N = int(input())
	lis = [[] for i in range(N)]
	for i in range(N - 1):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		lis[u].append(v)
		lis[v].append(u)
	(dlis, P) = NC_Dij(lis, 0)
	chnum = [0] * N
	for i in range(1, N):
		chnum[P[i]] += 1
	a = list(map(int, input().split()))
	cds = [{} for i in range(N)]
	allsum = [0] * N
	q = deque([])
	leaf = [False] * N
	ans = 0
	for i in range(N):
		if chnum[i] == 0:
			q.append(i)
			leaf[i] = True
	while q:
		v = q.popleft()
		nans = allsum[v] if a[v] not in cds[v] else allsum[v] - cds[v][a[v]]
		if leaf[v]:
			nans = 1
		nans %= mod
		ans += nans
		ans %= mod
		if a[v] not in cds[v]:
			cds[v][a[v]] = 0
		cds[v][a[v]] += nans
		cds[v][a[v]] %= mod
		if P[v] != v:
			chnum[P[v]] -= 1
			(cds[P[v]], cds[v]) = merge(cds[P[v]], cds[v])
			allsum[P[v]] = (allsum[P[v]] + allsum[v] + nans) % mod
			if chnum[P[v]] == 0:
				q.append(P[v])
	print(ans)