Greg has a tree of nodes containing integer data.  He wants to insert a node with some non-zero integer value somewhere into the tree.  His goal is to be able to cut two edges and have the values of each of the three new trees sum to the same amount.  This is called a balanced forest.  Being frugal, the data value he inserts should be minimal.  Determine the minimal amount that a new node can have to allow creation of a balanced forest.  If it's not possible to create a balanced forest, return -1.

For example, you are given node values $c=[15,12,8,14,13]$ and $edges=[[1,2],[1,3],[1,4],[4,5]]$.  It is the following tree:  

The blue node is root, the first number in a node is node number and the second is its value.  Cuts can be made between nodes $1$ and $3$ and nodes $1$ and $\begin{array}{c}4\end{array}$ to have three trees with sums $27$, $27$ and $8$.  Adding a new node $\boldsymbol{w}$ of $c[w]=19$ to the third tree completes the solution.  

Function Description

Complete the balancedForest function in the editor below.  It must return an integer representing the minimum value of $c[w]$ that can be added to allow creation of a balanced forest, or $-1$ if it is not possible.  

balancedForest has the following parameter(s):

c: an array of integers, the data values for each node  
edges: an array of 2 element arrays, the node pairs per edge  

Input Format

The first line contains a single integer, $\textit{q}$, the number of queries.  

Each of the following $\textit{q}$ sets of lines is as follows:  

The first line contains an integer, $n$, the number of nodes in the tree. 
The second line contains $n$ space-separated integers describing the respective values of $c[1],c[2],\ldots,c[n]$, where each $c[i]$ denotes the value at node $\boldsymbol{i}$.
Each of the following $n-1$ lines contains two space-separated integers, $x[j]$ and $y[j]$, describing edge $j$ connecting nodes $x[j]$ and $y[j]$.

Constraints

$1\leq q\leq5$  
$1\leq n\leq5\times10^4$  
$1\leq c[i]\leq10^9$  
Each query forms a valid undirected tree.  

Subtasks

For $30\%$ of the maximum score:

$1\leq n\leq100$
$1\leq c[i]\leq100$

For $50\%$ of the maximum score:

$1\leq n\leq2000$
$1\leq c[i]\leq10^9$

Output Format

For each query, return the minimum value of the integer $c[w]$.  If no such value exists, return $-1$ instead. 

Sample Input
2
5
1 2 2 1 1
1 2
1 3
3 5
1 4
3
1 3 5
1 3
1 2

Sample Output
2
-1

Explanation

We perform the following two queries:

The tree initially looks like this:      

Greg can add a new node $\boldsymbol{w=6}$ with $c[w]=2$ and create a new edge connecting nodes $\begin{array}{c}4\end{array}$ and $\boldsymbol{6}$. Then he cuts the edge connecting nodes $1$ and $\begin{array}{c}4\end{array}$ and the edge connecting nodes $1$ and $3$. We now have a three-tree balanced forest where each tree has a sum of $3$.    

In the second query, it's impossible to add a node in such a way that we can split the tree into a three-tree balanced forest so we return $-1$.

Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Starter code:

Solutions:
from random import randrange
import sys
sys.setrecursionlimit(10 ** 5)

def r():
	return list(map(int, input().split()))

def bin_search(arr, pred, lo=0):
	hi = len(arr)
	while lo < hi:
		mid = (lo + hi) // 2
		if pred(arr[mid]):
			hi = mid
		else:
			lo = mid + 1
	return lo if lo < len(arr) else None

class UndirectedGraph(object):

	def __init__(self, size):
		self.size = size
		self.M = 0
		self.edges = [set([]) for _ in range(self.size)]

	def add_edge(self, u, v):
		if v not in self.edges[u]:
			self.edges[u].add(v)
			self.edges[v].add(u)
			self.M += 1

	def neighbors(self, u):
		for v in self.edges[u]:
			yield v

