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

You are given a rooted tree with $N$ nodes (numbered $1$ through $N$); the root is node $1$. For each valid $i$, node $i$ has weight $w_{i}$, which is either $0$ or $1$.

We want to traverse the tree using depth first search. The order in which the nodes are visited is not uniquely defined, since we may visit the children of each node in an arbitrary order. Formally, the pseudocode of DFS-traversal is:

function DFS(node n):
	node n is visited
	for each node s (s is a son of n) in some order:
		call DFS(s)
	return
call DFS(root)

For each possible DFS-traversal of the tree, consider the sequence of weights of nodes in the order in which they are visited; each node is visited exactly once, so this sequence has length $N$. Calculate the number of inversions for each such sequence. The minimum of these numbers is the *treeversion* of our tree.

Find the treeversion of the given tree.

------  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 $w_{1}, w_{2}, \ldots, w_{N}$.
Each of the following $N-1$ lines contains two space-separated integers $x$ and $y$ denoting that nodes $x$ and $y$ are connected by an edge.

------  Output ------
For each test case, print a single line containing one integer — the treeversion of the given tree.

------  Constraints ------
$1 ≤ T ≤ 1,000$
$1 ≤ N ≤ 10^{5}$
$0 ≤ w_{i} ≤ 1$ for each valid $i$
$1 ≤ x, y ≤ N$
the graph on the input is a tree
the sum of $N$ over all test cases does not exceed $10^{6}$

------  Subtasks ------
Subtask #1 (50 points):
$1 ≤ N ≤ 1,000$
the sum of $N$ over all test cases does not exceed $10,000$

Subtask #2 (50 points): original constraints

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

3

1 0 1

1 2

1 3
----- Sample Output 1 ------ 
1

Source: codechef | Difficulty: VERY_HARD
Tags: Sorting

Graph algorithms

Graph traversal

Implementation


Solutions:
from sys import stdin, stdout
import heapq
import cProfile, math
from collections import Counter, defaultdict, deque
from bisect import bisect_left, bisect, bisect_right
import itertools
from copy import deepcopy
from fractions import Fraction
import sys, threading
import operator as op
from functools import reduce
import sys
sys.setrecursionlimit(10 ** 6)
threading.stack_size(2 ** 27)
fac_warm_up = False
printHeap = str()
memory_constrained = False
P = 10 ** 9 + 7

class MergeFind:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n
		self.num_sets = n
		self.lista = [[_] for _ in range(n)]

	def find(self, a):
		to_update = []
		while a != self.parent[a]:
			to_update.append(a)
			a = self.parent[a]
		for b in to_update:
			self.parent[b] = a
		return self.parent[a]

	def merge(self, a, b):
		a = self.find(a)
		b = self.find(b)
		if a == b:
			return
		if self.size[a] < self.size[b]:
			(a, b) = (b, a)
		self.num_sets -= 1
		self.parent[b] = a
		self.size[a] += self.size[b]
		self.lista[a] += self.lista[b]

	def set_size(self, a):
		return self.size[self.find(a)]

	def __len__(self):
		return self.num_sets

def display(string_to_print):
	stdout.write(str(string_to_print) + '\n')

def prime_factors(n):
	factors = dict()
	for i in range(2, math.ceil(math.sqrt(n)) + 1):
		while n % i == 0:
			if i in factors:
				factors[i] += 1
			else:
				factors[i] = 1
			n = n // i
	if n > 2:
		factors[n] = 1
	return factors

