You are given a tree with N vertices, where the i^{th} vertex has color A_{i}.

We say that an edge of this tree *separates* color C if, upon deleting this edge from the tree, both obtained components contain at least one vertex having color C.

The *value* of an edge is defined as the sum of all the colors it *separates*. For example, if an edge separates colors \{1, 4, 7, 13\}, then, its value is 1 + 4 + 7 + 13 = 25.

Find the *value* of every edge of the tree.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains a single integer N, the number of vertices of the tree.
- The second line contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N} — the colors of the vertices.
- The next N-1 lines describe the edges of the tree. The i^{th} of these lines contains two space-separated integers u_{i} and v_{i}, denoting an edge between u_{i} and v_{i}.

------ Output Format ------ 

For each test case, output N-1 space-separated integers. The i^{th} of these integers should be the value of the i^{th} input edge.

------ Constraints ------ 

$1 ≤ T ≤ 10^{4}$
$2 ≤ N ≤ 5\cdot 10^{5}$
$1 ≤ u_{i}, v_{i} ≤ N$
- The input edges describe a tree.
$1 ≤ A_{i} ≤ 10^{9}$
- The sum of $N$ over all test cases won't exceed $5\cdot 10^{5}$.

----- Sample Input 1 ------ 
3
3
10 11 12
1 2
1 3
5
1 1 9 4 4
1 2
2 3
3 4
3 5
7
3 8 7 8 3 7 7
3 6
3 7
2 5
1 6
5 6
4 1

----- Sample Output 1 ------ 
0 0 
1 0 4 4 
7 7 8 11 11 8 

----- explanation 1 ------ 
Test case $1$: No edge separates any color. Thus, every edge has value $0$.

Test case $2$: The first input edge separates color $1$, while the third and fourth input edges separate color $4$.

Test case $3$: The colors separated by each input edge are as follows:
- Edge $1$: $\{7\}$
- Edge $2$: $\{7\}$
- Edge $3$: $\{8\}$
- Edge $4$: $\{3, 8\}$
- Edge $5$: $\{3, 8\}$
- Edge $6$: $\{8\}$

Difficulty: VERY_HARD
Tags: Tree algorithms

Graph algorithms

Data structures

Constructive algorithms
Skill types: Data structures

Starter code:

Solutions:
from sys import stdin, setrecursionlimit
input = stdin.readline
inp = lambda : list(map(int, input().split()))
setrecursionlimit(6 * 10 ** 5)

def dfs(p, prev):
	d = dict()
	nextvalue = 0
	for [u, i] in child[p]:
		if prev == u:
			continue
		(take, value) = dfs(u, p)
		ans[i] = value
		if len(take) > len(d):
			(d, take) = (take, d)
		for x in take.keys():
			if x in d:
				d[x] += take[x]
				if take[x] != total[x]:
					nextvalue -= x
					if d[x] == total[x]:
						nextvalue -= x
			else:
				d[x] = take[x]
		nextvalue += value
	if a[p - 1] not in d:
		d[a[p - 1]] = 1
		if total[a[p - 1]] > 1:
			nextvalue += a[p - 1]
	else:
		d[a[p - 1]] += 1
		if d[a[p - 1]] == total[a[p - 1]]:
			nextvalue -= a[p - 1]
	return [d, nextvalue]
t = int(input())
for _ in range(t):
	n = int(input())
	a = inp()
	total = dict()
	for i in range(n):
		total[a[i]] = total.get(a[i], 0) + 1
	child = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = inp()
		child[u].append([v, i])
		child[v].append([u, i])
	ans = [0 for i in range(n - 1)]
	dfs(1, -1)
	print(*ans)