class WeightedTree(UndirectedGraph):

	def __init__(self, size, weights):
		super().__init__(size)
		self.weights = weights
		self.labels = [None] * self.size
		self.cum_weights = [None] * self.size
		self.inverted = [False] * self.size
		self.nextnode = 0
		self.num_children = [None] * self.size
		self.root = 0

	def initialize(self):
		self.set_labels(self.root)
		self.sorted_nodes = sorted(list(range(self.size)), key=lambda x: self.cum_weights[x])

	def set_labels(self, root):
		self.dfs(root, set([]))
		self.total_weight = self.cum_weights[self.root]
		for (i, cw) in enumerate(self.cum_weights):
			if cw > self.total_weight - cw:
				self.cum_weights[i] = self.total_weight - cw
				self.inverted[i] = True

	def dfs(self, u, visited):
		visited.add(u)
		self.labels[u] = self.nextnode
		self.nextnode += 1
		self.cum_weights[u] = self.weights[u]
		self.num_children[u] = 0
		for v in self.neighbors(u):
			if v not in visited:
				(cw, nchildren) = self.dfs(v, visited)
				self.cum_weights[u] += cw
				self.num_children[u] += nchildren + 1
		return (self.cum_weights[u], self.num_children[u])

	def solve(self):
		tw = self.total_weight
		first_idx = bin_search(self.sorted_nodes, lambda u: self.cum_weights[u] >= (tw + 2) // 3)
		if first_idx is None:
			return None
		while first_idx < self.size:
			first = self.sorted_nodes[first_idx]
			first_cw = self.cum_weights[first]
			label1 = self.labels[first]
			last_child_label = label1 + self.num_children[first]
			for target_w in (tw - first_cw * 2, first_cw):
				second_idx = bin_search(self.sorted_nodes, lambda u: self.cum_weights[u] >= target_w)
				if second_idx is not None:
					while second_idx < self.size and self.cum_weights[self.sorted_nodes[second_idx]] == target_w:
						second = self.sorted_nodes[second_idx]
						is_child = label1 < self.labels[second] <= last_child_label
						is_child = is_child if not self.inverted[first] else not is_child
						if not is_child and self.labels[second] != label1:
							return first_cw * 3 - tw
						second_idx += 1
			first_idx += 1
		if 2 * first_cw == tw:
			return first_cw
		return None

def read_input():
	n = int(input())
	weights = r()
	G = WeightedTree(n, weights)
	for _ in range(n - 1):
		(u, v) = r()
		u -= 1
		v -= 1
		G.add_edge(u, v)
	G.initialize()
	return G

def main():
	q = int(input())
	for _ in range(q):
		G = read_input()
		ans = G.solve()
		print(ans if ans is not None else -1)
main()


from operator import attrgetter
from itertools import groupby
from sys import stderr

class Node:

	def __init__(self, index, value):
		self.index = index
		self.value = value
		self.children = []

def readtree():
	size = int(input())
	values = readints()
	assert size == len(values)
	nodes = [Node(i, v) for (i, v) in enumerate(values)]
	for _ in range(size - 1):
		(x, y) = readints()
		nodes[x - 1].children.append(nodes[y - 1])
		nodes[y - 1].children.append(nodes[x - 1])
	return nodes

def readints():
	return [int(fld) for fld in input().strip().split()]

def findbestbal(nodes):
	if len(nodes) == 1:
		return -1
	rootify(nodes[0])
	best = total = nodes[0].totalval
	dummynode = Node(None, None)
	dummynode.totalval = 0
	sortnode = []
	for (k, g) in groupby(sorted([dummynode] + nodes, key=attrgetter('totalval')), attrgetter('totalval')):
		sortnode.append(list(g))
	total = nodes[0].totalval
	for (ihi, n) in enumerate(sortnode):
		if 3 * n[0].totalval >= total:
			break
	else:
		assert False
	ilo = ihi - 1
	for ihi in range(ihi, len(sortnode)):
		hi = sortnode[ihi][0].totalval
		lo = sortnode[ilo][0].totalval
		while 2 * hi + lo > total:
			if lo == 0:
				return -1
			if (total - lo) % 2 == 0:
				x = (total - lo) // 2
				for lonode in sortnode[ilo]:
					if uptototalval(lonode, x + lo):
						return x - lo
			ilo -= 1
			lo = sortnode[ilo][0].totalval
		if len(sortnode[ihi]) > 1:
			return 3 * hi - total
		hinode = sortnode[ihi][0]
		if 2 * hi + lo == total:
			for lonode in sortnode[ilo]:
				if uptototalval(lonode, hi) != hinode:
					return hi - lo
		y = total - 2 * hi
		if uptototalval(hinode, 2 * hi) or uptototalval(hinode, hi + y):
			return hi - y

def rootify(root):
	root.parent = root.jumpup = None
	root.depth = 0
	bfnode = [root]
	i = 0
	while i < len(bfnode):
		node = bfnode[i]
		depth = node.depth + 1
		jumpup = uptodepth(node, depth & depth - 1)
		for child in node.children:
			child.parent = node
			child.children.remove(node)
			child.depth = depth
			child.jumpup = jumpup
			bfnode.append(child)
		i += 1
	for node in reversed(bfnode):
		node.totalval = node.value + sum((child.totalval for child in node.children))

def uptodepth(node, depth):
	while node.depth > depth:
		if node.jumpup.depth <= depth:
			node = node.jumpup
		else:
			node = node.parent
	return node

def uptototalval(node, totalval):
	try:
		while node.totalval < totalval:
			if node.parent is None:
				return None
			if node.jumpup.totalval <= totalval:
				node = node.jumpup
			else:
				node = node.parent
		if node.totalval == totalval:
			return node
		else:
			return None
	except Exception:
		return None
ncases = int(input())
for _ in range(ncases):
	print(findbestbal(readtree()))


from collections import deque

def dfs(Ci, edges, parent, node, visited):
	visited.add(node)
	neighbors = edges[node]
	if node != 0 and len(neighbors) == 1:
		return
	for n in neighbors:
		if n in visited:
			continue
		parent[n] = node
		dfs(Ci, edges, parent, n, visited)
		Ci[node] += Ci[n]

def addToParent(Ci, edges, parent, node, val):
	if node > 0:
		parent_node = parent[node]
		Ci[parent_node] += val
		addToParent(Ci, edges, parent, parent_node, val)

def searchValue(Ci, edges, parent, node, val, noFollow=-1):
	parent_node = parent[node]
	neighbors = edges[node]
	for n in neighbors:
		if n == parent_node or n == noFollow:
			continue
		if Ci[n] == val:
			return True
		if Ci[n] > val:
			if searchValue(Ci, edges, parent, n, val, noFollow=noFollow):
				return True
	return False

def checkSplit(Ci, edges, parent, node):
	if node == 0:
		return None
	c = Ci[0]
	a = Ci[node]
	b = c - a
	if a == b:
		return a
	if a > b and a <= 2 * b:
		if searchValue(Ci, edges, parent, node, val=b):
			return 2 * b - a
	if a > 2 * b and a % 2 == 0:
		if searchValue(Ci, edges, parent, node, val=a // 2):
			return a // 2 - b
	if b > a and b <= 2 * a:
		addToParent(Ci, edges, parent, node, val=-a)
		if searchValue(Ci, edges, parent, 0, val=a, noFollow=node):
			addToParent(Ci, edges, parent, node, val=a)
			return 2 * a - b
		addToParent(Ci, edges, parent, node, val=a)
	if b > 2 * a and b % 2 == 0:
		addToParent(Ci, edges, parent, node, val=-a)
		if searchValue(Ci, edges, parent, 0, val=b // 2, noFollow=node):
			addToParent(Ci, edges, parent, node, val=a)
			return b // 2 - a
		addToParent(Ci, edges, parent, node, val=a)
	return None

def solution(Ci, edges):
	if len(Ci) <= 1:
		return -1
	if len(Ci) == 2:
		if Ci[0] == Ci[1]:
			return Ci[0]
		return -1
	parent = {}
	parent[0] = -1
	dfs(Ci, edges, parent, 0, set())
	output = -1
	visited = set()
	to_visit = deque()
	to_visit.append(0)
	while len(to_visit):
		node = to_visit.popleft()
		visited.add(node)
		Cw = checkSplit(Ci, edges, parent, node)
		if Cw is not None:
			if output < 0 or Cw < output:
				output = Cw
		neighbors = edges[node]
		for n in neighbors:
			if n not in visited:
				to_visit.append(n)
	return output
Q = int(input().strip())
for q in range(Q):
	N = int(input().strip())
	Ci = list(map(int, input().strip().split()))
	edges = {}
	for i in range(N - 1):
		(x, y) = list(map(int, input().strip().split()))
		x -= 1
		y -= 1
		if x not in edges:
			edges[x] = list()
		if y not in edges:
			edges[y] = list()
		edges[x].append(y)
		edges[y].append(x)
	print(solution(Ci, edges))


import time

def timing(f):

	def wrap(*args):
		time1 = time.time()
		ret = f(*args)
		time2 = time.time()
		print('%s function took %0.3f ms' % (f.__name__, (time2 - time1) * 1000.0))
		return ret
	return wrap

def depth_first_traversal(node, prev_node):
	global ticker
	ticker += 1
	tree_dict[node]['in'] = ticker
	tree_dict[node]['score'] = coins_list[node]
	for child in node_dict[node]:
		if child != prev_node:
			depth_first_traversal(child, node)
			tree_dict[node]['score'] += tree_dict[child]['score']
	tree_dict[node]['out'] = ticker
	return

def valid_C3(node):
	global Cmin
	C3 = tree_dict[node]['score']
	C2 = (tree_sum - C3) // 2
	Cw = C2 - C3
	if (tree_sum - C3) % 2 != 0:
		return
	if C2 in max_time.keys() and (tree_dict[max_node[C2]]['in'] > tree_dict[node]['in'] or tree_dict[max_node[C2]]['out'] < tree_dict[node]['in']):
		Cmin = Cw if Cmin == None else min(Cmin, Cw)
	elif C2 in min_time.keys() and (tree_dict[min_node[C2]]['in'] > tree_dict[node]['in'] or tree_dict[min_node[C2]]['out'] < tree_dict[node]['in']):
		Cmin = Cw if Cmin == None else min(Cmin, Cw)
	elif C2 + C3 in min_time.keys() and (tree_dict[min_node[C2 + C3]]['in'] < tree_dict[node]['in'] and tree_dict[min_node[C2 + C3]]['out'] >= tree_dict[node]['in']):
		Cmin = Cw if Cmin == None else min(Cmin, Cw)
	elif C2 + C3 in max_time.keys() and (tree_dict[max_node[C2 + C3]]['in'] < tree_dict[node]['in'] and tree_dict[max_node[C2 + C3]]['out'] >= tree_dict[node]['in']):
		Cmin = Cw if Cmin == None else min(Cmin, Cw)
	return

def valid_C2(node):
	global Cmin
	C2 = tree_dict[node]['score']
	Cw = 3 * C2 - tree_sum
	C3 = C2 - Cw
	if min_time[C2] != max_time[C2]:
		Cmin = Cw if Cmin == None else min(Cmin, Cw)
	elif C3 in max_time.keys() and (tree_dict[node]['in'] > tree_dict[max_node[C3]]['in'] or tree_dict[node]['out'] < tree_dict[max_node[C3]]['in']):
		Cmin = Cw if Cmin == None else min(Cmin, Cw)
	elif C3 in min_time.keys() and (tree_dict[node]['in'] > tree_dict[min_node[C3]]['in'] or tree_dict[node]['out'] < tree_dict[min_node[C3]]['in']):
		Cmin = Cw if Cmin == None else min(Cmin, Cw)
	elif C2 + C3 in min_time.keys():
		Cmin = Cw if Cmin == None else min(Cmin, Cw)
	elif 2 * C2 in min_time.keys():
		Cmin = Cw if Cmin == None else min(Cmin, Cw)
	return

def main():
	N = int(input())
	global coins_list, node_dict, tree_dict, min_time, max_time, min_node, max_node, ticker, Cmin, tree_sum
	node_dict = {i: [] for i in range(1, N + 1)}
	tree_dict = {i: {'score': 0, 'in': 0, 'out': 0} for i in range(1, N + 1)}
	(min_time, max_time, min_node, max_node) = ({}, {}, {}, {})
	(ticker, tree_sum) = (0, 0)
	Cmin = None
	coins_list = [0] + [x for x in list(map(int, input().split()))]
	tree_sum = sum(coins_list)
	for _ in range(1, N):
		(x, y) = map(int, input().split())
		node_dict[x].append(y)
		node_dict[y].append(x)
	depth_first_traversal(1, 0)
	for node in range(1, N + 1):
		if tree_dict[node]['score'] not in min_time.keys():
			min_time[tree_dict[node]['score']] = tree_dict[node]['in']
			min_node[tree_dict[node]['score']] = node
			max_time[tree_dict[node]['score']] = tree_dict[node]['in']
			max_node[tree_dict[node]['score']] = node
		elif tree_dict[node]['in'] > min_time[tree_dict[node]['score']]:
			max_time[tree_dict[node]['score']] = tree_dict[node]['in']
			max_time[tree_dict[node]['score']] = node
		else:
			min_time[tree_dict[node]['score']] = tree_dict[node]['in']
			min_time[tree_dict[node]['score']] = node
	if tree_sum % 2 == 0 and tree_sum // 2 in min_time.keys():
		Cmin = tree_sum // 2
	for node in range(1, N + 1):
		if tree_dict[node]['score'] <= tree_sum // 3:
			valid_C3(node)
		elif tree_dict[node]['score'] <= tree_sum // 2:
			valid_C2(node)
	if Cmin == None:
		print(-1)
	else:
		print(Cmin)
	return
T = int(input())
for _ in range(T):
	main()


import math
import copy
import sys
sys.setrecursionlimit(60000)

def DFS_Recursive(graph, currentNode, splitGraph, totalCoins, explored_global):
	explored_global[currentNode] = True
	if currentNode not in graph:
		return
	totSplitValue = coins[currentNode - 1]
	for node in graph[currentNode]:
		if node not in explored_global:
			splitValue = DFS_Recursive(graph, node, splitGraph, totalCoins, explored_global)
			if splitValue in splitGraph:
				splitGraph[splitValue].append([node, currentNode])
				splitGraph[totalCoins - splitValue].append([currentNode, node])
			else:
				splitGraph[splitValue] = [[node, currentNode]]
				splitGraph[totalCoins - splitValue] = [[currentNode, node]]
			totSplitValue = totSplitValue + splitValue
	return totSplitValue

def FindLeaf(graph, node):
	explored = {}
	toContinue = True
	while toContinue:
		toContinue = False
		for n in graph[node]:
			if n in explored:
				continue
			else:
				node = n
				explored[n] = True
				toContinue = True
				break
	return node

def FindOutput(graph, coins):
	totalCoins = sum(coins)
	idealSplit = math.ceil(totalCoins / 3)
	outOfBoundSplit = math.ceil(totalCoins / 2)
	leafNode = FindLeaf(graph, 1)
	splitGraphFirst = {}
	explored_global = {}
	DFS_Recursive(graph, leafNode, splitGraphFirst, totalCoins, explored_global)
	splitGraphFirst[totalCoins] = True
	explored_global = {}
	smallestChosenSplit = totalCoins + 1
	for currentSplit in splitGraphFirst:
		if currentSplit >= idealSplit and currentSplit <= outOfBoundSplit:
			if currentSplit > smallestChosenSplit:
				continue
			if len(splitGraphFirst[currentSplit]) > 1:
				if currentSplit < smallestChosenSplit:
					smallestChosenSplit = currentSplit
			if 2 * currentSplit not in splitGraphFirst:
				continue
			pendingGraph = copy.deepcopy(graph)
			(fromEdge, toEdge) = splitGraphFirst[currentSplit][0]
			pendingGraph[fromEdge].remove(toEdge)
			pendingGraph[toEdge].remove(fromEdge)
			leafNode = FindLeaf(pendingGraph, toEdge)
			splitGraphSecond = {}
			explored_global = {}
			newTotalCoins = totalCoins - currentSplit
			splitGraphSecond[newTotalCoins] = True
			DFS_Recursive(pendingGraph, leafNode, splitGraphSecond, newTotalCoins, explored_global)
			explored_global = {}
			if currentSplit in splitGraphSecond:
				if currentSplit < smallestChosenSplit:
					smallestChosenSplit = currentSplit
	if smallestChosenSplit == totalCoins + 1:
		return -1
	else:
		return smallestChosenSplit
numberOfTrees = int(input())
for t in range(numberOfTrees):
	numberOfNodes = int(input())
	coins = [int(c) for c in input().strip().split()]
	graph = {}
	for n in range(numberOfNodes - 1):
		(firstNode, secondNode) = [int(n) for n in input().strip().split()]
		if firstNode in graph:
			graph[firstNode].append(secondNode)
		else:
			graph[firstNode] = [secondNode]
		if secondNode in graph:
			graph[secondNode].append(firstNode)
		else:
			graph[secondNode] = [firstNode]
	chosenSplit = 0
	if len(graph) > 0:
		chosenSplit = FindOutput(graph, coins)
	extraCoin = -1
	if chosenSplit > 0:
		extraCoin = 3 * chosenSplit - sum(coins)
	print(extraCoin)


from itertools import combinations
import pdb
import math

def create_tree(edge, v):
	graph = []
	for i in range(len(v) + 1):
		graph.append([])
	graph[0].append(len(v))
	for e in edge:
		(v1, v2) = e
		graph[v1].append(v2)
		graph[v2].append(v1)
	return graph

def populate_weight(graph, v):
	weight = [{} for x in range(len(v) + 1)]
	visited = [False] * (len(v) + 1)
	stack = [1]
	comesfrom = [0 for x in range(len(v) + 1)]
	totw = 0
	for x in v:
		totw += x
	while len(stack) != 0:
		last = stack[-1]
		visited[last] = True
		notyet = False
		for adj in graph[last]:
			if not visited[adj]:
				comesfrom[adj] = last
				notyet = True
				stack.append(adj)
		if not notyet:
			ogweight = 0
			stack.pop()
			stw = 0
			for adj in graph[last]:
				if adj == comesfrom[last]:
					weight[last][adj] = 0
				else:
					weight[last][adj] = sum((weight[adj][x] for x in weight[adj] if x != last))
					ogweight += weight[last][adj]
			weight[last][last] = v[last - 1]
			ogweight += v[last - 1]
			if comesfrom[last] != 0:
				weight[last][comesfrom[last]] = totw - ogweight
	return (weight, totw)

def find_min_diff2(graph, edge, weight, v, totw):
	minw = math.inf
	visited = [False] * (len(v) + 1)
	for e in edge:
		(e0, e1) = e
		f1 = weight[e0][e1]
		f2 = totw - f1
		if f1 < f2:
			(mn, mx) = (f1, f2)
		else:
			(mn, mx) = (f2, f1)
		maxside = f1 > f2 and e1 or e0
		minside = maxside == e1 and e0 or e1
		if mx == mn:
			minw = min(minw, mn)
		elif mx - mn <= mn:
			stk = [maxside]
			for i in range(len(visited)):
				visited[i] = False
			while len(stk) != 0:
				last = stk.pop()
				visited[last] = True
				stopiter = False
				for adj in graph[last]:
					if adj != minside and (not visited[adj]):
						stk.append(adj)
						if weight[last][adj] == mn:
							minw = min(minw, mn - (mx - weight[last][adj]))
							stopiter = True
							break
						if mx - weight[last][adj] == mn:
							minw = min(minw, mn - weight[last][adj])
							stopiter = True
							break
				if stopiter:
					break
	if minw < math.inf:
		return minw
	else:
		return -1

def main():
	t = int(input())
	for x in range(t):
		n = int(input())
		coins = list(map(int, input().strip().split()))
		edge = []
		for i in range(n - 1):
			edge.append(list(map(int, input().strip().split())))
		graph = create_tree(edge, coins)
		(weight, totw) = populate_weight(graph, coins)
		print(find_min_diff2(graph, edge, weight, coins, totw))

def main2():
	f = open('blftc4.txt', 'r')
	t = int(f.readline())
	for x in range(t):
		n = int(f.readline())
		coins = list(map(int, f.readline().strip().split()))
		edge = []
		for i in range(n - 1):
			edge.append(list(map(int, f.readline().strip().split())))
		pdb.set_trace()
		graph = create_tree(edge, coins)
		(weight, totw) = populate_weight(graph, coins)
		print(find_min_diff2(graph, edge, weight, coins, totw))
	f.close()
main()


import sys
import heapq

def solve(adj, deg, c):
	n = len(adj)
	cost = sum(c)
	costs = [0] * n
	visited = [False] * n
	v2c = list(range(n))
	c2v = [[i] for i in range(n)]
	c2cnt = [1] * n
	w2c = {}
	c2w = {}

	def hasOtherComp(weight, comp):
		cnt = 0
		for item in w2c.get(weight, []):
			if item != comp:
				return True
		return False

	def add(weight, comp):
		if weight not in w2c:
			w2c[weight] = set([comp])
		else:
			w2c[weight].add(current_comp)
		if comp not in c2w:
			c2w[comp] = set([weight])
		else:
			c2w[comp].add(weight)

	def mergeInto(c1, c2):
		for v in c2v[c2]:
			v2c[v] = c1
		c2cnt[c1] += c2cnt[c2]
		for w in c2w.get(c2, []):
			comps = w2c[w]
			if c2 in comps:
				comps.remove(c2)
			if c1 not in comps:
				comps.add(c1)
				weights = c2w.get(c1, set())
				weights.add(w)
				c2w[c1] = weights

	def merge(c1, c2):
		size1 = c2cnt[c1]
		size2 = c2cnt[c2]
		if size1 < size2:
			mergeInto(c2, c1)
		else:
			mergeInto(c1, c2)
	q = []
	for i in range(n):
		if deg[i] == 1:
			heapq.heappush(q, (c[i], i))
			costs[i] = c[i]
			deg[i] = 0
	bestResult = sys.maxsize
	lastWeight = 0
	while q:
		(weight, v) = heapq.heappop(q)
		visited[v] = True
		if weight * 2 > cost:
			break
		if lastWeight == weight:
			rest = cost - lastWeight - weight
			if rest <= weight:
				bestResult = min(bestResult, weight - rest)
		for u in adj[v]:
			deg[u] -= 1
			if visited[u]:
				merge(v2c[v], v2c[u])
			elif deg[u] == 1:
				heapq.heappush(q, (weight + c[u], u))
			else:
				c[u] += weight
		rest = cost - weight * 2
		current_comp = v2c[v]
		add(weight, current_comp)
		if rest <= weight:
			has = hasOtherComp(rest, current_comp)
			if has:
				bestResult = min(bestResult, weight - rest)
		lastWeight = weight
	return bestResult if bestResult < sys.maxsize else -1
q = int(input().strip())
for i in range(q):
	n = int(input().strip())
	c = [int(x) for x in input().strip().split(' ')]
	adj = [[] for k in range(n)]
	deg = [0] * n
	for a0 in range(n - 1):
		[u, v] = [int(x) for x in input().strip().split(' ')]
		u = u - 1
		v = v - 1
		adj[u].append(v)
		adj[v].append(u)
		deg[u] += 1
		deg[v] += 1
	w = solve(adj, deg, c)
	print(w)


import sys

class Edge:

	def __init__(self, top, bottom):
		self.data = [top, bottom]

	def edge_break(self):
		self.data[0].detach(self.data[1])

	def build(self):
		self.data[0].attach(self.data[1])

class Node:

	def __init__(self, weight):
		self.weight = weight
		self.child = set()
		self.parent = None

	def attach(self, other):
		self.child.add(other)
		self.smallattach(other)

	def smallattach(self, other):
		other.parent = self
		x = self
		w = other.weight
		while x is not None:
			x.weight += w
			x = x.parent

	def detach(self, other):
		self.child.remove(other)
		other.parent = None
		x = self
		w = other.weight
		while x is not None:
			x.weight -= w
			x = x.parent

	def subtreesizes(self, minimum):
		yield self.weight
		if self.weight > minimum:
			for node in self.child:
				for x in node.subtreesizes(minimum):
					yield x

	def buildtree(self):
		if self.parent is not None:
			self.child.remove(self.parent)
		for other in self.child:
			edges.append(Edge(self, other))
			self.smallattach(other)
			other.buildtree()

def isgood(number):
	return number >= (total + 2) // 3 and number < target
q = int(input())
for _ in range(q):
	n = int(input())
	weights = [int(i) for i in input().split()]
	total = sum(weights)
	target = total // 2 + 1
	nodes = [Node(i) for i in weights]
	edges = []
	broken = []
	successful = False
	for _ in range(n - 1):
		z = [int(num) for num in input().split()]
		z.sort()
		x = nodes[z[0] - 1]
		y = nodes[z[1] - 1]
		x.child.add(y)
		y.child.add(x)
	root = nodes[0]
	root.buildtree()
	for i in range(len(edges)):
		edge = edges[i]
		top = edge.data[0]
		bot = edge.data[1]
		x = root.weight - bot.weight
		if isgood(x):
			y = bot.weight - x
			z = min(x, y)
			for w in bot.subtreesizes(z):
				if w == x or w == z:
					target = x
					break
		elif isgood(bot.weight):
			x = bot.weight
			y = root.weight - 2 * x
			z = min(x, y)
			edge.edge_break()
			for w in root.subtreesizes(z):
				if w == x or w == z:
					target = x
					break
			edge.build()
	if target == total // 2 + 1:
		print(-1)
	else:
		print(target * 3 - total)


import sys
from time import time
from collections import deque

def solve(ww, ee):

	def get_graph(root, edges):
		n = len(edges)
		cache = set()
		stack = [root]
		g = [list() for _ in range(n)]
		pp = [None for _ in range(n)]
		while stack:
			node = stack.pop()
			cache.add(node)
			for ch in edges[node]:
				if ch not in cache:
					g[node].append(ch)
					pp[ch] = node
					stack.append(ch)
		return (g, pp)

	def get_totals(root, ww, g, pp):
		totals = [None] * len(ww)
		stack = [(root, False)]
		while stack:
			(node, sumup) = stack.pop()
			if sumup:
				sm = ww[node]
				for ch in g[node]:
					sm += totals[ch]
				totals[node] = sm
			else:
				stack.append((node, True))
				for ch in g[node]:
					stack.append((ch, False))
		return totals

	def get_root(root, g):
		totals = [None] * len(ww)
		stack = [(root, False)]
		while stack:
			(node, sumup) = stack.pop()
			if sumup:
				sm = 1
				for ch in g[node]:
					sm += totals[ch]
				totals[node] = sm
			else:
				stack.append((node, True))
				for ch in g[node]:
					stack.append((ch, False))
		(root, mn, total) = (None, None, totals[root])
		for (node, t) in enumerate(totals):
			delta = abs(total - 2 * t)
			if mn is None or mn > delta:
				(root, mn) = (node, delta)
		return root

	def node_gen(root, g):
		dq = deque([root])
		while dq:
			node = dq.popleft()
			yield node
			for ch in g[node]:
				dq.append(ch)

	def is_parent(pp, n1, n2):
		node = n2
		while node is not None:
			if node == n1:
				return True
			node = pp[node]
		return False

	def gen(root, g, pp, totals):
		t = totals[root]
		candidates = []
		for node in node_gen(root, g):
			v = totals[node]
			r = v
			k = (t - r) // 2
			if (t - r) % 2 == 0 and k >= r:
				candidates.append((node, k, r))
			k = v
			r = t - 2 * k
			if r >= 0 and r <= k:
				candidates.append((node, k, r))
		candidates.sort(key=lambda t: t[1] - t[2])
		tcache = dict()
		for (node, t) in enumerate(totals):
			if t in tcache:
				tcache[t].add(node)
			else:
				tcache[t] = {node}
		for (node, k, r) in candidates:
			print('\t\tnode=%d k=%d r=%d' % (node, k, r), file=sys.stderr)
			p = pp[node]
			while p is not None:
				(fr, to) = (totals[p], totals[p] - totals[node])
				totals[p] = to
				tcache[fr].remove(p)
				if len(tcache[fr]) == 0:
					tcache.pop(fr)
				if to in tcache:
					tcache[to].add(p)
				else:
					tcache[to] = {p}
				p = pp[p]
			if totals[node] == k:
				(a, b) = (k, r)
			elif totals[node] == r:
				(a, b) = (k, k)
			if a in tcache:
				for n2 in tcache[a]:
					if not is_parent(pp, node, n2) and totals[root] - a == b:
						yield (n2, k - r)
			if b in tcache:
				for n2 in tcache[b]:
					if not is_parent(pp, node, n2) and totals[root] - b == a:
						yield (n2, k - r)
			p = pp[node]
			while p is not None:
				(fr, to) = (totals[p], totals[p] + totals[node])
				totals[p] = to
				tcache[fr].remove(p)
				if len(tcache[fr]) == 0:
					tcache.pop(fr)
				if to in tcache:
					tcache[to].add(p)
				else:
					tcache[to] = {p}
				p = pp[p]
	print('ww=%s\nee=%s' % (ww, ee), file=sys.stderr)
	edges = [list() for _ in range(len(ww))]
	for (fr, to) in ee:
		edges[fr].append(to)
		edges[to].append(fr)
	root = 0
	(g, pp) = get_graph(root, edges)
	print('\tg=%s' % (g,), file=sys.stderr)
	print('\tpp=%s' % (pp,), file=sys.stderr)
	totals = get_totals(root, ww, g, pp)
	print('\ttotals=%s' % (totals,), file=sys.stderr)
	new_root = get_root(root, g)
	print('\tnew_root=%s' % (root,), file=sys.stderr)
	if new_root != root:
		(g, pp) = get_graph(root, edges)
		print('\tg=%s' % (g,), file=sys.stderr)
		print('\tpp=%s' % (pp,), file=sys.stderr)
		totals = get_totals(root, ww, g, pp)
		print('\ttotals=%s' % (totals,), file=sys.stderr)
	for (node, delta) in gen(root, g, pp, totals):
		print('\tnode=%d delta=%d' % (node, delta), file=sys.stderr)
		return delta
	return None
tm = time()
t = int(input())
for _ in range(t):
	_ = int(input())
	ww = list(map(int, input().split()))
	ee = []
	for _ in range(len(ww) - 1):
		(fr, to) = map(int, input().split())
		ee.append((fr - 1, to - 1))
	s = solve(ww, ee)
	if s is None:
		print(-1)
	else:
		print(s)
print('time elapsed: %s' % (time() - tm,), file=sys.stderr)


import time

def timing(f):

	def wrap(*args):
		time1 = time.time()
		ret = f(*args)
		time2 = time.time()
		print('%s function took %0.3f ms' % (f.__name__, (time2 - time1) * 1000.0))
		return ret
	return wrap

def depth_first_traversal(node, prev_node):
	global ticker
	ticker += 1
	tree_dict[node]['in'] = ticker
	tree_dict[node]['score'] = coins_list[node]
	for child in node_dict[node]:
		if child != prev_node:
			depth_first_traversal(child, node)
			tree_dict[node]['score'] += tree_dict[child]['score']
	tree_dict[node]['out'] = ticker
	return

def valid_C3(node):
	global Cmin
	C3 = tree_dict[node]['score']
	C2 = (tree_sum - C3) // 2
	Cw = C2 - C3
	if (tree_sum - C3) % 2 != 0:
		return
	if C2 in max_time.keys() and (tree_dict[max_node[C2]]['in'] > tree_dict[node]['in'] or tree_dict[max_node[C2]]['out'] < tree_dict[node]['in']):
		Cmin = Cw if Cmin == None else min(Cmin, Cw)
	elif C2 in min_time.keys() and (tree_dict[min_node[C2]]['in'] > tree_dict[node]['in'] or tree_dict[min_node[C2]]['out'] < tree_dict[node]['in']):
		Cmin = Cw if Cmin == None else min(Cmin, Cw)
	elif C2 + C3 in min_time.keys() and (tree_dict[min_node[C2 + C3]]['in'] < tree_dict[node]['in'] and tree_dict[min_node[C2 + C3]]['out'] >= tree_dict[node]['in']):
		Cmin = Cw if Cmin == None else min(Cmin, Cw)
	elif C2 + C3 in max_time.keys() and (tree_dict[max_node[C2 + C3]]['in'] < tree_dict[node]['in'] and tree_dict[max_node[C2 + C3]]['out'] >= tree_dict[node]['in']):
		Cmin = Cw if Cmin == None else min(Cmin, Cw)
	return

def valid_C2(node):
	global Cmin
	C2 = tree_dict[node]['score']
	Cw = 3 * C2 - tree_sum
	C3 = C2 - Cw
	if min_time[C2] != max_time[C2]:
		Cmin = Cw if Cmin == None else min(Cmin, Cw)
	elif C3 in max_time.keys() and (tree_dict[node]['in'] > tree_dict[max_node[C3]]['in'] or tree_dict[node]['out'] < tree_dict[max_node[C3]]['in']):
		Cmin = Cw if Cmin == None else min(Cmin, Cw)
	elif C3 in min_time.keys() and (tree_dict[node]['in'] > tree_dict[min_node[C3]]['in'] or tree_dict[node]['out'] < tree_dict[min_node[C3]]['in']):
		Cmin = Cw if Cmin == None else min(Cmin, Cw)
	elif C2 + C3 in min_time.keys():
		Cmin = Cw if Cmin == None else min(Cmin, Cw)
	elif 2 * C2 in min_time.keys():
		Cmin = Cw if Cmin == None else min(Cmin, Cw)
	return

def main():
	N = int(input())
	global coins_list, node_dict, tree_dict, min_time, max_time, min_node, max_node, ticker, Cmin, tree_sum
	node_dict = {i: [] for i in range(1, N + 1)}
	tree_dict = {i: {'score': 0, 'in': 0, 'out': 0} for i in range(1, N + 1)}
	(min_time, max_time, min_node, max_node) = ({}, {}, {}, {})
	(ticker, tree_sum) = (0, 0)
	Cmin = None
	coins_list = [0] + [x for x in list(map(int, input().split()))]
	tree_sum = sum(coins_list)
	for _ in range(1, N):
		(x, y) = map(int, input().split())
		node_dict[x].append(y)
		node_dict[y].append(x)
	depth_first_traversal(1, 0)
	for node in range(1, N + 1):
		if tree_dict[node]['score'] not in min_time.keys():
			min_time[tree_dict[node]['score']] = tree_dict[node]['in']
			min_node[tree_dict[node]['score']] = node
			max_time[tree_dict[node]['score']] = tree_dict[node]['in']
			max_node[tree_dict[node]['score']] = node
		elif tree_dict[node]['in'] > min_time[tree_dict[node]['score']]:
			max_time[tree_dict[node]['score']] = tree_dict[node]['in']
			max_time[tree_dict[node]['score']] = node
		else:
			min_time[tree_dict[node]['score']] = tree_dict[node]['in']
			min_time[tree_dict[node]['score']] = node
	if tree_sum % 2 == 0 and tree_sum // 2 in min_time.keys():
		Cmin = tree_sum // 2
	for node in range(1, N + 1):
		if tree_dict[node]['score'] <= tree_sum // 3:
			valid_C3(node)
		elif tree_dict[node]['score'] <= tree_sum // 2:
			valid_C2(node)
	if Cmin == None:
		print(-1)
	else:
		print(Cmin)
	return
T = int(input())
for _ in range(T):
	main()


import math
from collections import defaultdict
from collections import deque
from copy import deepcopy
from time import time

def balancedForest(c, edges):
	t0 = time()
	if p1:
		print('=' * 40, t0)
	if edges == []:
		return -1
	n = len(c) + 1
	graph = defaultdict(list)
	root_max = 0
	root_node = None
	for (n1, n2) in edges:
		graph[n1].append(n2)
		if len(graph[n1]) > root_max:
			root_max = len(graph[n1])
			root_node = n1
		graph[n2].append(n1)
		if len(graph[n2]) > root_max:
			root_max = len(graph[n2])
			root_node = n2
	t1 = time()
	if p3:
		print('build a graph', round(t1 - t0, 2))
	parent = [None] * n
	visited = [None] * n
	visited[root_node] = 0
	S = deque([root_node])
	while len(S) > 0:
		cur = S.popleft()
		visited_cur = visited[cur]
		for node in graph[cur]:
			if visited[node] != None:
				continue
			S.append(node)
			visited[node] = visited_cur + 1
			parent[node] = cur
	t2 = time()
	if p3:
		print('BFS costs for root_node', round(t2 - t1, 2))
	sums = [None]
	sums.extend(c)
	for (node, level) in sorted([(i, visited[i]) for i in range(n) if visited[i] != None], key=lambda x: x[1], reverse=True):
		if parent[node] != None:
			sums[parent[node]] += sums[node]
	t3 = time()
	if p3:
		print('build a tree', round(t3 - t2, 2))
	root_sum = sums[root_node]
	lim1 = math.ceil(root_sum / 3)
	lim2 = root_sum // 2
	if p2:
		print('lim1,lim2=', lim1, lim2)
	S1 = [i for i in range(n) if i != root_node and sums[i] != None and (lim1 <= sums[i] <= lim2)]
	if p2:
		print('S1=', S1)
	t4 = time()
	if p3:
		print('brute force First Node list', round(t4 - t3, 2))
	res = []
	min_add_val = None
	for s1 in S1:
		val1 = sums[s1]
		if p2:
			print('sub1[', s1, ']=', val1, 'Tree=', root_sum - val1)
		if root_sum == val1 * 2:
			res.append(('s3,4=', s1, s1, 'val1,2,3', root_sum - val1, val1, val1))
			if min_add_val == None or min_add_val > val1:
				min_add_val = val1
			continue
		S2 = [i for i in range(n) if i not in (root_node, s1) and sums[i] != None and (sums[i] in (root_sum - val1 * 2, val1, val1 * 2, root_sum - val1))]
		if p2:
			print('S2=', S2)
		for s2 in S2:
			cur = parent[s2]
			while cur != None and cur != s1:
				cur = parent[cur]
			val2 = sums[s2]
			if p2:
				print('sub2[', s2, ']=', val2, 'Cur=', cur)
			if cur != s1 and val2 in (root_sum - val1 * 2, val1):
				res.append(('s1,2=', s1, s2, 'val1,2,3', val1, val2, root_sum - val1 - val2))
			elif cur == s1 and val2 in (val1 * 2, root_sum - val1):
				res.append(('s1,2=', s1, s2, 'val1,2,3', val1, val2, root_sum - val2))
			if min_add_val == None or min_add_val > 3 * val1 - root_sum:
				min_add_val = 3 * val1 - root_sum
	t5 = time()
	if p3:
		print('brute force Second Node list', round(t5 - t4, 2))
	S3 = [i for i in range(n) if i != root_node and sums[i] != None and (lim1 <= root_sum - sums[i] <= lim2)]
	if p2:
		print('S3=', S3)
	for s3 in S3:
		val1 = sums[s3]
		if p2:
			print('sub3[', s3, ']=', val1, 'Tree=', root_sum - val1)
		S4 = [i for i in range(n) if i not in (root_node, s3) and sums[i] != None and (sums[i] == val1 * 2 - root_sum)]
		if p2:
			print('S4=', S4)
		for s4 in S4:
			cur = parent[s4]
			while cur != None and cur != s3:
				cur = parent[cur]
			val2 = sums[s4]
			if p2:
				print('sub4[', s4, ']=', val2)
			if cur == s3 and val2 == 2 * val1 - root_sum:
				res.append(('s3,4=', s3, s4, 'val1,2,3', root_sum - val1, root_sum - val1 - val2, val2))
				if min_add_val == None or min_add_val > val1 - val2 * 2:
					min_add_val = val1 - val2 * 2
	t6 = time()
	if p3:
		print('brute force Third Node list', round(t6 - t5, 2))
	if p1:
		print('-' * 40, round(time() - t0, 2))
	if p1:
		print('res=', str(res)[:100])
	if p1:
		print('sums=', str(sums)[:100])
	if p1:
		print('visited=', str(visited)[:100])
	if p1:
		print('parent=', str(parent)[:100])
	if p1:
		print('graph=', str(str(graph)[27:-1])[:100])
	if p1:
		print('root_node', root_node, 'root_max=', root_max, 'root_sum=', root_sum, 'edge_count', len(edges))
	if p2:
		print('c=', c[:100], 'edges=', edges[:100])
	return -1 if min_add_val == None else min_add_val
p1 = 0
p2 = 0
p3 = 0
q = int(input())
for q_itr in range(q):
	n = int(input())
	c = list(map(int, input().rstrip().split()))
	edges = []
	for _ in range(n - 1):
		edges.append(list(map(int, input().rstrip().split())))
	result = balancedForest(c, edges)
	print(result)


import math
import os
import random
import re
import sys

def second_cut(u):
	global sumTree, mark2, cutId, sumCut, res, adj
	mark2[u] = True
	sum = c[u]
	for v in adj[u]:
		if v != cutId and mark2[v] == False:
			sum += second_cut(v)
	if sum == sumCut:
		res = min(res, sum - (sumTree - 2 * sumCut))
	if sumTree - sumCut - sum == sumCut:
		res = min(res, sumCut - sum)
	return sum

def first_cut(u):
	global sumTree, upper_bound, lower_bound, mark1, mark2, cutId, sumCut, adj, res
	mark1[u] = True
	sum = c[u]
	for v in adj[u]:
		if mark1[v] == False:
			sum += first_cut(v)
	if sum <= upper_bound and sum >= lower_bound:
		mark2 = [False for i in range(n)]
		if sum < sumTree - sum:
			cutId = u
			sumCut = sum
			second_cut(0)
		elif sum > sumTree - sum:
			cutId = 0
			sumCut = sumTree - sum
			second_cut(u)
		else:
			res = min(res, sum)
	return sum

def balancedForest(c, edges):
	n = len(c)
	global adj
	adj = []
	for i in range(n):
		adj.append([])
	for edge in edges:
		adj[edge[0] - 1].append(edge[1] - 1)
		adj[edge[1] - 1].append(edge[0] - 1)
	global sumTree
	sumTree = 0
	for i in range(n):
		sumTree += c[i]
	global upper_bound, lower_bound, result
	upper_bound = 2 * sumTree / 3
	lower_bound = sumTree / 3
	global mark1, mark2, cutId, res
	mark1 = [False for i in range(n)]
	mark2 = [False for i in range(n)]
	res = 12345678999999999
	first_cut(0)
	if res == 12345678999999999:
		return -1
	else:
		return res
q = int(input())
for q_itr in range(q):
	n = int(input())
	c = list(map(int, input().rstrip().split()))
	edges = []
	for _ in range(n - 1):
		edges.append(list(map(int, input().rstrip().split())))
	result = balancedForest(c, edges)
	print(result)


import math
import os
import random
import re
import sys

class Tree:

	def __init__(self, val, weight, children):
		self.val = val
		self.weight = weight
		self.children = children
		self.down = self.weight + sum((child.down for child in children))

	def walk(self):
		yield self
		for child in self.children:
			yield from child.walk()

def assignancestors(tree, prefix=[]):
	tree.ancestors = prefix[:]
	prefix.append(tree.val)
	for child in tree.children:
		assignancestors(child, prefix)
	prefix.pop()

def adjacencygraph(edges):
	graph = {}
	for [a, b] in edges:
		graph.setdefault(a, [])
		graph.setdefault(b, [])
		graph[a].append(b)
		graph[b].append(a)
	return graph

def maketree(graph, weights, root, parent):
	childrennames = [childname for childname in graph[root] if childname != parent]
	children = [maketree(graph, weights, childname, root) for childname in childrennames]
	return Tree(root, weights[root], children)
global directory

def hasrelation(val1, val2, relation):
	global directory
	(node1, node2) = (directory[val1], directory[val2])
	if relation == 'disjoint':
		return val1 not in node2.ancestors and val2 not in node1.ancestors
	elif relation == 'childof':
		return val2 in node1.ancestors
	elif relation == 'parentof':
		return val1 in node2.ancestors

def hasunique(coll1, index1, coll2, index2, relation):
	if index1 not in coll1 or index2 not in coll2:
		return False
	else:
		for val1 in coll1[index1]:
			for val2 in coll2[index2]:
				if val1 != val2 and hasrelation(val1, val2, relation):
					return True
		return False

def balancedForest(c, edges):
	if edges == []:
		return -1
	graph = adjacencygraph(edges)
	weights = {index + 1: weight for (index, weight) in enumerate(c)}
	tree = maketree(graph, weights, 1, None)
	(downs, ups) = ({}, {})
	sumall = tree.down
	global directory
	directory = {}
	for node in tree.walk():
		downs.setdefault(node.down, [])
		downs[node.down].append(node.val)
		ups.setdefault(sumall - node.down, [])
		ups[sumall - node.down].append(node.val)
		directory[node.val] = node
	assignancestors(tree)
	minval = math.inf
	for value in downs:
		if value * 3 >= sumall:
			if hasunique(downs, value, downs, value, 'disjoint'):
				minval = min(minval, value)
			if hasunique(downs, value, downs, sumall - 2 * value, 'disjoint'):
				minval = min(minval, value)
			if hasunique(downs, value, ups, value, 'childof'):
				minval = min(minval, value)
			if hasunique(downs, value, downs, 2 * value, 'childof'):
				minval = min(minval, value)
	for value in ups:
		if value * 3 >= sumall:
			if hasunique(ups, value, downs, sumall - 2 * value, 'parentof'):
				minval = min(minval, value)
	return -1 if minval == math.inf else minval * 3 - sumall

def main():
	q = int(input())
	for q_itr in range(q):
		n = int(input())
		c = list(map(int, input().rstrip().split()))
		edges = []
		for _ in range(n - 1):
			edges.append(list(map(int, input().rstrip().split())))
		result = balancedForest(c, edges)
		print(result)
main()


from random import randrange
import sys
sys.setrecursionlimit(10 ** 5)

def r():
	return list(map(int, input().split()))

def bin_search(arr, pred, lo=0):
	hi = len(arr)
	while lo < hi:
		mid = (lo + hi) // 2
		if pred(arr[mid]):
			hi = mid
		else:
			lo = mid + 1
	return lo if lo < len(arr) else None

class UndirectedGraph(object):

	def __init__(self, size):
		self.size = size
		self.M = 0
		self.edges = [set([]) for _ in range(self.size)]

	def add_edge(self, u, v):
		if v not in self.edges[u]:
			self.edges[u].add(v)
			self.edges[v].add(u)
			self.M += 1

	def neighbors(self, u):
		for v in self.edges[u]:
			yield v

class WeightedTree(UndirectedGraph):

	def __init__(self, size, weights):
		super().__init__(size)
		self.weights = weights
		self.labels = [None] * self.size
		self.cum_weights = [None] * self.size
		self.inverted = [False] * self.size
		self.nextnode = 0
		self.num_children = [None] * self.size
		self.root = 0

	def initialize(self):
		self.set_labels(self.root)
		self.sorted_nodes = sorted(list(range(self.size)), key=lambda x: self.cum_weights[x])

	def set_labels(self, root):
		self.dfs(root, set([]))
		self.total_weight = self.cum_weights[self.root]
		for (i, cw) in enumerate(self.cum_weights):
			if cw > self.total_weight - cw:
				self.cum_weights[i] = self.total_weight - cw
				self.inverted[i] = True

	def dfs(self, u, visited):
		visited.add(u)
		self.labels[u] = self.nextnode
		self.nextnode += 1
		self.cum_weights[u] = self.weights[u]
		self.num_children[u] = 0
		for v in self.neighbors(u):
			if v not in visited:
				(cw, nchildren) = self.dfs(v, visited)
				self.cum_weights[u] += cw
				self.num_children[u] += nchildren + 1
		return (self.cum_weights[u], self.num_children[u])

	def solve(self):
		tw = self.total_weight
		first_idx = bin_search(self.sorted_nodes, lambda u: self.cum_weights[u] >= (tw + 2) // 3)
		if first_idx is None:
			return None
		while first_idx < self.size:
			first = self.sorted_nodes[first_idx]
			first_cw = self.cum_weights[first]
			label1 = self.labels[first]
			last_child_label = label1 + self.num_children[first]
			for target_w in (tw - first_cw * 2, first_cw):
				second_idx = bin_search(self.sorted_nodes, lambda u: self.cum_weights[u] >= target_w)
				if second_idx is not None:
					while second_idx < self.size and self.cum_weights[self.sorted_nodes[second_idx]] == target_w:
						second = self.sorted_nodes[second_idx]
						is_child = label1 < self.labels[second] <= last_child_label
						is_child = is_child if not self.inverted[first] else not is_child
						if not is_child and self.labels[second] != label1:
							return first_cw * 3 - tw
						second_idx += 1
			first_idx += 1
		if 2 * first_cw == tw:
			return first_cw
		return None

def read_input():
	n = int(input())
	weights = r()
	G = WeightedTree(n, weights)
	for _ in range(n - 1):
		(u, v) = r()
		u -= 1
		v -= 1
		G.add_edge(u, v)
	G.initialize()
	return G

def main():
	q = int(input())
	for _ in range(q):
		G = read_input()
		ans = G.solve()
		print(ans if ans is not None else -1)
main()


import random
import time
from collections import defaultdict

class Node(object):
	__slots__ = ('value', 'children')

	def __init__(self, value):
		self.value = value
		self.children = []

	def __repr__(self):
		return 'N({})'.format(self.value)

def build_tree(c, edges):
	graph = [Node(value) for value in c]
	for (l, r) in edges:
		graph[l - 1].children.append(graph[r - 1])
		graph[r - 1].children.append(graph[l - 1])

	def walk(cur):
		r = Node(cur.value)
		visited.add(cur)
		for next in cur.children:
			if next not in visited:
				r.children.append(walk(next))
		return r
	visited = set()
	return walk(graph[0])

def collect_cuts(tree):
	cuts = defaultdict(set)

	def walk(cur):
		S = cur.value
		for child in cur.children:
			S += walk(child)
		cuts[S].add(cur)
		return S
	total_sum = walk(tree)
	return (cuts, total_sum)

def balanced_forest(c, edges):
	tree = build_tree(c, edges)
	(cuts, total_sum) = collect_cuts(tree)
	best_answer = None

	def check_new_answer(new_answer):
		nonlocal best_answer
		if best_answer is None or best_answer > new_answer:
			best_answer = new_answer

	def walk(cur):
		nonlocal best_answer
		cur_children = {cur}
		cur_sum = cur.value
		for child in cur.children:
			(child_set, child_sum) = walk(child)
			cur_sum += child_sum
			if len(cur_children) < len(child_set):
				(cur_children, child_set) = (child_set, cur_children)
			cur_children.update(child_set)
		other_sum = total_sum - cur_sum

		def can_cut_from_self(what):
			for node in cuts[what]:
				if node in cur_children:
					return True

		def can_cut_from_other(what):
			for node in cuts[what]:
				if node not in cur_children:
					return True
		X = cur_sum
		Y = other_sum - cur_sum
		if 0 <= Y <= X:
			if can_cut_from_other(Y):
				check_new_answer(X - Y)
			if can_cut_from_other(X):
				check_new_answer(X - Y)
		X = cur_sum // 2
		Y = other_sum
		if 0 <= Y <= X and X + X == cur_sum:
			if can_cut_from_self(X):
				check_new_answer(X - Y)
		X = other_sum
		Y = cur_sum - X
		if 0 <= Y <= X:
			if can_cut_from_self(X):
				check_new_answer(X - Y)
			if can_cut_from_self(Y):
				check_new_answer(X - Y)
		return (cur_children, cur_sum)
	walk(tree)
	return best_answer if best_answer is not None else -1

def add_edge(A, B):
	A.children.append(B)
	B.children.append(A)

def remove_edge(A, B):
	A.children.remove(B)
	B.children.remove(A)

def calc_sum(start):
	visited = set()

	def walk(cur):
		r = cur.value
		visited.add(cur)
		for next in cur.children:
			if next not in visited:
				r += walk(next)
		return r
	total = walk(start)
	return total

def balanced_forest_slow(c, edges):
	nodes = [Node(value) for value in c]
	edges = [(x - 1, y - 1) for (x, y) in edges]
	for (x, y) in edges:
		add_edge(nodes[x], nodes[y])
	total_sum = calc_sum(nodes[0])
	best_answer = None

	def check_best_answer(new_val):
		nonlocal best_answer
		if best_answer is None or best_answer > new_val:
			best_answer = new_val
	for (x, y) in edges:
		A = nodes[x]
		B = nodes[y]
		remove_edge(A, B)
		S = calc_sum(A)
		if 2 * S == total_sum:
			check_best_answer(S)
		add_edge(A, B)
	for (edge_id, (x, y)) in enumerate(edges):
		A = nodes[x]
		B = nodes[y]
		remove_edge(A, B)
		for (xx, yy) in edges[edge_id + 1:]:
			C = nodes[xx]
			D = nodes[yy]
			remove_edge(C, D)
			Sa = calc_sum(A)
			Sb = calc_sum(B)
			Sc = total_sum - Sa - Sb
			if Sa < Sb:
				(Sa, Sc) = (Sc, Sa)
			elif Sa > Sb:
				(Sb, Sc) = (Sc, Sb)
			if Sa == Sb and Sa > Sc:
				check_best_answer(Sa - Sc)
			add_edge(C, D)
		add_edge(A, B)
	return best_answer or -1

def generate_tree(r, N, max_weight):
	C = [r.randint(1, max_weight) for _ in range(N)]
	edges = [(k + 1, r.randint(1, k)) for k in range(1, N)]
	return (C, edges)

def run_search():
	r = random.Random()
	N = 5
	count = 0
	last = 0
	while True:
		count += 1
		if time.time() > last + 1:
			last = time.time()
			print(count)
		(C, edges) = generate_tree(r, N, 100)
		expected = balanced_forest_slow(C, edges)
		actual = balanced_forest(C, edges)
		if expected != actual:
			print('Expected: {}'.format(expected))
			print('Actual: {}'.format(actual))
			print('Test case:')
			print(1)
			print(N)
			print(' '.join(map(str, C)))
			for (x, y) in edges:
				print(x, y)
			break

def run():
	q = int(input())
	for q_itr in range(q):
		n = int(input())
		c = list(map(int, input().rstrip().split()))
		edges = []
		for _ in range(n - 1):
			edges.append(list(map(int, input().rstrip().split())))
		result = balanced_forest(c, edges)
		print(result)
run()