You are given a tree with $N$ vertices (numbered $1$ through $N$) and a sequence of integers $A_1, A_2, \ldots, A_N$. You may choose an arbitrary permutation $p_1, p_2, \ldots, p_N$ of the integers $1$ through $N$. Then, for each vertex $i$, you should assign the value $A_{p_i}$ to this vertex.
The profit of a path between two vertices $u$ and $v$ is the sum of the values assigned to the vertices on that path (including $u$ and $v$).
Let's consider only (undirected) paths that start at a leaf and end at a different leaf. Calculate the maximum possible value of the sum of profits of all such paths. Since this value could be very large, compute it modulo $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 a single integer $N$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.
- Each of the following $N−1$ lines contains two space-separated integers $u$ and $v$ denoting that vertices $u$ and $v$ are connected by an edge.

-----Output-----
For each test case, print a single line containing one integer — the maximum sum of profits, modulo $10^9 + 7$.

-----Constraints-----
- $1 \le T \le 1,000$
- $1 \le N \le 300,000$
- $1 \le A_i \le 10^9$ for each valid $i$
- the sum of $N$ over all test cases does not exceed $5 \cdot 10^5$

-----Example Input-----
2
4
1 2 3 4
1 2
2 3
2 4
5
1 2 3 4 5
1 2
2 3
3 4
4 5

-----Example Output-----
24
15

-----Explanation-----
Example case 1: $(1, 4, 2, 3)$ is one of the possible permutations that give the optimal answer. Then, the profits of paths between pairs of vertices $(1, 3)$, $(1, 4)$ and $(3, 4)$ are $7$, $8$ and $9$ respectively.
Example case 2: Here, any permutation could be chosen.

Difficulty: VERY_HARD
Tags: Graph algorithms

Graph traversal

Sorting

Greedy algorithms

Dynamic programming
Skill types: Dynamic programming

Sorting

Greedy algorithms

Starter code:

Solutions:
T = int(input())
M = 10 ** 9 + 7
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	if N == 1:
		print(0)
		continue
	B = {}
	C = {}
	for i in range(N - 1):
		(u, v) = input().split()
		u = int(u) - 1
		v = int(v) - 1
		if u not in B:
			B[u] = []
		if v not in B:
			B[v] = []
		B[u].append(v)
		B[v].append(u)
	total_leaves = 0
	for i in B:
		if len(B[i]) == 1:
			total_leaves += 1
	S = [0]
	visited = [False] * N
	parent = [-1] * N
	total_visits = [0] * N
	while len(S) > 0:
		current = S.pop(len(S) - 1)
		if visited[current]:
			p = parent[current]
			if p != -1:
				total_visits[p] += total_visits[current]
				if p not in C:
					C[p] = {}
				C[p][current] = total_visits[current]
				if current not in C:
					C[current] = {}
				C[current][p] = total_leaves - C[p][current]
		else:
			S.append(current)
			visited[current] = True
			for (i, j) in enumerate(B[current]):
				if not visited[j]:
					parent[j] = current
					S.append(j)
			if len(B[current]) == 1:
				total_visits[current] = 1
				p = parent[current]
				if p != -1:
					if p not in C:
						C[p] = {}
					C[p][current] = 1
	D = {}
	for i in C:
		sum1 = 0
		for j in C[i]:
			sum1 += C[i][j]
		D[i] = sum1
	E = [0] * N
	for i in C:
		sum1 = 0
		for j in C[i]:
			D[i] -= C[i][j]
			sum1 += C[i][j] * D[i]
		E[i] = sum1
	for (i, j) in enumerate(E):
		if j == 0:
			for k in C[i]:
				E[i] = C[i][k]
	E.sort()
	E.reverse()
	A.sort()
	A.reverse()
	E = [x % M for x in E]
	A = [x % M for x in A]
	ans = 0
	for (i, j) in zip(E, A):
		a = i * j
		a %= M
		ans += a
		ans %= M
	print(ans)


inf = 10 ** 18
mod = 10 ** 9 + 7

def read_line_int():
	return [int(x) for x in input().split()]

def getDfsOrder(adj, src):
	st = [src]
	ret = []
	n = len(adj) - 1
	visited = [False] * (n + 1)
	visited[src] = True
	while len(st) > 0:
		u = st.pop()
		ret.append(u)
		for v in adj[u]:
			if not visited[v]:
				st.append(v)
				visited[v] = True
	return ret
T = read_line_int()[0]
for test in range(T):
	n = read_line_int()[0]
	a = read_line_int()
	adj = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = read_line_int()
		adj[u].append(v)
		adj[v].append(u)
	if n == 1:
		print(0)
		continue
	if n == 2:
		print(sum(a) % mod)
		continue
	mx_deg = -1
	root = -1
	for i in range(1, n + 1):
		if mx_deg < len(adj[i]):
			mx_deg = len(adj[i])
			root = i
	dfs_order = getDfsOrder(adj, root)
	sz = [0] * (n + 1)
	par = [-1] * (n + 1)
	cnt_leafs = 0
	for u in dfs_order[::-1]:
		for v in adj[u]:
			sz[u] += sz[v]
			if sz[v] == 0:
				par[u] = v
		if len(adj[u]) == 1:
			sz[u] += 1
			cnt_leafs += 1
	coef = [0] * (n + 1)
	for u in range(1, n + 1):
		s = 0
		for v in adj[u]:
			if v == par[u]:
				continue
			coef[u] += s * sz[v]
			s += sz[v]
		coef[u] += sz[u] * (cnt_leafs - sz[u])
	coef = coef[1:]
	coef = sorted(coef)
	a = sorted(a)
	ret = sum([x * y % mod for (x, y) in zip(coef, a)]) % mod
	print(ret)


import sys
sys.setrecursionlimit(10000000)

def call(node, leaf, al, p):
	ans = 0
	for i in al[node]:
		if i == p:
			continue
		ans += max(1, call(i, leaf, al, node))
	leaf[node] = max(1, ans)
	return max(1, ans)

def get(node, sum, al, p, leaf, total_l):
	ans = leaf[node] * leaf[node]
	for i in al[node]:
		if i == p:
			continue
		get(i, sum, al, node, leaf, total_l)
		ans -= leaf[i] * leaf[i]
	ans = ans // 2
	ans += leaf[node] * (total_l - leaf[node])
	sum[node] = ans
t = int(input())
for _ in range(t):
	n = int(input())
	arr = map(int, input().split())
	arr = sorted(arr)
	al = [0] * n
	for i in range(n):
		al[i] = list()
	for i in range(n - 1):
		(a, b) = input().split()
		(a, b) = (int(a) - 1, int(b) - 1)
		al[a].append(b)
		al[b].append(a)
	leaf = [0] * n
	total_l = 0
	for i in al:
		if len(i) <= 1:
			total_l += 1
	call(0, leaf, al, -1)
	sum = [0] * n
	get(0, sum, al, -1, leaf, total_l)
	sum = sorted(sum)
	(answer, mod) = (0, int(1000000000.0 + 7))
	for i in range(n):
		answer = (answer + sum[i] * arr[i]) % mod
	print(answer)