def all_factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def fibonacci_modP(n, MOD):
	if n < 2:
		return 1
	return (cached_fn(fibonacci_modP, (n + 1) // 2, MOD) * cached_fn(fibonacci_modP, n // 2, MOD) + cached_fn(fibonacci_modP, (n - 1) // 2, MOD) * cached_fn(fibonacci_modP, (n - 2) // 2, MOD)) % MOD

def factorial_modP_Wilson(n, p):
	if p <= n:
		return 0
	res = p - 1
	for i in range(n + 1, p):
		res = res * cached_fn(InverseEuler, i, p) % p
	return res

def binary(n, digits=20):
	b = bin(n)[2:]
	b = '0' * (digits - len(b)) + b
	return b

def is_prime(n):
	if n < 4:
		return True
	if n % 2 == 0:
		return False
	if n % 3 == 0:
		return False
	i = 5
	w = 2
	while i * i <= n:
		if n % i == 0:
			return False
		i += w
		w = 6 - w
	return True

def generate_primes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p]:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	return prime
factorial_modP = []

def warm_up_fac(MOD):
	global factorial_modP, fac_warm_up
	if fac_warm_up:
		return
	factorial_modP = [1 for _ in range(fac_warm_up_size + 1)]
	for i in range(2, fac_warm_up_size):
		factorial_modP[i] = factorial_modP[i - 1] * i % MOD
	fac_warm_up = True

def InverseEuler(n, MOD):
	return pow(n, MOD - 2, MOD)

def nCr(n, r, MOD):
	global fac_warm_up, factorial_modP
	if not fac_warm_up:
		warm_up_fac(MOD)
		fac_warm_up = True
	return factorial_modP[n] * (pow(factorial_modP[r], MOD - 2, MOD) * pow(factorial_modP[n - r], MOD - 2, MOD) % MOD) % MOD

def get_int():
	return int(stdin.readline().strip())

def get_tuple():
	return map(int, stdin.readline().split())

def get_list():
	return list(map(int, stdin.readline().split()))
memory = dict()

def clear_cache():
	global memory
	memory = dict()

def cached_fn(fn, *args):
	global memory
	if args in memory:
		return memory[args]
	else:
		result = fn(*args)
		memory[args] = result
		return result

def ncr(n, r):
	return math.factorial(n) / (math.factorial(n - r) * math.factorial(r))

def binary_search(i, li):
	fn = lambda x: li[x] - x // i
	x = -1
	b = len(li)
	while b >= 1:
		while b + x < len(li) and fn(b + x) > 0:
			x += b
		b = b // 2
	return x
TestCases = True
optimise_for_recursion = True
from functools import cmp_to_key

class SubTree:

	def __init__(self, zeros, ones, inversions):
		self.zeros = zeros
		self.ones = ones
		self.inversions = inversions

	def __str__(self):
		return '0: ' + str(self.zeros) + ' 1:' + str(self.ones) + ' Inversions:' + str(self.inversions)

def dfs(root):
	global visited, adj, weights
	visited[root] = True
	child = [vertex for vertex in adj[root] if not visited[vertex]]
	if len(child) == 0:
		return SubTree(weights[root] ^ 1, weights[root], 0)
	results = [dfs(i) for i in child]
	results.sort(key=cmp_to_key(lambda x, y: x.ones * y.zeros - x.zeros * y.ones))
	(zeros, ones, inversions) = (weights[root] ^ 1, weights[root], 0)
	factor = weights[root]
	for sub_tree in results:
		zeros += sub_tree.zeros
		ones += sub_tree.ones
		inversions += factor * sub_tree.zeros + sub_tree.inversions
		factor += sub_tree.ones
	return SubTree(zeros, ones, inversions)

def main():
	global visited, adj, weights
	n = get_int()
	weights = get_list()
	adj = [[] for _ in range(n)]
	for _ in range(n - 1):
		(x, y) = get_tuple()
		adj[x - 1].append(y - 1)
		adj[y - 1].append(x - 1)
	visited = [False for _ in range(n)]
	print(dfs(0).inversions)
if TestCases:
	for i in range(get_int()):
		main()
else:
	main() if not optimise_for_recursion else threading.Thread(target=main).start()


from abc import ABC, abstractmethod
import numpy as np

def get_int(source):
	return int(source())

def get_ints(source):
	return [int(x) for x in source().split(' ')]

def getline_from_std():
	return input()

class IOProcessing(ABC):

	@abstractmethod
	def read_test_case(self, source):
		pass

	@abstractmethod
	def process_test_case(self, tcase):
		pass

	def solve(self, input_type='from_std', output_type='to_std', input_path='', output_path='output.txt', tcase_handling='all'):
		ans = []
		if input_type == 'from_file':
			with open(input_path, 'r') as in_file:
				t = int(in_file.readline())
				for _ in range(t):
					tcase = self.read_test_case(in_file.readline)
					ans.append(self.process_test_case(tcase))
					if tcase_handling == 'single' and output_type == 'to_std':
						print(ans[-1])
		elif input_type == 'from_std':
			t = int(getline_from_std())
			for _ in range(t):
				tcase = self.read_test_case(getline_from_std)
				ans.append(self.process_test_case(tcase))
				if tcase_handling == 'single' and output_type == 'to_std':
					print(ans[-1])
		if output_type == 'to_file':
			with open(output_path, 'w') as output:
				for a in ans:
					output.write(a)
		elif output_type == 'to_std' and tcase_handling == 'all':
			for a in ans:
				print(a)
import numpy as np
import sys

class Ex_1_io(IOProcessing):

	def read_test_case(self, source):
		n = get_int(source)
		w = get_ints(source)
		edges = [[] for _ in range(n)]
		for _ in range(n - 1):
			(p, q) = get_ints(source)
			edges[p - 1].append(q - 1)
			edges[q - 1].append(p - 1)
		return (n, w, edges)

	def process_test_case(self, tcase):
		n = tcase[0]
		w = tcase[1]
		edges = tcase[2]
		inv = [0] * n
		wcount = [np.array([0, 0])] * n
		visited = [False] * n

		def dfs(v):
			visited[v] = True
			ans = 0
			wcount_new = np.array([1 - w[v], w[v]])
			wcount_children = []
			for v0 in edges[v]:
				if not visited[v0]:
					dfs(v0)
					ans += inv[v0]
					wcount_new += wcount[v0]
					wcount_children.append(wcount[v0])
			wcount_children.sort(key=lambda wc: -wc[0] / (wc[0] + wc[1]))
			sum_of_ones = 0
			sum_of_zeroes = 0
			for wc in wcount_children:
				ans += wc[0] * sum_of_ones
				sum_of_ones += wc[1]
				sum_of_zeroes += wc[0]
			if w[v] == 1:
				ans += sum_of_zeroes
			inv[v] = ans
			wcount[v] = wcount_new
		dfs(0)
		return inv[0]
sys.setrecursionlimit(1000000)
solution = Ex_1_io()
solution.solve(input_type='from_std', output_type='to_std', input_path='input.txt', output_path='output.txt', tcase_handling='all')