There is an undirected tree where each vertex is numbered from $1$ to $n$, and each contains a data value.  The sum of a tree is the sum of all its nodes' data values.  If an edge is cut, two smaller trees are formed.  The difference between two trees is the absolute value of the difference in their sums.  

Given a tree, determine which edge to cut so that the resulting trees have a minimal difference between them, then return that difference.  

Example 

$data=[1,2,3,4,5,6]$ 

$edges=[(1,2),(1,3),(2,6),(3,4),(3,5)]$   

In this case, node numbers match their weights for convenience.  The graph is shown below.   

The values are calculated as follows:  

Edge    Tree 1  Tree 2  Absolute
Cut     Sum      Sum     Difference
1        8         13         5
2        9         12         3
3        6         15         9
4        4         17        13
5        5         16        11

The minimum absolute difference is $3$.

Note: The given tree is always rooted at vertex $1$.  

Function Description  

Complete the cutTheTree function in the editor below.    

cutTheTree has the following parameter(s):  

int data[n]: an array of integers that represent node values  
int edges[n-1][2]: an 2 dimensional array of integer pairs where each pair represents nodes connected by the edge  

Returns  

int: the minimum achievable absolute difference of tree sums  

Input Format

The first line contains an integer $n$, the number of vertices in the tree. 

The second line contains $n$ space-separated integers, where each integer $\mbox{u}$ denotes the $node[u]$ data value, $\textit{data}[u]$. 

Each of the $n-1$ subsequent lines contains two space-separated integers $\mbox{u}$ and $\boldsymbol{\nu}$ that describe edge $u\leftrightarrow v$ in tree $\boldsymbol{\boldsymbol{t}}$.        

Constraints

$3\leq n\leq10^5$  
$1\leq data[u]\leq1001$, where $1\leq u\leq n$.

Sample Input
STDIN                       Function
-----                       --------
6                           data[] size n = 6
100 200 100 500 100 600     data = [100, 200, 100, 500, 100, 600]
1 2                         edges = [[1, 2], [2, 3], [2, 5], [4, 5], [5, 6]]
2 3
2 5
4 5
5 6

Sample Output
400

Explanation

We can visualize the initial, uncut tree as:  

There are $n-1=5$ edges we can cut:

Edge $1\leftrightarrow2$ results in $d_{1\leftrightarrow2}=1500-100=1400$ 
Edge $2\leftrightarrow3$ results in $d_{2\leftrightarrow3}=1500-100=1400$
Edge $2\leftrightarrow5$ results in $d_{2\leftrightarrow5}=1200-400=800$ 
Edge $4\leftrightarrow5$ results in $d_{4\leftrightarrow5}=1100-500=600$
Edge $5\leftrightarrow6$ results in $d_{5\leftrightarrow6}=1000-600=400$

The minimum difference is $\textbf{400}$.

Source: hackerrank | Difficulty: MEDIUM
Tags: Complete search


Solutions:
from collections import deque

class Node(object):

	def __init__(self, index, value):
		self.index = index
		self.value = value
		self.children = set()
		self.parent = None
		self.value_of_subtree = 0
N = int(input())
node_at_index = [Node(index, value) for (index, value) in enumerate(map(int, input().split()))]
for (a, b) in (map(int, input().split()) for _ in range(N - 1)):
	node_at_index[a - 1].children.add(node_at_index[b - 1])
	node_at_index[b - 1].children.add(node_at_index[a - 1])
root = node_at_index[0]
ordered_nodes = [root]
q = deque([root])
while q:
	n = q.popleft()
	for c in n.children:
		c.children.remove(n)
		c.parent = n
		q.append(c)
		ordered_nodes.append(c)
ordered_nodes.reverse()
for n in ordered_nodes:
	n.value_of_subtree = n.value + sum((c.value_of_subtree for c in n.children))
total = root.value_of_subtree
best = N * 2000
for n in ordered_nodes:
	for c in n.children:
		tree_a = c.value_of_subtree
		tree_b = total - tree_a
		dif = abs(tree_a - tree_b)
		if dif < best:
			best = dif
print(best)


n = int(input())
vals = list(map(int, input().split()))
t = sum(vals)
adjLi = [[] for i in range(n)]
for i in range(n - 1):
	(u, v) = map(int, input().split())
	adjLi[u - 1].append(v - 1)
	adjLi[v - 1].append(u - 1)
totVal = [0] * n
explored = []
waiting = {i for i in range(n) if len(adjLi[i]) == 1}
while len(waiting):
	for i in waiting:
		totVal[i] += vals[i]
		if len(adjLi[i]):
			adjLi[adjLi[i][0]].remove(i)
			totVal[adjLi[i][0]] += totVal[i]
	waiting = {adjLi[i][0] for i in waiting if len(adjLi[i]) and len(adjLi[adjLi[i][0]]) == 1}
rt = abs(t - 2 * totVal[0])
for i in range(1, n):
	k = abs(t - 2 * totVal[i])
	if k < rt:
		rt = k
print(rt)


import sys
sys.setrecursionlimit(200010)
n = int(input())
a = list(map(int, input().split()))
g = [[] for i in range(n)]
for i in range(n - 1):
	(v1, v2) = map(lambda s: int(s) - 1, input().split())
	g[v1].append(v2)
	g[v2].append(v1)

def compute_order():
	global order
	order = []
	global parent
	parent = [-1] * n
	stack = [0]
	while stack:
		v = stack.pop()
		order.append(v)
		for to in g[v]:
			if to != parent[v]:
				parent[to] = v
				stack.append(to)
	return order
sz = [0] * n
compute_order()
for v in reversed(order):
	sz[v] = a[v]
	for to in g[v]:
		if to != parent[v]:
			sz[v] += sz[to]
tot = sum(a)
print(min((abs(tot - 2 * x) for x in sz)))


import sys
from pprint import pprint
totalGraphValue = 0
vertexValues = []
vertexLinks = []
numberOfVertices = int(input())
vertexValues = list(map(float, input().rstrip().split(' ')))
for i in range(numberOfVertices):
	vertexLinks.append([])
	totalGraphValue += vertexValues[i]
inputLine = list(map(int, input().rstrip().split(' ')))
while inputLine:
	(valueA, valueB) = (inputLine[0] - 1, inputLine[1] - 1)
	vertexLinks[valueA].append(valueB)
	vertexLinks[valueB].append(valueA)
	try:
		inputLine = list(map(int, input().rstrip().split(' ')))
	except EOFError:
		break

def main():
	smallestEdgeDiffValue = sys.maxsize
	parentDict = dict()
	alreadyEvaluated = [False for i in range(numberOfVertices)]
	linkChildrenValues = [0 for i in range(numberOfVertices)]
	listToCheck = []
	listToCheck.append(0)
	while listToCheck:
		currentIndex = listToCheck.pop(0)
		alreadyEvaluated[currentIndex] = True
		if len(vertexLinks[currentIndex]) == 1:
			otherIndex = vertexLinks[currentIndex][0]
			edge = (min(currentIndex, otherIndex), max(currentIndex, otherIndex))
			diffValue = abs(totalGraphValue - vertexValues[currentIndex] * 2)
			linkChildrenValues[currentIndex] = vertexValues[currentIndex]
			smallestEdgeDiffValue = min(smallestEdgeDiffValue, diffValue)
			listToCheck.insert(0, otherIndex)
			if otherIndex != 0 and (not otherIndex in parentDict):
				parentDict[otherIndex] = currentIndex
		else:
			neighborsVisited = 0
			for otherIndex in vertexLinks[currentIndex]:
				if alreadyEvaluated[otherIndex]:
					neighborsVisited += 1
			if neighborsVisited == len(vertexLinks[currentIndex]):
				if currentIndex in parentDict:
					sumValueOfChildren = vertexValues[currentIndex]
					for otherIndex in vertexLinks[currentIndex]:
						sumValueOfChildren += linkChildrenValues[otherIndex]
					parentIndex = parentDict[currentIndex]
					edge = (min(currentIndex, parentIndex), max(currentIndex, parentIndex))
					diffValue = abs(totalGraphValue - sumValueOfChildren * 2)
					linkChildrenValues[currentIndex] = sumValueOfChildren
					smallestEdgeDiffValue = min(smallestEdgeDiffValue, diffValue)
					if linkChildrenValues[parentIndex]:
						return smallestEdgeDiffValue
					else:
						listToCheck.insert(0, parentIndex)
				else:
					return smallestEdgeDiffValue
			else:
				for otherIndex in vertexLinks[currentIndex]:
					if currentIndex in parentDict and parentDict[currentIndex] == otherIndex:
						continue
					if alreadyEvaluated[otherIndex]:
						continue
					else:
						if not otherIndex in parentDict:
							parentDict[otherIndex] = currentIndex
						listToCheck.insert(0, otherIndex)
						break
	return smallestEdgeDiffValue
x = main()
print(int(x))


n = int(input())
l = input().strip().split()
val = {}
kk = 1
S = 0
for i in l:
	val[kk] = int(i)
	S += int(i)
	kk += 1
adj = {}
deg = {}
for i in range(n - 1):
	s = input().strip().split()
	a = int(s[0])
	b = int(s[1])
	try:
		deg[a] += 1
		adj[a].append(b)
	except KeyError:
		deg[a] = 1
		adj[a] = [b]
	try:
		deg[b] += 1
		adj[b].append(a)
	except KeyError:
		deg[b] = 1
		adj[b] = [a]
deg1 = []
for key in deg.keys():
	if deg[key] == 1:
		deg1.append(key)
ans = S
while 1:
	v = deg1.pop(0)
	if deg[v] == 0:
		break
	ans = min(ans, abs(S - 2 * val[v]))
	u = adj[v][0]
	adj[u].remove(v)
	deg[u] -= 1
	val[u] += val[v]
	if deg[u] == 1:
		deg1.append(u)
print(ans)


N = int(input())
vertices = [int(c) for c in input().split()[:N]]
edges = [[] for _ in range(N)]
for _ in range(N - 1):
	(x, y) = input().split()
	edges[int(x) - 1].append(int(y) - 1)
	edges[int(y) - 1].append(int(x) - 1)
sums = [None] * N
pending = [None] * N
pending[0] = (None, 0)
pending_index = 0
while pending_index >= 0:
	(prev_index, index) = pending[pending_index]
	calculable = True
	s = vertices[index]
	for child_index in edges[index]:
		if child_index == prev_index:
			continue
		if sums[child_index] == None:
			pending_index += 1
			pending[pending_index] = (index, child_index)
			calculable = False
		else:
			s += sums[child_index]
	if calculable:
		sums[index] = s
		pending_index -= 1
s = sum(vertices)
ans = s
for i in range(N):
	d = abs(s - sums[i] * 2)
	if d < ans:
		ans = d
print(ans)


N = int(input())
Values = [int(x) for x in input().strip().split(' ')]
Goal = sum(Values)
Tree = [[] for i in range(N)]
for i in range(N - 1):
	(a, b) = [int(x) - 1 for x in input().strip().split(' ')]
	Tree[a].append(b)
	Tree[b].append(a)
(stack, weight) = ([0], [None] * N)
mindiff = Goal
while stack:
	a = stack.pop()
	if weight[a] == None:
		stack.append(a)
		for b in Tree[a]:
			if weight[b] == None:
				stack.append(b)
		weight[a] = 0
	else:
		weight[a] = Values[a]
		for b in Tree[a]:
			weight[a] += weight[b]
		if abs(weight[a] * 2 - Goal) < mindiff:
			mindiff = abs(weight[a] * 2 - Goal)
print(mindiff)


N = int(input())
weights = [int(w) for w in input().split()]
neighbors = [[] for _ in range(N)]
root = None
for _ in range(N - 1):
	(n1, n2) = map(int, input().split())
	neighbors[n1 - 1].append(n2 - 1)
	neighbors[n2 - 1].append(n1 - 1)
leaves = set((i for (i, n) in enumerate(neighbors) if len(n) == 1))
while leaves:
	i = leaves.pop()
	for n in neighbors[i]:
		weights[n] += weights[i]
		neighbors[n].remove(i)
		if len(neighbors[n]) == 1:
			leaves.add(n)
wt = weights[i]
print(min([abs(w * 2 - wt) for w in weights]))


import sys
import queue

def readInputs0():
	global n, lAdj, lCost
	n = int(input())
	lCost = list(map(int, input().split()))
	lAdj = [[] for _ in range(n)]
	for _ in range(n - 1):
		(a, b) = map(int, input().split())
		lAdj[a] += [b]
		lAdj[b] += [a]

def readInputs():
	global n, lAdj, lCost
	n = int(input())
	lCost = list(map(int, input().split()))
	lAdj = [[] for _ in range(n)]
	for _ in range(n - 1):
		(a, b) = map(int, input().split())
		lAdj[a - 1] += [b - 1]
		lAdj[b - 1] += [a - 1]

def DFexplo():
	global listFather, listChildren
	listFather = n * [-1]
	listChildren = [set() for _ in range(n)]
	lifo = [0]
	while len(lifo) > 0:
		node = lifo.pop()
		for child in lAdj[node]:
			if child != listFather[node]:
				listFather[child] = node
				listChildren[node] |= {child}
				lifo.append(child)

def BFexplo():
	global nodesBF
	nodesBF = []
	fifo = queue.deque()
	fifo.append(0)
	while len(fifo) > 0:
		node = fifo.pop()
		for child in listChildren[node]:
			fifo.append(child)
			nodesBF += [child]

def propagateTotalCostsToRoots():
	global totCostAsRoot
	totCostAsRoot = [v for v in lCost]
	for node in reversed(nodesBF):
		totCostAsRoot[listFather[node]] += totCostAsRoot[node]

def solve():
	totCost = totCostAsRoot[0]
	lifo = [0]
	minDiff = sys.maxsize
	while len(lifo) > 0:
		node = lifo.pop()
		for child in listChildren[node]:
			lifo.append(child)
			totCostChild = totCostAsRoot[child]
			diff = abs(totCost - totCostChild - totCostChild)
			minDiff = min(minDiff, diff)
	return minDiff
readInputs()
DFexplo()
BFexplo()
propagateTotalCostsToRoots()
print(solve())


n = int(input())
w = [0] + list(map(int, input().split()))
sw = [0] * (n + 1)
level = [0] * (n + 1)
g = dict(((v, []) for v in range(1, n + 1)))
edges = [list(map(int, input().split())) for _ in range(n - 1)]
for (x, y) in edges:
	g[x].append(y)
	g[y].append(x)
stack = [(1, 0, 0, False)]

def dfs():
	while stack:
		(v, f, l, visited) = stack.pop()
		if not visited:
			stack.append((v, f, l, True))
			for u in g[v]:
				if u == f:
					continue
				stack.append((u, v, l + 1, False))
		else:
			sw[v] = w[v] + sum([sw[u] for u in g[v] if u != f])
			level[v] = l
dfs()
total = sw[1]

def diff(x, y):
	if level[x] > level[y]:
		return diff(y, x)
	return abs(total - sw[y] - sw[y])
costs = [diff(x, y) for (x, y) in edges]
print(min(costs))


import collections

def collect_input():
	N = int(input())
	vs = [0] + [int(x) for x in input().split()]
	edges = dict()
	for i in range(N - 1):
		(f, t) = [int(x) for x in input().split()]
		edges[f] = edges.get(f, []) + [t]
		edges[t] = edges.get(t, []) + [f]
	return (vs, edges)

def tree_diff(tw1, tw2):
	return abs(tw1 - tw2)

def create_subtree_weights(vs, edges):
	subtree_weights = dict()
	dq = collections.deque()
	dq.append(1)
	while dq:
		node_f = dq.pop()
		if node_f in subtree_weights:
			continue
		defer = False
		total = vs[node_f]
		for node_t in edges[node_f]:
			if node_t not in subtree_weights:
				if not defer:
					dq.append(node_f)
				defer = True
				edges[node_t].remove(node_f)
				dq.append(node_t)
			else:
				total += subtree_weights[node_t]
		if defer:
			continue
		else:
			subtree_weights[node_f] = total
	return subtree_weights

def merge_lighter_children(root, root_subtree_weight, edges, subtree_weights):
	if len(edges[root]) < 2:
		return root_subtree_weight
	ewt = []
	for node_t in edges[root]:
		ewt.append([node_t, subtree_weights[node_t]])
	ewt = sorted(ewt, key=lambda x: x[1])[:-1]
	for (node_t, sub_weight) in ewt:
		root_subtree_weight += sub_weight
		edges[root].remove(node_t)
	return root_subtree_weight
(vs, edges) = collect_input()
subtree_weights = create_subtree_weights(vs, edges)
total_weight = sum(vs)
t1_weight = vs[1]
node = 1
best_td = total_weight
done = False
while not done:
	t1_weight = merge_lighter_children(node, t1_weight, edges, subtree_weights)
	t2_weight = total_weight - t1_weight
	td = tree_diff(t1_weight, t2_weight)
	best_td = min(best_td, td)
	if not edges[node]:
		break
	node = edges[node][0]
	t1_weight += vs[node]
print(best_td)


class Node(object):

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

	def __repr__(self, parent=None, level=0):
		ret = '\t' * level + repr(self.value) + '\n'
		for child in self.children:
			if child != parent:
				ret += child.__repr__(parent=self, level=level + 1)
		return ret
input()
nodes = [Node(int(el)) for el in input().split()]
for _ in range(len(nodes) - 1):
	(node1, node2) = sorted([int(el) - 1 for el in input().split()])
	nodes[node1].children.append(nodes[node2])
	nodes[node2].children.append(nodes[node1])
total = sum((node.value for node in nodes))
root = nodes[0]
queue = [root]
while queue:
	node = queue.pop(0)
	for child in node.children:
		child.children.remove(node)
	queue += node.children
stack = [root]
visited = set()
while stack:
	node = stack[-1]
	if not node.children or node.children[0] in visited:
		visited.add(node)
		node.value += sum((child.value for child in node.children))
		stack.pop()
	else:
		stack += node.children
queue = root.children
min_diff = 10000000000000000000000000000000000000000000000000000000000
while queue:
	node = queue.pop(0)
	min_diff = min(min_diff, abs(total - 2 * node.value))
	queue += node.children
print(min_diff)


def my_append(list_l, a, j):
	l = -1
	r = len(list_l)
	while r - l > 1:
		mid = (r + l) // 2
		if a[list_l[mid]] < a[j]:
			l = mid
		else:
			r = mid
	list_l.insert(r, j)
n = int(input())
a = [int(i) for i in input().strip().split()]
edge_list = []
for i in range(n):
	edge_list.append([])
list_v = [0] * n
for e in range(n - 1):
	(x, y) = [int(i) for i in input().strip().split()]
	list_v[x - 1] += 1
	list_v[y - 1] += 1
	edge_list[x - 1].append(y - 1)
	edge_list[y - 1].append(x - 1)
list_l = []
for i in range(n):
	if list_v[i] == 1:
		my_append(list_l, a, i)
for q in range(n - 2):
	cur_i = list_l.pop(0)
	cur_j = edge_list[cur_i].pop(0)
	edge_list[cur_j].remove(cur_i)
	a[cur_j] += a[cur_i]
	list_v[cur_j] -= 1
	if list_v[cur_j] == 1:
		my_append(list_l, a, cur_j)
print(abs(a[list_l[0]] - a[list_l[1]]))


def main():
	nvert = int(input())
	value = list(map(int, input().split()))
	child = [[] for _ in range(nvert)]
	for _ in range(1, nvert):
		(i, j) = [int(x) - 1 for x in input().split()]
		child[i].append(j)
		child[j].append(i)
	fixchild(None, 0, child)
	sumvalues = getsumvalues(child, value)
	print(min((abs(sumvalues[0] - 2 * sv) for sv in sumvalues)))

def fixchild(prev, root, child):
	stack = [(prev, root)]
	while stack:
		(prev, root) = stack.pop()
		child[root] = [node for node in child[root] if node != prev]
		stack += [(root, c) for c in child[root]]

def getsumvalues(child, value):
	ans = [None] * len(value)

	def svcomp(root):
		for node in child[root]:
			svcomp(node)
		ans[root] = value[root] + sum((ans[node] for node in child[root]))
	stack = [(0, False)]
	while stack:
		(root, ready) = stack.pop()
		if ready:
			ans[root] = value[root] + sum((ans[node] for node in child[root]))
		else:
			stack.append((root, True))
			stack += [(node, False) for node in child[root]]
	return ans
main()


from collections import deque
node_count = int(input())
nodes_cost = [int(i) for i in input().split()]
sum_cost = sum(nodes_cost)
nodes = [[i, nodes_cost[i], set()] for i in range(node_count)]
for _ in range(node_count - 1):
	(a, b) = [int(i) - 1 for i in input().split()]
	nodes[a][2].add(b)
	nodes[b][2].add(a)
min_diff = 10 ** 9
nodes_order = nodes[:]
nodes_order.sort(key=lambda a: len(a[2]))
queue = deque()
for node in nodes_order:
	if len(node[2]) > 1:
		break
	queue.append(node[0])
while len(queue) > 1:
	idx = queue.popleft()
	subtree_cost = nodes[idx][1]
	diff = abs(sum_cost - 2 * subtree_cost)
	if diff < min_diff:
		min_diff = diff
	if sum_cost - 2 * subtree_cost < 0:
		break
	jdx = nodes[idx][2].pop()
	nodes[jdx][2].remove(idx)
	if len(nodes[jdx][2]) == 1:
		queue.append(jdx)
	nodes[jdx][1] += nodes[idx][1]
print(min_diff)


from collections import defaultdict

class Node:

	def __init__(self, identifier, value, parent=None):
		self.__identifier = identifier
		self.__value = value
		self.__parent = parent
		self.__children = list()
		self.__neighbors = set()
		self.__accumulated_weight = 0

	def set_parent(self, parent):
		self.__parent = parent

	def identifier(self):
		return self.__identifier

	def value(self):
		return self.__value

	def add_child(self, child):
		self.__children.append(child)
		child.__parent = self

	def add_edge(self, node):
		self.__neighbors.add(node)

	def parent(self):
		return self.__parent

	def children(self):
		return self.__children

	def neighbors(self):
		return self.__neighbors

	def accumulated_weight(self):
		if self.__accumulated_weight == 0:
			accumulated_weight = self.__value
			for child in self.__children:
				accumulated_weight += child.accumulated_weight()
			self.__accumulated_weight = accumulated_weight
			return self.__accumulated_weight
		else:
			return self.__accumulated_weight

class Tree:

	def __init__(self):
		self.__nodes = dict()
		self.__depth = defaultdict(set)

	def set_root(self, root):
		self.__root = root

	def root(self):
		return self.__root

	def all_nodes(self):
		return self.__nodes

	def nodes(self, identifier):
		return self.__nodes[identifier]

	def add_node(self, identifier, node):
		self.__nodes[identifier] = node

	def add_edge(self, node_a_id, node_b_id):
		node_a = self.nodes(node_a_id)
		node_b = self.nodes(node_b_id)
		node_a.add_edge(node_b)
		node_b.add_edge(node_a)

	def depth(self):
		return self.__depth

	def format(self):
		nodes = list()
		nodes.append(self.root())
		depth = -1
		for node in nodes:
			depth += 1
			self.__depth[depth].add(node)
			while len(node.neighbors()) > 0:
				neighbor = node.neighbors().pop()
				if neighbor == node.parent():
					continue
				else:
					node.add_child(neighbor)
					nodes.append(neighbor)
n = int(input())
values = list(map(int, input().split()))
tree = Tree()
for idx in range(1, n + 1):
	node = Node(idx, values[idx - 1])
	tree.add_node(idx, node)
for _ in range(n - 1):
	(node_a_id, node_b_id) = map(int, input().split())
	tree.add_edge(node_a_id, node_b_id)
for identifier in tree.all_nodes():
	node = tree.nodes(identifier)
	if len(node.neighbors()) == 1:
		tree.set_root(node)
		break
tree.format()
rev_keys = list(tree.depth().keys())
rev_keys.reverse()
for level in rev_keys:
	tree.depth()[level].pop().accumulated_weight()
min_diff = float('inf')
root = tree.root()
root_accumulated_weight = root.accumulated_weight()
for identifier in tree.all_nodes():
	node = tree.nodes(identifier)
	if node == root:
		continue
	node_accumulated_weight = node.accumulated_weight()
	remain_weight = root_accumulated_weight - node_accumulated_weight
	diff = abs(remain_weight - node_accumulated_weight)
	if diff < min_diff:
		min_diff = diff
print(min_diff)


import sys

def post_order_traverse(T, root, func, *args):
	stack = []
	stack.append((root, 0))
	while len(stack) > 0:
		(node, status) = stack.pop()
		if status == len(T[node]):
			func(node, args)
		else:
			stack.append((node, status + 1))
			stack.append((T[node][status], 0))

def calc_node_total_value(node, args):
	(T, total_value, node_value) = args
	total_value[node] = 0
	for child in T[node]:
		total_value[node] += total_value[child]
	total_value[node] += node_value[node]

def build_tree(N, edges):
	T = []
	for _ in range(N + 1):
		T.append([])
	stack = [1]
	visited = [False] * (N + 1)
	while len(stack) > 0:
		node = stack.pop()
		visited[node] = True
		for child in edges[node]:
			if visited[child]:
				continue
			T[node].append(child)
			stack.append(child)
	return (T, 1)

def calc_all_total_value(T, N, node_value, edges, root):
	total_value = []
	for _ in range(N + 1):
		total_value.append([])
	post_order_traverse(T, root, calc_node_total_value, T, total_value, node_value)
	return total_value

def calc_diff_in_edges(node, args):
	(total_value, root, diff) = args
	diff[node] = abs(total_value[root] - total_value[node] * 2)

def calc_mini_diff(T, N, total_value, root):
	diff = [0] * (N + 1)
	post_order_traverse(T, root, calc_diff_in_edges, total_value, root, diff)
	return min(diff[1:])
N = int(sys.stdin.readline())
node_value = [int(x) for x in sys.stdin.readline().split()]
node_value.insert(0, 0)
edges = {}
for i in range(N + 1):
	edges[i] = []
for _ in range(N - 1):
	(x, y) = [int(x) for x in sys.stdin.readline().split()]
	edges[x].append(y)
	edges[y].append(x)
(T, root) = build_tree(N, edges)
total_value = calc_all_total_value(T, N, node_value, edges, root)
mini_diff = calc_mini_diff(T, N, total_value, root)
print(mini_diff)


def subtreeVals(g, node_vals, subtree_vals, root):
	stack = [root]
	while stack:
		v = stack[-1]
		v_done = True
		subtree_vals[v] = node_vals[v]
		if v in g:
			for u in g[v]:
				if subtree_vals[u] is None:
					stack.append(u)
					v_done = False
				elif u != v and subtree_vals[u] != -1:
					subtree_vals[v] += subtree_vals[u]
		if v_done:
			stack.pop()
		else:
			subtree_vals[v] = -1
n = int(input())
node_vals = [int(i) for i in input().split()]
g = {}
for _ in range(n - 1):
	(u, v) = [int(i) - 1 for i in input().split()]
	if u in g:
		g[u].add(v)
	else:
		g[u] = set([v])
	if v in g:
		g[v].add(u)
	else:
		g[v] = set([u])
subtree_vals = [None for i in range(n)]
subtreeVals(g, node_vals, subtree_vals, 0)
tree_diffs = [abs(subtree_vals[0] - 2 * subtree_vals[i]) for i in range(1, n)]
print(min(tree_diffs))


import sys

def cut_the_tree():
	nodes = int(input())
	graph = {}
	for (i, v) in enumerate(input().split()):
		graph[i + 1] = [int(v), 0, []]
	for n in range(nodes - 1):
		(x, y) = map(int, input().split())
		graph.get(x)[2].append(y)
		graph.get(y)[2].append(x)
	make_tree_iterative(graph, 1)
	full_tree_value = calculate_subtree_value_iterative(graph, 1)
	min_diff = sys.maxsize
	for (k, v) in graph.items():
		diff = abs(full_tree_value - 2 * v[1])
		if diff < min_diff:
			min_diff = diff
			if min_diff == 0:
				break
	print(min_diff)

def make_tree(graph, node_id):
	if node_id not in graph.keys():
		return
	else:
		for n in graph[node_id][2]:
			graph[n][2].remove(node_id)
			make_tree(graph, n)

def make_tree_iterative(graph, root):
	stack = [root]
	while len(stack) > 0:
		node_id = stack.pop()
		for child in graph[node_id][2]:
			graph[child][2].remove(node_id)
			stack.append(child)

def calculate_subtree_value(tree, node_id):
	if node_id not in tree.keys():
		return 0
	else:
		node = tree[node_id]
		tree_value = node[0]
		for n in node[2]:
			tree_value += calculate_subtree_value(tree, n)
		node[1] = tree_value
		return tree_value

def calculate_subtree_value_iterative(tree, root):
	stack = [root]
	traversing_stack = [root]
	while len(traversing_stack) > 0:
		node_id = traversing_stack.pop()
		for child in tree[node_id][2]:
			stack.append(child)
			traversing_stack.append(child)
	while len(stack) > 0:
		node = tree[stack.pop()]
		tree_value = node[0]
		for child in node[2]:
			tree_value += tree[child][1]
		node[1] = tree_value
	return tree[root][1]
cut_the_tree()


def dfs(l, w):
	stack = [1]
	tw = sum(w)
	v = set()
	ord = []
	p = [0] * len(l)
	while stack:
		curr = stack.pop()
		v.add(curr)
		ord.append(curr)
		for i in l[curr]:
			if i not in v:
				stack.append(i)
				p[i] = curr
	ord = list(reversed(ord))
	for i in ord:
		w[p[i]] += w[i]
	mw = tw
	for el in l:
		for i in el:
			x = abs(tw - 2 * w[i])
			if mw > x:
				mw = x
	print(mw)

def main():
	n = int(input())
	l = []
	for i in range(n + 1):
		l.append([])
	w = [0]
	w.extend(list(map(int, input().split())))
	tw = sum(w)
	for i in range(n - 1):
		(a, b) = input().split()
		(a, b) = (int(a), int(b))
		l[a].append(b)
		l[b].append(a)
	dfs(l, w)
main()


from collections import defaultdict

def cut_the_tree(nodes, edges):
	visited = set()
	stack = [0]
	order = defaultdict(set)
	DAG = []
	while stack:
		curr = stack.pop()
		visited.add(curr)
		DAG.append(curr)
		for edge in edges[curr]:
			if edge not in visited and edge not in stack:
				order[curr].add(edge)
				stack.append(edge)
	subtree = [0 for _ in range(len(nodes))]
	for node in reversed(DAG):
		subtree[node] = sum([subtree[x] for x in order[node]]) + nodes[node]
	total = sum(nodes)
	min_val = None
	for val in subtree:
		if min_val == None:
			min_val = abs(total - 2 * val)
		else:
			min_val = min(abs(total - 2 * val), min_val)
	return min_val
N = int(input())
nodes = list(map(int, input().split(' ')))
edges = defaultdict(set)
for _ in range(N - 1):
	(parent, child) = map(int, input().split(' '))
	edges[parent - 1].add(child - 1)
	edges[child - 1].add(parent - 1)
print(cut_the_tree(nodes, edges))


N = int(input())
node_val = input().split()
for i in range(N):
	node_val[i] = int(node_val[i])
sum_val = sum(node_val)
edge_set = [[] for i in range(N)]
for i in range(N - 1):
	edge_in = input().split()
	edge_in[0] = int(edge_in[0]) - 1
	edge_in[1] = int(edge_in[1]) - 1
	edge_set[edge_in[0]].append(edge_in[1])
	edge_set[edge_in[1]].append(edge_in[0])
node_sum_val = [0 for i in range(N)]
node_sum_val[0] = sum_val
node_visited = [0 for k in range(N)]
L = [[0]]
level = 0
node_left = N - 1
node_visited[0] = 1
while node_left > 0:
	L.append([])
	for i in range(len(L[level])):
		current_node = L[level][i]
		for j in range(len(edge_set[current_node])):
			if node_visited[edge_set[current_node][j]] == 0:
				L[level + 1].append(edge_set[current_node][j])
				node_visited[edge_set[current_node][j]] = 1
				node_left -= 1
	level += 1
min_diff = sum_val
for i in range(level, -1, -1):
	for j in range(len(L[i])):
		current_node = L[i][j]
		node_sum_val[L[i][j]] = node_val[L[i][j]]
		for k in range(len(edge_set[current_node])):
			if i < level and edge_set[current_node][k] in L[i + 1]:
				node_sum_val[current_node] += node_sum_val[edge_set[current_node][k]]
		if min_diff > abs(sum_val - 2 * node_sum_val[current_node]):
			min_diff = abs(sum_val - 2 * node_sum_val[current_node])
print(min_diff)


import sys
N = int(sys.stdin.readline())
vertices_weights = [int(X) for X in sys.stdin.readline().split()]
subtrees_weights = vertices_weights[:]
G = {i: set() for i in range(N)}
for edge in range(N - 1):
	[v1, v2] = [int(X) - 1 for X in sys.stdin.readline().split()]
	G[v1].add(v2)
	G[v2].add(v1)
for vertex in G:
	if len(G[vertex]) <= 2:
		root = vertex
		break
visited = set()
visiting = [root]
while visiting:
	parent = visiting[-1]
	visited.add(parent)
	childs = G[parent] - visited
	if childs:
		for child in childs:
			G[child].remove(parent)
			visiting.append(child)
	else:
		parent = visiting.pop()
		subtrees_weights[parent] += sum([subtrees_weights[i] for i in G[parent]])
min_diff = sys.maxsize
visited = set()
visiting = [(root, 0)]
while visiting:
	(parent, path_weight) = visiting[-1]
	visited.add(parent)
	childs = G[parent] - visited
	if childs:
		for child in childs:
			lhs = path_weight + vertices_weights[parent] + sum([subtrees_weights[i] for i in childs - {child}])
			rhs = subtrees_weights[child]
			min_diff = min(min_diff, abs(lhs - rhs))
			visiting.append((child, lhs))
	else:
		(_parent, _path_weight) = visiting.pop()
print(min_diff)


import sys
n = int(input())
c = list(map(int, input().split()))
d = dict()
for line in sys.stdin:
	(u, v) = map(int, line.split())
	if u in d:
		d[u].append(v)
	else:
		d[u] = [v]
	if v in d:
		d[v].append(u)
	else:
		d[v] = [u]

def dfs(u, vis):
	vis.add(u)
	if u not in d:
		return c[u - 1]
	elif u in w:
		return w[u]
	t = c[u - 1]
	for v in d[u]:
		if v not in vis:
			vis_c = type(vis)(vis)
			t += dfs(v, vis_c)
	w[u] = t
	return t

def dfsV2(u):
	s = [u]
	vis = set()
	while s:
		t = s[-1]
		vis.add(t)
		m = False
		for v in d[t]:
			if v not in vis:
				s.append(v)
				m = True
		if not m:
			tmp = c[t - 1]
			for v in d[t]:
				if v in w:
					tmp += w[v]
			w[t] = tmp
			s.pop()
w = dict()
dfsV2(list(d.keys())[0])
root = max(w.values())
r = sys.maxsize
for u in w:
	if w[u] != root:
		r = min(r, abs(root - 2 * w[u]))
print(r)


from collections import deque

def add_nodes(E, l):
	visited = set()
	queue = deque()
	queue.append(0)
	queue.append(-1)
	level = {}
	visited.add(0)
	count = 1
	flag = False
	while len(queue) != 0:
		u = queue.popleft()
		if u == -1 and flag == False:
			count += 1
			flag = True
			queue.append(-1)
			continue
		elif u == -1 and flag == True:
			break
		flag = False
		if count not in level:
			level[count] = set()
		level[count].add(u)
		for v in E[u]:
			if v not in visited:
				visited.add(v)
				queue.append(v)
	totals = {}
	for k in sorted(level, reverse=True):
		for u in level[k]:
			if u not in totals:
				totals[u] = l[u]
			if k - 1 not in level:
				break
			for v in E[u]:
				if v in level[k - 1] and v in totals:
					totals[v] += totals[u]
				elif v in level[k - 1] and v not in totals:
					totals[v] = totals[u] + l[v]
	return totals
T = int(input())
l = list(map(int, input().split(' ')))
E = {}
for i in range(0, T):
	E[i] = []
for i in range(0, T - 1):
	(u, v) = map(int, input().split(' '))
	E[u - 1].append(v - 1)
	E[v - 1].append(u - 1)
totals = add_nodes(E, l)
total = totals[0]
ans = 1 << 30
for i in range(0, T):
	temp = abs(total - 2 * totals[i])
	ans = min(ans, temp)
print(ans)


N = int(input())
Values = [int(x) for x in input().strip().split(' ')]
Goal = sum(Values)
Tree = [[] for i in range(N)]
for i in range(N - 1):
	(a, b) = [int(x) - 1 for x in input().strip().split(' ')]
	Tree[a].append(b)
	Tree[b].append(a)
(stack, weight) = ([0], [None] * N)
mindiff = Goal
while stack:
	a = stack.pop()
	if weight[a] == None:
		stack.append(a)
		for b in Tree[a]:
			if weight[b] == None:
				stack.append(b)
		weight[a] = 0
	else:
		weight[a] = Values[a]
		for b in Tree[a]:
			weight[a] += weight[b]
		if abs(weight[a] * 2 - Goal) < mindiff:
			mindiff = abs(weight[a] * 2 - Goal)
print(mindiff)


import sys
from collections import deque
sys.setrecursionlimit(100000)

def acc_node_to_subtree_val(node, graph, node_to_subtree_val, arr, nodeparent):
	for child in graph[node] - set([nodeparent]):
		acc_node_to_subtree_val(child, graph, node_to_subtree_val, arr, node)
	subtree_val = arr[node]
	for child in graph[node] - set([nodeparent]):
		subtree_val += node_to_subtree_val[child]
	node_to_subtree_val[node] = subtree_val

def calc_node_to_depth_dic(root, graph):
	ret = dict()
	visited = set()
	queue = deque([root])
	ret[root] = 0
	while queue:
		head = queue.popleft()
		visited.add(head)
		for neighbor in graph[head] - visited:
			ret[neighbor] = ret[head] + 1
			queue.append(neighbor)
	return ret

def rev_dict(dictionary):
	ret = dict()
	for k in dictionary:
		v = dictionary[k]
		if v in ret:
			ret[v].add(k)
		else:
			ret[v] = set([k])
	return ret

def acc_node_to_subtree_val_iter(root, graph, node_to_subtree_val, arr):
	node_to_depth_dict = calc_node_to_depth_dic(root, graph)
	depth_to_nodes_dict = rev_dict(node_to_depth_dict)
	for leaf in depth_to_nodes_dict[len(depth_to_nodes_dict) - 1]:
		node_to_subtree_val[leaf] = arr[leaf]
	for i in range(len(depth_to_nodes_dict) - 2, 0, -1):
		parents = depth_to_nodes_dict[i - 1]
		nodes = depth_to_nodes_dict[i]
		for node in nodes:
			subtree_val = arr[node]
			for child in graph[node] - parents:
				subtree_val += node_to_subtree_val[child]
			node_to_subtree_val[node] = subtree_val
N = int(input())
arr = [int(x) for x in input().split()]
arrsum = sum(arr)
graph = dict()
node_to_subtree_val = dict()
for i in range(N):
	graph[i] = set()
	node_to_subtree_val[i] = arrsum
for _ in range(N - 1):
	(node1, node2) = tuple([int(x) - 1 for x in input().split()])
	graph[node1].add(node2)
	graph[node2].add(node1)
for i in range(N):
	if len(graph[i]) == 1:
		acc_node_to_subtree_val_iter(i, graph, node_to_subtree_val, arr)
		break
ret = arrsum
for i in range(N):
	ret = min(ret, abs(arrsum - node_to_subtree_val[i] * 2))
print(ret)


from collections import defaultdict
n = int(input())
w = [int(x) for x in input().split()]
e = defaultdict(list)
start = -1
for i in range(n - 1):
	(x, y) = map(int, input().split())
	if start == -1:
		start = x
	e[x].append((x, y))
	e[y].append((y, x))
total = sum(w)
visited = set([start])
path = [start]
subweights = {}
while len(path) > 0:
	node = path[-1]
	for edge in e[node]:
		(parent, children) = edge
		if children not in visited:
			visited.add(children)
			path.append(children)
			break
	if node == path[-1]:
		s = w[node - 1]
		for edge in e[node]:
			(parent, children) = edge
			if len(path) < 2 or children != path[-2]:
				s += subweights[children]
		subweights[node] = s
		path.pop()
print(min(map(lambda x: abs(total - 2 * x), subweights.values())))


from collections import deque

class Node:

	def __init__(self, i, weight):
		self.i = i
		(self.weight, self.total_weight) = (weight, weight)
		(self.neighbors, self.children) = (set(), set())
		self.parent = None
		self.is_leaf = True
		self.participation = {}

	def add(self, destination):
		self.neighbors.add(nodes[destination])
		nodes[destination].neighbors.add(self)

	def build(self):
		visit = {}
		queue = deque([self])
		while queue:
			current = queue.popleft()
			visit[current.i] = True
			for neighbor in current.neighbors:
				if neighbor.i not in visit:
					current.children.add(neighbor)
					neighbor.parent = current
					current.is_leaf = False
					queue.append(neighbor)

	def compute_weights(self, leafs):
		queue = deque(leafs)
		while queue:
			current = queue.popleft()
			if current.parent is not None:
				current.parent.participation[current.i] = current.total_weight
				if len(current.parent.participation) == len(current.parent.children):
					current.parent.total_weight += sum((p for p in current.parent.participation.values()))
					queue.append(current.parent)

	def min_cut(self):
		minimum = float('inf')
		visit = {}
		queue = deque([self])
		while queue:
			current = queue.popleft()
			(weight, other) = (current.total_weight, self.total_weight - current.total_weight)
			minimum = min(minimum, abs(weight - other))
			for child in current.children:
				queue.append(child)
		return minimum
n = int(input())
nodes = [Node(i, int(x)) for (i, x) in enumerate(input().split())]
roots = {i: nodes[i] for i in range(n)}
for _ in range(n - 1):
	(a, b) = [int(x) - 1 for x in input().split()]
	nodes[a].add(b)
	if b in roots:
		del roots[b]
root = list(roots.values())[0]
root.build()
root.compute_weights([node for node in nodes if node.is_leaf])
print(root.min_cut())


from collections import deque

class Node:

	def __init__(self, id, value):
		self.id = id
		self.value = value
		self.neighbor = set()
		self.neighborvalue = {}

	def link(self, other):
		self.neighbor.add(other)
		other.neighbor.add(self)

	def unlink(self, other):
		self.neighbor.discard(other)
		other.neighbor.discard(self)

	def sumValue(self):
		sum = 0
		s = deque([self])
		v = set()
		while len(s):
			c = s[-1]
			v.add(c)
			nb = [x for x in c.neighbor if x not in v]
			if len(nb):
				s.append(nb[0])
			else:
				s.pop()
				sum += c.value
		return sum

	def __eq__(self, other):
		return self.id == other.id

	def __hash__(self):
		return hash(self.id)

	def __repr__(self):
		return 'id:{},v:{},nb:{},nbv:{}'.format(self.id + 1, self.value, [x.id + 1 for x in self.neighbor], self.neighborvalue)
n = int(input())
t = [Node(i, v) for (i, v) in enumerate(map(int, input().split()))]
e = []
sumv = sum([x.value for x in t])
for i in range(n - 1):
	(d, c) = map(int, input().split())
	e.append((d - 1, c - 1))
	t[d - 1].link(t[c - 1])
min = -1
sumw = 0
s = deque([t[0]])
v = set()
while len(s):
	c = s[-1]
	v.add(c)
	nb = [x for x in c.neighbor if x not in v]
	if len(nb):
		s.append(nb[0])
	else:
		s.pop()
		nb = [x for x in c.neighbor if not len(s) or (len(s) and x != s[-1])]
		for nbi in nb:
			c.neighborvalue[nbi.id] = sum([nbi.neighborvalue[x] for x in nbi.neighborvalue.keys() if x != c.id]) + nbi.value
		p = [x for x in c.neighbor if len(s) and x == s[-1]]
		if len(p):
			p = p[0]
			c.neighborvalue[p.id] = sumv - sum([c.neighborvalue[x] for x in c.neighborvalue.keys() if x != s[-1].id]) - c.value
for (a, b) in e:
	aa = sum([t[a].neighborvalue[x] for x in t[a].neighborvalue.keys() if x != b]) + t[a].value
	bb = sum([t[b].neighborvalue[x] for x in t[b].neighborvalue.keys() if x != a]) + t[b].value
	r = abs(aa - bb)
	if min < 0 or r < min:
		min = r
print(min)


def DFS(Adj):
	start = 0
	Vtd = [False for x in Adj]
	inQ = [False for x in Adj]
	Q = [start]
	inQ[start] = True
	PostOrd = []
	while Q:
		n1 = Q[len(Q) - 1]
		for n2 in Adj[n1]:
			if not inQ[n2] and (not Vtd[n2]):
				Q.append(n2)
				inQ[n2] = True
		Vtd[n1] = True
		if Q[len(Q) - 1] == n1:
			temp = Q.pop()
			PostOrd.append(temp)
	return PostOrd
n = int(input().strip())
A = input().strip().split(' ')
A = [int(x) for x in A]
Adj = [[] for i in range(n)]
for i in range(n - 1):
	e = input().strip().split(' ')
	(n1, n2) = [int(e[0]) - 1, int(e[1]) - 1]
	Adj[n1].append(n2)
	Adj[n2].append(n1)
PostOrd = DFS(Adj)
Sum = [0 for i in range(n)]
for x in PostOrd:
	Sum[x] = A[x]
	for n in Adj[x]:
		Sum[x] += Sum[n]
SumT1 = Sum[1:]
SumT2 = [Sum[0] - x for x in SumT1]
Diff = [abs(SumT1[i] - SumT2[i]) for i in range(len(SumT1))]
print(min(Diff))


import sys
n = int(input())
visited = [False] * n
found = [False] * n
cache = [-1] * n
ws = [int(i) for i in input().split(' ')]
all_w = sum(ws)
weights = {}
tree = [[] for i in range(n)]
min_d = [float('inf')]
uniq = set()
q = []
S = []
raw = [[] for i in range(n)]
(start, tt) = [int(j) - 1 for j in input().split(' ')]
raw[start].append(tt)
raw[tt].append(start)
for line in sys.stdin:
	(s, t) = [int(j) - 1 for j in line.split(' ')]
	raw[s].append(t)
	raw[t].append(s)
Q = [start]
found[start] = True
while len(Q) > 0:
	node = Q.pop(0)
	for c in raw[node]:
		if not found[c]:
			found[c] = True
			tree[node].append(c)
			Q.append(c)
S = [start]
min_d = float('inf')
cached = [-1] * n
while len(S) > 0:
	s = S[0]
	if len(tree[s]) == 0:
		cached[s] = ws[s]
		S.pop(0)
	else:
		all_good = True
		new_c = ws[s]
		for c in tree[s]:
			if cached[c] == -1:
				all_good = False
				S.insert(0, c)
				break
			else:
				new_c += cached[c]
				new_d = abs(cached[c] * 2 - all_w)
				min_d = min(min_d, new_d)
		cached[s] = new_c
		if all_good:
			S.pop(0)
print(min_d)


import sys

def subtree_costs(tree, vertic_costs):
	stack = []
	costs = list(vertic_costs)
	parents = [None] * len(vertic_costs)
	stack.append((0, 'f'))
	while len(stack) > 0:
		(vert, state) = stack.pop()
		i = tree[vert]
		if state == 'f':
			stack.append((vert, 's'))
			while i != None:
				if i[0] != parents[vert]:
					stack.append((i[0], 'f'))
					parents[i[0]] = vert
				i = i[1]
		else:
			while i != None:
				if i[0] != parents[vert]:
					costs[vert] += costs[i[0]]
				i = i[1]
	return costs
vertic_cnt = int(input())
tree = [None] * vertic_cnt
vertic_costs = [int(i) for i in input().split()]
for i in sys.stdin:
	(a, b) = [int(j) for j in i.split()]
	tree[a - 1] = (b - 1, tree[a - 1])
	tree[b - 1] = (a - 1, tree[b - 1])
tree_cost = sum(vertic_costs)
costs = subtree_costs(tree, vertic_costs)
min_value = min([abs(2 * i - tree_cost) for i in costs])
print(min_value)


from collections import defaultdict, namedtuple

def dfs(start, edges, nodes):
	stack = [(start, start)]
	visited = set()
	while stack:
		(node, parent) = stack.pop()
		nodes[node] = Node(nodes[node].value, nodes[node].total, parent)
		if node in visited:
			continue
		if all((nodes[n_node].total != None for n_node in edges[node] if n_node != parent)):
			node_total = nodes[node].value + sum((nodes[n_node].total for n_node in edges[node] if n_node != parent))
			nodes[node] = Node(nodes[node].value, node_total, nodes[node].parent)
			visited.add(node)
			stack.append((nodes[node].parent, nodes[nodes[node].parent].parent))
		else:
			for n_node in edges[node]:
				if n_node != parent:
					stack.append((n_node, node))
n = int(input())
Node = namedtuple('Node', ['value', 'total', 'parent'])
nodes = {i: Node(int(x), None, None) for (i, x) in enumerate(input().split(), 1)}
edges = defaultdict(list)
loaded_edges = []
for edge in range(n - 1):
	(a, b) = [int(x) for x in input().split()]
	(a, b)
	edges[a] += [b]
	edges[b] += [a]
	loaded_edges += [(a, b)]
dfs(1, edges, nodes)
min_edge = nodes[1].total
for edge in loaded_edges:
	(a, b) = edge
	tree_1 = min(nodes[a].total, nodes[b].total)
	tree_2 = nodes[1].total - tree_1
	(max_tree, min_tree) = (max(tree_1, tree_2), min(tree_1, tree_2))
	min_edge = min(min_edge, max_tree - min_tree)
print(min_edge)


def dfs(Tree, w):
	res = summ = sum(w)
	visited = set()
	stack = [(1, -1)]
	while stack:
		(v, prev_v) = stack[-1]
		childs = []
		if v not in visited:
			childs = [(vertex, v) for vertex in Tree[v] if vertex != prev_v]
		visited.add(v)
		stack.extend(childs)
		if not childs:
			stack.pop()
			if v != 1:
				w[v] += sum((w[vertex] for vertex in Tree[v] if vertex != prev_v))
				res = min(res, abs(summ - 2 * w[v]))
	return res
n = int(input())
w = list(map(int, input().split()))
w = [0] + w
Tree = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	(v1, v2) = map(int, input().split())
	Tree[v1].append(v2)
	Tree[v2].append(v1)
print(dfs(Tree, w))


import sys

class Node:

	def __init__(self, w):
		self.total = self.weight = w
		self.leaves = []
n = int(sys.stdin.readline())
nodes = [Node(int(x)) for x in sys.stdin.readline().strip().split(' ')]
assert len(nodes) == n
root = None
for line in sys.stdin:
	(f, t) = map(int, line.strip().split(' '))
	if root is None:
		root = nodes[f - 1]
	nodes[f - 1].leaves.append(nodes[t - 1])
	nodes[t - 1].leaves.append(nodes[f - 1])
s = [(root, 0)]
while len(s) > 0:
	(node, idx) = s.pop()
	if idx == 0:
		for leave in node.leaves:
			leave.leaves.remove(node)
	if idx < len(node.leaves):
		s.append((node, idx + 1))
		s.append((node.leaves[idx], 0))
	elif len(node.leaves) > 0:
		node.total = node.weight + sum([n.total for n in node.leaves])
print(min([abs(root.total - 2 * n.total) for n in nodes]))


def find_leafs(graph):
	leafs = []
	for v in graph:
		if len(graph[v]) == 1:
			leafs.append(v)
	return leafs

def find_leafs2(graph, branches):
	leafs = []
	r = lambda v: leafs.append(v) if len(graph[v]) == 1 else None
	[r(v) for v in branches]
	return leafs

def test_case(N, w, graph):
	t_sum = sum(w.values())
	min_diff = t_sum

	def cal(leaf, stop, min_diff, branches):
		min_diff = min(min_diff, abs(t_sum - 2 * w[leaf - 1]))
		branch = graph[leaf].pop()
		branches.add(branch)
		if not stop:
			w[branch - 1] += w[leaf - 1]
			graph[branch].remove(leaf)
		del graph[leaf]
		return (min_diff, branches)
	stop = False
	branches = set()
	while not stop:
		if not branches:
			leafs = find_leafs(graph)
		else:
			leafs = find_leafs2(graph, branches)
		branches = set()
		if len(graph) < 3:
			stop = True
		for leaf in leafs:
			(min_diff, branches) = cal(leaf, stop, min_diff, branches)
	return min_diff
N = int(input().strip())
weights = list(map(int, input().strip().split()))
w = dict(zip(range(len(weights)), weights))
graph = {}
for _ in range(N - 1):
	edge = list(map(int, input().strip().split()))
	if edge[0] not in graph:
		graph[edge[0]] = set([edge[1]])
	else:
		graph[edge[0]].add(edge[1])
	if edge[1] not in graph:
		graph[edge[1]] = set([edge[0]])
	else:
		graph[edge[1]].add(edge[0])
print(test_case(N, w, graph))


def cut_the_tree(costs, edges):
	adj = {i: [] for i in range(1, len(costs) + 1)}
	for (n, m) in edges:
		adj[n].append(m)
		adj[m].append(n)
	visited = {i: False for i in adj}
	order = []
	children = {}
	stack = [1]
	while stack:
		node = stack.pop()
		visited[node] = True
		order.append(node)
		children[node] = [c for c in adj[node] if not visited[c]]
		stack.extend(children[node])
	stc = {}
	for node in order[::-1]:
		stc[node] = costs[node - 1] + sum((stc[c] for c in children[node]))
	total = sum(costs)
	return min((abs(total - 2 * s) for s in stc.values()))
N = int(input())
costs = [int(x) for x in input().split()]
edges = [[int(x) for x in input().split()] for _ in range(N - 1)]
print(cut_the_tree(costs, edges))


from collections import defaultdict
n = int(input())
weights = list(map(int, input().split()))
total = sum(weights)
if n == 2:
	print(abs(weights[1] - weights[0]))
cur = tuple(map(int, input().split()))
links = defaultdict(list)
while True:
	try:
		link = tuple(map(int, input().split()))
	except EOFError:
		break
	else:
		links[link[0]].append(link[1])
		links[link[1]].append(link[0])
bottoms = set((i for i in links if len(links[i]) == 1))
bottoms.discard(cur[0])
bottoms.discard(cur[1])

def calc_branch(u):
	stack = [u]
	stack_set = {u}
	while stack:
		last = stack[-1]
		for v in links[last]:
			if v not in bottoms and v not in stack_set:
				stack.append(v)
				stack_set.add(v)
		if last == stack[-1]:
			for v in links[last]:
				if v in bottoms:
					weights[last - 1] += weights[v - 1]
			bottoms.add(last)
			stack.pop()
			stack_set.remove(last)
calc_branch(cur[0])
calc_branch(cur[1])
(heavy, light) = (cur[0], cur[1])
if weights[heavy - 1] < weights[light - 1]:
	(heavy, light) = (light, heavy)
while True:
	direction = None
	max_weight = 0
	for v in links[heavy]:
		if weights[v - 1] > max_weight and v != light:
			direction = v
			max_weight = weights[v - 1]
	if direction is None:
		print(weights[heavy - 1] * 2 - total)
		break
	elif max_weight > total // 2:
		light = heavy
		heavy = direction
	else:
		res = min(weights[heavy - 1] * 2 - total, total - 2 * weights[direction - 1])
		print(res)
		break


from collections import defaultdict, deque
N = int(input())
NodeScore = list(map(int, input().split()))
ConnD = defaultdict(list)
ParentD = {}
ScoreD = {}
GraphLevels = []
for _ in range(N - 1):
	(a, b) = tuple(map(int, input().split()))
	ConnD[a - 1].append(b - 1)
	ConnD[b - 1].append(a - 1)
Root = 0
for i in range(1, N):
	if len(ConnD[i]) > len(ConnD[Root]):
		Root = i
ParentList = [Root]
ParentD[Root] = 4294967295
while len(ParentList) > 0:
	GraphLevels.append([x for x in ParentList])
	nextList = []
	for curNode in ParentList:
		for child in ConnD[curNode]:
			if child != ParentD[curNode]:
				ParentD[child] = curNode
				nextList.append(child)
	ParentList = nextList
lastLevel = len(GraphLevels) - 1
for lv in range(lastLevel, -1, -1):
	for node in GraphLevels[lv]:
		ScoreD[node] = NodeScore[node]
		for child in ConnD[node]:
			if child != ParentD[node]:
				ScoreD[node] += ScoreD[child]
minimumDiff = ScoreD[Root]
for i in range(N):
	if i != Root and abs(ScoreD[Root] - 2 * ScoreD[i]) < minimumDiff:
		minimumDiff = abs(ScoreD[Root] - 2 * ScoreD[i])
print(minimumDiff)


from collections import deque

def make_tree(start_node, adj_list):
	frontier = deque([start_node])
	while frontier:
		current = frontier.popleft()
		for neighbor in adj_list[current]:
			frontier.append(neighbor)
			adj_list[neighbor].remove(current)
	return adj_list

def postorder_traverse(start_node, tree, values):
	sums = list(values)
	stack = deque()
	queue = deque([start_node])
	while queue:
		node = queue.pop()
		stack.append(node)
		for n in tree[node]:
			queue.append(n)
	while stack:
		node = stack.pop()
		for n in tree[node]:
			sums[node - 1] += sums[n - 1]
	return sums

def tree_diff(edges, sums):
	max_sum = max(sums)
	result = float('inf')
	for (node1, node2) in edges:
		sum1 = sums[node1 - 1]
		sum2 = sums[node2 - 1]
		(cut_sum, cut_node) = min((sum1, node1), (sum2, node2))
		result = min(result, abs(max_sum - cut_sum - cut_sum))
		if result == 0:
			break
	return result
n = int(input().strip())
vals = list(map(int, input().strip().split()))
adj = {}
edges = []
for _ in range(n - 1):
	(a, b) = map(int, input().strip().split())
	adj[a] = adj.get(a, set())
	adj[a].add(b)
	adj[b] = adj.get(b, set())
	adj[b].add(a)
	edges.append((a, b))
start = edges[0][0]
print(tree_diff(edges, postorder_traverse(start, make_tree(start, adj), vals)))


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 = [0] * (len(v) + 1)
	visited = [False] * (len(v) + 1)
	stack = [1]
	while len(stack) != 0:
		last = stack[-1]
		visited[last] = True
		notyet = False
		for adj in graph[last]:
			if not visited[adj]:
				notyet = True
				stack.append(adj)
		if not notyet:
			stack.pop()
			stw = 0
			for adj in graph[last]:
				stw += weight[adj]
			stw += v[last - 1]
			weight[last] = stw
	return weight

def find_min_diff(graph, weight, v):
	visited = [False] * (len(v) + 1)
	stack = [1]
	minw = 999999999
	totw = 0
	for x in v:
		totw += x
	while len(stack) != 0:
		pop = stack.pop()
		visited[pop] = True
		for adj in graph[pop]:
			if not visited[adj]:
				stack.append(adj)
				minw = min(minw, abs(totw - 2 * weight[adj]))
	return minw

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


from collections import deque
import sys

def tree_cut(n, weights, edges):
	diffs = []
	seen = [0] * (n + 1)
	total_weight = sum(weights)
	dfs_stack(1, edges, weights, diffs, seen)
	min_cut = min(weights, key=lambda x: abs(2 * x - total_weight))
	return abs(2 * min_cut - total_weight)

def dfs(start, edges, weights, diffs, seen):
	seen[start] = 1
	ans = weights[start]
	if start in edges:
		ans += sum((dfs(node, edges, weights, diffs, seen) for node in edges[start] if not seen[node]))
	diffs.append(ans)
	return ans

def dfs_stack(start, edges, weights, diffs, seen):
	stack = deque()
	stack.append((start, 0))
	while True:
		try:
			elem = stack.pop()
			if seen[elem[0]]:
				weights[elem[1]] += weights[elem[0]]
			else:
				seen[elem[0]] = 1
				stack.append(elem)
				if elem[0] in edges:
					for node in edges[elem[0]]:
						if not seen[node]:
							stack.append((node, elem[0]))
		except IndexError:
			break
n = int(input())
weights = [int(x) for x in input().split()]
weights[0:0] = [0]
edges = {}
for i in range(n - 1):
	(s, e) = [int(x) for x in input().split()]
	if s in edges:
		edges[s].append(e)
	else:
		edges[s] = [e]
	if e in edges:
		edges[e].append(s)
	else:
		edges[e] = [s]
print(tree_cut(n, weights, edges))


import sys

def dfs(root, ancester, adj, value):
	for child in adj[root]:
		if child != ancester:
			dfs(child, root, adj, value)
			value[root] += value[child]

def dfs_loop(root, ancester, adj, value):
	(visited, stack) = (set(), [(root, None)])
	while stack:
		(peek, ancester) = stack[len(stack) - 1]
		if peek in visited:
			stack.pop()
			if ancester:
				value[ancester] += value[peek]
		else:
			visited.add(peek)
			for vertex in adj[peek]:
				if vertex not in visited:
					stack.append((vertex, peek))
sys.setrecursionlimit(1000000)
n = int(input())
arr = [int(value) for value in input().split(' ')]
value = [0] + arr
total = sum(value)
tree_diff = sys.maxsize
adj = {}
for i in range(n - 1):
	(adjA, adjB) = input().split(' ')
	(adjA, adjB) = (int(adjA), int(adjB))
	if adjA not in adj:
		adj[adjA] = [adjB]
	else:
		adj[adjA].append(adjB)
	if adjB not in adj:
		adj[adjB] = [adjA]
	else:
		adj[adjB].append(adjA)
dfs_loop(1, None, adj, value)
for num in value:
	tree_diff = min(tree_diff, abs(num - (total - num)))
print(tree_diff)


import sys

class Tree(object):

	def __init__(self):
		self.value = 0
		self.children = []
		self.index = -1
		self.parent = -1
overallValue = 0
vertices = []
nbVertices = int(sys.stdin.readline())
for j in range(nbVertices):
	vertices.append(Tree())
line = sys.stdin.readline()
for (h, v) in enumerate(list(map(int, line.strip().split(' ')))):
	overallValue += v
	vertices[h].value = v
	vertices[h].index = h
line = sys.stdin.readline()
while len(line) > 0:
	if len(line) > 2:
		pc = list(map(int, line.strip().split(' ')))
		p = pc[0] - 1
		c = pc[1] - 1
		if p == c:
			continue
		vertices[p].children.append(vertices[c])
		vertices[c].children.append(vertices[p])
	line = sys.stdin.readline()

def findBestSplit(overallValue, curMin):
	stack = [0]
	while len(stack) > 0:
		curIdx = stack.pop()
		if curIdx < 0:
			if cur.parent == -1:
				continue
			diff = abs(overallValue - 2 * cur.value)
			if diff < curMin:
				curMin = diff
			parent = vertices[cur.parent]
			parent.value += cur.value
			cur = parent
			continue
		cur = vertices[curIdx]
		stack.append(-1)
		for c in cur.children:
			if c.index == cur.parent:
				continue
			c.parent = curIdx
			stack.append(c.index)
	return curMin
resMin = findBestSplit(overallValue, overallValue)
print(resMin)


def form_tree(tree, branches):
	remaining_queue = [0]
	for node in remaining_queue:
		for child in tree[node]['children']:
			tree[child]['children'].remove(node)
			branches.append((node, child))
			remaining_queue.append(child)

def load_tree():
	elements = int(input())
	values = str.split(input())
	tree = [{'value': int(value), 'children': []} for value in values]
	branches = []
	for i in range(elements - 1):
		(b1, b2) = str.split(input())
		b1 = int(b1) - 1
		b2 = int(b2) - 1
		tree[b1]['children'].append(b2)
		tree[b2]['children'].append(b1)
	form_tree(tree, branches)
	return (tree, branches, elements)

def calculate_weight(tree, elements):
	nodes = [0]
	for node in nodes:
		for child in tree[node]['children']:
			nodes.append(child)
	for i in range(elements):
		cur_element = nodes.pop()
		weight = tree[cur_element]['value']
		if tree[cur_element].get('children') is not None:
			for child in tree[cur_element]['children']:
				weight += tree[child]['weight']
		tree[cur_element]['weight'] = weight

def find_diference(tree, child):
	return abs(tree[0]['weight'] - 2 * tree[child]['weight'])
min_dif = -1
(tree, branches, elements) = load_tree()
calculate_weight(tree, elements)
for branch in branches:
	cur_dif = find_diference(tree, branch[1])
	if min_dif == -1 or cur_dif < min_dif:
		min_dif = cur_dif
print(min_dif)


def get_best_cut(adjacency, weights):
	root = 1
	cumulative_weights = {}
	decide_cumulative_weights(root, adjacency, cumulative_weights, set(), weights)
	total_weight = cumulative_weights[root]
	best_half = None
	for v in adjacency:
		if best_half is None or abs(cumulative_weights[v] - total_weight / 2) < abs(best_half - total_weight / 2):
			best_half = cumulative_weights[v]
	print(abs(total_weight - 2 * best_half))

def decide_cumulative_weights(root, adjacency, cumulative_weights, visited, weights):
	stack = [root]
	while stack:
		node = stack[-1]
		visited.add(node)
		children = adjacency[node]
		finished_children = True
		for child in children:
			if child not in visited:
				stack.append(child)
				finished_children = False
		if finished_children:
			stack.pop()
			total = weights[node]
			for child in children:
				if child in cumulative_weights:
					total += cumulative_weights[child]
			cumulative_weights[node] = total
vcount = int(input())
raw_weights = list(map(int, input().split()))
weights = {}
for i in range(vcount):
	weights[i + 1] = raw_weights[i]
adj = {v: [] for v in range(1, vcount + 1)}
for edge in range(vcount - 1):
	(start, end) = list(map(int, input().split()))
	adj[start].append(end)
	adj[end].append(start)
get_best_cut(adj, weights)


from collections import defaultdict
N = int(input().strip())
weight = [int(a_temp) for a_temp in input().strip().split(' ')]
edges = []
for a0 in range(N - 1):
	a = [int(a_temp) for a_temp in input().strip().split(' ')]
	edges.append(a)
graph = defaultdict(set)
for e in edges:
	graph[e[0]].add(e[1])
	graph[e[1]].add(e[0])
root = edges[0][0]
visited = {root}
child = defaultdict(set)
path = []
stack = [root]
arr = N * [0]
weight_sum = sum(weight)
while stack:
	node = stack.pop()
	path.append(node)
	visited.add(node)
	for c in graph[node]:
		if c not in visited:
			stack.append(c)
			child[node].add(c)
path.reverse()
for n in path:
	if len(graph[n]) == 1:
		arr[n - 1] = weight[n - 1]
	else:
		arr[n - 1] = sum([arr[c - 1] for c in child[n]]) + weight[n - 1]
res = [abs(weight_sum - 2 * arr[i]) for i in range(N) if i != root - 1]
print(min(res))


n = int(input().strip())
weights = [int(temp) for temp in input().strip().split(' ')]
adj_list = [[] for _ in range(n)]
for _ in range(n - 1):
	(i, j) = input().strip().split(' ')
	(i, j) = [int(i) - 1, int(j) - 1]
	adj_list[i].append(j)
	adj_list[j].append(i)
total_cost = sum(weights)
subtree_cost = [0] * n
visited = [False] * n
search_stack = [0]
calc_stack = []
visited[0] = True
while search_stack != []:
	ci = search_stack.pop(-1)
	children = []
	for v in adj_list[ci]:
		if not visited[v]:
			children.append(v)
			search_stack.append(v)
			visited[v] = True
	calc_stack.append((ci, children))
for (ci, children) in reversed(calc_stack):
	subtree_cost[ci] = weights[ci]
	for v in children:
		subtree_cost[ci] += subtree_cost[v]
min_diff = abs(total_cost - 2 * subtree_cost[0])
for i in range(1, n):
	min_diff = min(min_diff, abs(total_cost - 2 * subtree_cost[i]))
print(min_diff)


from collections import defaultdict
num_vertices = int(input().strip())
weights = list(map(int, input().strip().split()))
total = sum(weights)
weights.insert(0, None)
node_weight = [0] * (num_vertices + 1)
edges = defaultdict(list)
for _ in range(num_vertices - 1):
	(a, b) = tuple(map(int, input().strip().split()))
	edges[a].append(b)
	edges[b].append(a)
visited = [False] * (num_vertices + 1)
stack = [1]
next_level = []
diff = total
level = 1
level_dict = dict()
level_dict[1] = [1]
while len(stack) > 0:
	while len(stack) > 0:
		t = stack.pop()
		visited[t] = True
		if t in edges:
			for i in edges[t]:
				if not visited[i]:
					next_level.append(i)
	level += 1
	level_dict[level] = next_level[:]
	(stack, next_level) = (next_level, stack)
while level > 0:
	for i in level_dict[level]:
		node_weight[i] = weights[i]
		if i in edges:
			node_weight[i] += sum(map(lambda x: node_weight[x], edges[i]))
		diff = diff if abs(total - node_weight[i] * 2) > diff else abs(total - node_weight[i] * 2)
	level -= 1
print(diff)


class Node:

	def __init__(self, node_id, parent, weight):
		self.id = node_id
		self.parent = parent
		self.weight = weight
		self.children = []
		self.total_weight = weight

	def __str__(self):
		return 'id %s weight %s child_count %s' % (self.id, self.total_weight, len(self.children))

	def build_tree(self, graph: dict, added_set: set):
		my_node = self
		while my_node is not None:
			added_set.add(my_node.id)
			if len(graph[my_node.id]['adj']) > 0:
				child_id = graph[my_node.id]['adj'].pop()
				if child_id not in added_set:
					child = Node(child_id, my_node, graph[child_id]['weight'])
					graph[child_id]['adj'].remove(my_node.id)
					my_node.children.append(child)
					my_node = child
			else:
				if my_node.parent is not None:
					my_node.parent.total_weight += my_node.total_weight
				my_node = my_node.parent

	def get_min_weight_diff(self):
		process_list = [self]
		total_tree_weight = self.total_weight
		min_weight_diff = self.total_weight
		while len(process_list) > 0:
			my_node = process_list.pop()
			for child in my_node.children:
				process_list.append(child)
				child_tree_weight = child.total_weight
				remaining_tree_weight = total_tree_weight - child.total_weight
				difference = abs(remaining_tree_weight - child_tree_weight)
				if difference < min_weight_diff:
					min_weight_diff = difference
		return min_weight_diff

class Tree:

	def __init__(self, graph):
		root_id = self.get_root(graph)
		self.root = Node(root_id, None, graph[root_id]['weight'])
		self.root.build_tree(graph, set())

	def get_min_weight_diff(self):
		return self.root.get_min_weight_diff()

	def get_root(self, graph: dict):
		for (i_node, data) in graph.items():
			if len(data['adj']) > 1:
				return i_node
		return list(graph.keys())[0]

def read_input():
	nodes = int(input())
	node_weights = get_int_list(input())
	edge_list = []
	for i_edges in range(nodes - 1):
		edge_list.append(get_int_list(input()))
	return (node_weights, edge_list)

class CutTheTree:

	def __init__(self):
		(weight_list, edge_list) = read_input()
		graph = self.build_graph(weight_list, edge_list)
		self.tree = Tree(graph)

	def build_graph(self, weight_list, edge_list):
		graph = {i: {'weight': weight, 'adj': set()} for (i, weight) in enumerate(weight_list, 1)}
		for (node1, node2) in edge_list:
			graph[node1]['adj'].add(node2)
			graph[node2]['adj'].add(node1)
		return graph

	def calculate(self):
		return self.tree.get_min_weight_diff()

def main():
	my_obj = CutTheTree()
	print(my_obj.calculate())

def get_int_list(in_str):
	return [int(i) for i in in_str.strip().split()]
main()


n = int(input())
values = list(map(int, input().split()))
nodes = [[] for _ in range(n)]
for _ in range(n - 1):
	(n1, n2) = map(int, input().split())
	nodes[n1 - 1].append(n2 - 1)
	nodes[n2 - 1].append(n1 - 1)
processed = [False] * n
orders = [0]
current = [0]
while len(current) > 0:
	tmpList = []
	for i in current:
		processed[i] = True
		for j in nodes[i]:
			nodes[j].remove(i)
			if processed[j] == True:
				continue
			processed[j] = True
			orders.append(j)
			tmpList.append(j)
	current = tmpList
sumTotal = sum(values)
minDif = sumTotal
for _ in range(n):
	current = orders.pop()
	val = values[current]
	for c in nodes[current]:
		val += values[c]
	values[current] = val
	dif = abs(sumTotal - 2 * val)
	if dif < minDif:
		minDif = dif
print(minDif)


import collections
import re
n = int(input())
values = [int(x) for x in re.split('\\s+', input().strip())]
G = collections.defaultdict(list)
for n_ in range(n - 1):
	pass
	(l, r) = [int(x) - 1 for x in re.split('\\s+', input().strip())]
	G[l].append(r)
	G[r].append(l)
T = collections.defaultdict(list)
visited = [False] * n
vsum = [0] * n

def dfs(x):
	stack = collections.deque()
	stack.append((x, 0))
	while stack:
		(curr, curredge) = stack.pop()
		visited[curr] = True
		if curredge + 1 > len(G[curr]):
			vsum[curr] = values[curr]
			for y in T[curr]:
				vsum[curr] += vsum[y]
			continue
		if visited[G[curr][curredge]]:
			stack.append((curr, curredge + 1))
		else:
			stack.append((curr, curredge + 1))
			stack.append((G[curr][curredge], 0))
			T[curr].append(G[curr][curredge])
dfs(0)
totalsum = vsum[0]
print(min([abs(totalsum - 2 * x) for x in vsum[1:]]))


import sys

class Node(object):

	def __init__(self, number, index):
		self.index = index
		self.number = number
		self.connected_nodes = []
		self.prev = None

	def __eq__(self, other):
		return self.index == other.index
N = int(next(sys.stdin))
node_list = [Node(int(num), index) for (index, num) in enumerate(next(sys.stdin).rstrip('\n').split(' '))]
connects_list = (l.rstrip('\n').split(' ') for l in sys.stdin)
for connects in connects_list:
	node_list[int(connects[0]) - 1].connected_nodes.append(node_list[int(connects[1]) - 1])
	node_list[int(connects[1]) - 1].connected_nodes.append(node_list[int(connects[0]) - 1])
head = node_list[0]
node_stack = [head]
while node_stack:
	last = node_stack[-1]
	if last.connected_nodes:
		for node in last.connected_nodes:
			node.prev = last
			node.connected_nodes.remove(last)
		node_stack += last.connected_nodes
		last.connected_nodes = []
	else:
		if last.prev:
			last.prev.number += last.number
		node_stack.pop()
min_diff = 1000000000
for node in node_list:
	if node != head:
		min_diff = min(min_diff, abs(head.number - 2 * node.number))
print(min_diff)


class Node:
	child = []
	index = -1
	val = -1
	sum = 0

	def __init__(self, index, val, child=[]):
		self.index = index
		self.val = val
		self.child = child
		self.sum = val

class DFS:
	nodes = []
	levels = {}

	def __init__(self, nodes):
		self.nodes = nodes

	def doDFS_ordering(self, cnodes, level, visited):
		tnodes = cnodes
		level = 0
		while len(tnodes) > 0:
			self.levels[level] = tnodes
			nextChilds = []
			for i in range(len(tnodes)):
				visited[tnodes[i].index] = True
				curChild = tnodes[i].child
				tnodes[i].child = []
				for j in range(len(curChild)):
					if not visited[curChild[j].index]:
						tnodes[i].child.append(curChild[j])
						nextChilds.append(curChild[j])
			level += 1
			tnodes = nextChilds
		return level

	def populate_sum(self, level):
		while level >= 0:
			tnodes = self.levels.get(level, [])
			for i in range(len(tnodes)):
				childs = tnodes[i].child
				for j in range(len(childs)):
					tnodes[i].sum += childs[j].sum
			level -= 1
n = int(input())
data = list(map(int, input().split(' ')))
total = sum(data)
nodes = []
visited = []
for i in range(n):
	nodes.append(Node(i, data[i], []))
	visited.append(False)
edges = []
for i in range(n - 1):
	inp = list(map(int, input().split(' ')))
	nodes[inp[1] - 1].child.append(nodes[inp[0] - 1])
	nodes[inp[0] - 1].child.append(nodes[inp[1] - 1])
	edges.append((inp[0] - 1, inp[1] - 1))
dfs = DFS(nodes)
l = dfs.doDFS_ordering([nodes[0]], 0, visited)
dfs.populate_sum(l - 1)
minDiff = total
for i in range(n - 1):
	(x, y) = edges[i]
	a = min(nodes[x].sum, nodes[y].sum)
	minDiff = min(abs(abs(a) - abs(total - a)), minDiff)
print(minDiff)


import sys

def solve(g, debug=0):

	def unidirect(g):
		visited = set([1])
		g[1].append(None)
		while visited:
			n = visited.pop()
			for c in g[n][1]:
				g[c][1].remove(n)
				g[c].append(n)
				visited.add(c)

	def tree_weight_cache(g, node):
		f = {}
		for n in g:
			f[n] = []
			f[n].append(g[n][0])
			f[n].append(list(g[n][1]))
			f[n].append(g[n][2])
		cache = {n: f[n][0] for n in f}
		if debug > 0:
			print(cache, file=sys.stderr)
		while len(f) > 1:
			ns = [n for n in f]
			for n in ns:
				if n not in f:
					continue
				(sm, c, p) = (f[n][0], n, f[n][-1])
				while p and len(f[c][1]) == 0:
					if debug > 0:
						print('c=%d p=%d' % (c, p), file=sys.stderr)
						print('f=%s' % f, file=sys.stderr)
						print('cache=%s' % cache, file=sys.stderr)
					cache[p] += cache[c]
					del f[c]
					f[p][1].remove(c)
					(c, p) = (p, f[p][-1])
				if debug > 0:
					print('c=%d' % c, file=sys.stderr)
					print('f=%s' % f, file=sys.stderr)
					print('cache=%s' % cache, file=sys.stderr)
		return cache
	if debug > 0:
		print(g, file=sys.stderr)
	unidirect(g)
	if debug > 0:
		print(g, file=sys.stderr)
	cache = tree_weight_cache(g, 1)
	if debug > 0:
		print(cache, file=sys.stderr)
	(rval, sm) = (cache[1], cache[1])
	for node in g:
		for next in g[node][1]:
			u = cache[next]
			v = sm - cache[next]
			delta = abs(u - v)
			rval = min(rval, delta)
	return rval

def run():
	_ = int(input())
	g = {i + 1: [w, set()] for (i, w) in enumerate(map(int, input().split()))}
	for _ in range(len(g) - 1):
		(fr, to) = map(int, input().split())
		g[fr][1].add(to)
		g[to][1].add(fr)
	print(solve(g, 0))
run()


nodes = int(input())
values = input().split()
nodeVal = {}
for i in range(nodes):
	nodeVal[i + 1] = int(values[i])
del values
neighbours = {}
for i in range(1, nodes):
	(a, b) = input().split()
	(a, b) = (int(a), int(b))
	if a in neighbours:
		neighbours[a].append(b)
	else:
		neighbours[a] = [b]
	if b in neighbours:
		neighbours[b].append(a)
	else:
		neighbours[b] = [a]
children = {}
parent = {}
curGen = set([1])
prevGen = set()
nextGen = set()
while True:
	for node in curGen:
		for neighbour in neighbours[node]:
			if neighbour in prevGen:
				parent[node] = neighbour
			else:
				nextGen.add(neighbour)
				children[node] = children.get(node, set()) | set([neighbour])
	prevGen |= curGen
	if len(nextGen) == 0:
		break
	else:
		curGen = nextGen
		nextGen = set()
del neighbours
del nextGen
nodeCumulate = {}
curGen = [node for node in nodeVal if node not in children]
prevGen = set()
explored = set()
while True:
	for node in curGen:
		if node in explored:
			continue
		explored.add(node)
		nodeCumulate[node] = nodeVal[node] + sum([nodeCumulate[child] for child in children.get(node, set())])
		if node in parent and sum([1 for node in children[parent[node]] if node not in explored]) == 0:
			prevGen.add(parent[node])
	if len(prevGen) == 0:
		break
	else:
		curGen = prevGen
		prevGen = set()
print(min([abs(nodeCumulate[1] - 2 * nodeCumulate[child]) for child in range(2, nodes + 1)]))


def main():
	n = int(input())
	graph = [[] for _ in range(n + 1)]
	weights = [0] + [int(x) for x in input().split()]
	for _ in range(n - 1):
		(a, b) = [int(x) for x in input().split()]
		graph[a].append(b)
		graph[b].append(a)
	tree = [[] for _ in graph]
	reverse_traversal_order = []
	visited = [False for _ in graph]
	costs = [None for _ in graph]
	queue = [1]
	while queue:
		node = queue.pop()
		reverse_traversal_order.append(node)
		for child in graph[node]:
			if graph[child] is not None:
				tree[node].append(child)
				queue.append(child)
		graph[node] = None
	all_weights = sum(weights)
	best = all_weights
	for node in reversed(reverse_traversal_order):
		costs[node] = weights[node]
		for child in tree[node]:
			costs[node] += costs[child]
		best = min(best, abs(all_weights - 2 * costs[node]))
	print(best)
main()


from collections import defaultdict
n = int(input())
cost = [int(x) for x in input().split()]
edges = defaultdict(list)
for i in range(n - 1):
	(a, b) = [int(x) for x in input().split()]
	edges[a - 1] += [b - 1]
	edges[b - 1] += [a - 1]
sumBelow = cost[:]
level = [0] * n
parent = [None] * n
atLevel = defaultdict(list)
L = [0]
while L:
	v = L.pop()
	for w in edges[v]:
		if level[w] == 0 and w:
			level[w] = level[v] + 1
			parent[w] = v
			atLevel[level[w]] += [w]
			L.append(w)
end = max(level)
at = end
while at >= 0:
	for w in atLevel[at]:
		sumBelow[parent[w]] += sumBelow[w]
	at -= 1
differences = []
for i in range(1, n):
	differences.append(max(2 * sumBelow[i] - sumBelow[0], sumBelow[0] - 2 * sumBelow[i]))
print(min(differences))


class Node:

	def __init__(self, value):
		self.value = value
		self.neighbors = []
		self.parent = None
		self.sum = 0

class Tree:

	def __init__(self, nodevals):
		self.nodes = [Node(v) for v in nodevals]

	def addbranch(self, branch):
		self.nodes[branch[0]].neighbors.append(self.nodes[branch[1]])
		self.nodes[branch[1]].neighbors.append(self.nodes[branch[0]])

	def build(self):
		toProcess = [self.nodes[0]]
		while toProcess:
			node = toProcess.pop()
			for child in node.neighbors:
				child.parent = node
				child.neighbors.remove(node)
				toProcess.append(child)

	def mindiff(self):
		total = sum((node.value for node in self.nodes))
		out = total
		node = self.nodes[0]
		while node is not None:
			if node.neighbors:
				node = node.neighbors.pop()
			else:
				node.sum += node.value
				if node.parent is not None:
					node.parent.sum += node.sum
				diff = abs(total - 2 * node.sum)
				if diff < out:
					out = diff
				node = node.parent
		return out
N = int(input().strip())
tree = Tree([int(x) for x in input().strip().split()])
for i in range(N - 1):
	tree.addbranch([int(x) - 1 for x in input().strip().split()])
tree.build()
print(tree.mindiff())


import sys

class Node:

	def __init__(self, vertex, value):
		self.vertex = vertex
		self.value = value
		self.subtree_sum = 0
		self.edges = []
		self.visited = False

def build_subtree_sum(root):
	pre_stack = [root]
	post_stack = []
	while len(pre_stack) > 0:
		node = pre_stack.pop()
		post_stack.append(node)
		for child_node in node.edges:
			if not child_node.visited:
				pre_stack.append(child_node)
				child_node.visited = True
	while len(post_stack) > 0:
		node = post_stack.pop()
		node.visited = False
		if len(node.edges) > 1 or node.vertex == 1:
			for child_node in node.edges:
				if child_node.subtree_sum > 0:
					node.subtree_sum += child_node.subtree_sum
		node.subtree_sum += node.value

def cut_the_tree(root):
	stack = [root]
	sum = root.subtree_sum
	min = root.subtree_sum
	while len(stack) > 0:
		node = stack.pop()
		sum -= node.subtree_sum
		node.visited = True
		tree_diff = abs(node.subtree_sum - sum)
		if min > tree_diff:
			min = tree_diff
		sum += node.value
		for child_node in node.edges:
			if child_node.subtree_sum < node.subtree_sum:
				sum += child_node.subtree_sum
		for child_node in node.edges:
			if not child_node.visited:
				stack.append(child_node)
	return min
N = int(input().strip())
v = [int(q_temp) for q_temp in input().strip().split(' ')]
nodes = []
for n in range(N):
	nodes.append(Node(n + 1, v[n]))
for n in range(N - 1):
	e = [int(q_temp) for q_temp in input().strip().split(' ')]
	nodes[e[0] - 1].edges.append(nodes[e[1] - 1])
	nodes[e[1] - 1].edges.append(nodes[e[0] - 1])
nodes[0].visited = True
build_subtree_sum(nodes[0])
min = cut_the_tree(nodes[0])
print(min)


class TreeNode(object):

	def __init__(self, val, index):
		self.p = None
		self.value = val
		self.index = index
		self.total = val
		self.kids = []
N = int(input())
nodes = [TreeNode(int(x), i + 1) for (i, x) in enumerate(input().split())]
diff = 0
edges = []
hashes = {}
root = nodes[0]
root.p = root

def addEdgeToTree1(edge):
	n1 = nodes[edge[0] - 1]
	n2 = nodes[edge[1] - 1]
	if n1.p and n2.p:
		print('Invalid Edge:', edge)
	elif n1.p and n2.p is None:
		n1.kids.append(n2)
		n2.p = n1
	elif n2.p and n1.p is None:
		n2.kids.append(n1)
		n1.p = n2
	else:
		print('None Edge:', edge)
		n1.kids.append(n2)
		n2.p = n1

def addEdgeToTree2(node):
	for c in hashes[node.index]:
		i = nodes[c - 1]
		if i != node and i.p is None:
			i.p = node
			node.kids.append(i)
			addEdgeToTree(i)
	print(node.index, node, node.p, hashes[node.index])

def addEdgeToTree(root):
	jobs = [root]
	while len(jobs) > 0:
		for (i, j) in enumerate(jobs):
			jobs.pop(i)
			for c in hashes[j.index]:
				node = nodes[c - 1]
				if node.p is None and node is not j:
					node.p = j
					j.kids.append(node)
					jobs.append(node)

def walkTreeSum(root):
	jobs = [root]
	dfs = []
	while jobs:
		node = jobs.pop(0)
		dfs.append(node)
		jobs.extend(node.kids)
	while dfs:
		node = dfs.pop()
		if node is not root:
			node.p.total += node.total

def walkTreeSum2(node):
	if len(node.kids) == 0:
		return
	for i in node.kids:
		walkTreeSum(i)
		node.total += i.total
for i in range(N - 1):
	edge = [int(x) for x in input().split()]
	edges.append(edge)
	if edge[0] not in hashes:
		hashes[edge[0]] = []
	hashes[edge[0]].append(edge[1])
	if edge[1] not in hashes:
		hashes[edge[1]] = []
	hashes[edge[1]].append(edge[0])
addEdgeToTree(root)
walkTreeSum(root)
for edge in edges:
	n1 = nodes[edge[0] - 1]
	n2 = nodes[edge[1] - 1]
	n = n2
	if n1 in n2.kids:
		n = n1
	d = abs(root.total - n.total * 2)
	if diff == 0:
		diff = d
	diff = min(diff, d)
print(diff)


import sys

class Node:

	def __init__(self, data, index, parent_index):
		self.data = data
		self.children = None
		self.index = index
		self.parent_index = parent_index

	def add_child(self, node):
		if self.children is None:
			self.children = [node]
		else:
			self.children.append(node)

class Edge:

	def __init__(self, from_node, to_node):
		self.from_node = from_node
		self.to_node = to_node

def build_tree(root, root_index, vertices, edge_map, node_dict):
	parent_index_queue = [root_index]
	try:
		while True:
			parent_index = parent_index_queue.pop(0)
			parent_node = node_dict.get(parent_index)
			children_index = edge_map.get(parent_index)
			if children_index is not None:
				for index in children_index:
					if parent_node.parent_index is None or index != parent_node.parent_index:
						node = Node(vertices[index - 1], index, parent_index)
						parent_node.add_child(node)
						parent_index_queue.append(index)
						if node_dict.get(index) is None:
							node_dict[index] = node
	except:
		pass

def sum_sub_tree(root, sum_subtree_map):
	if root is None:
		return 0
	node_stack = [root]
	node_queue = [root]
	node = root
	try:
		while True:
			node = node_queue.pop()
			if node.children is not None:
				for child in node.children:
					node_queue.append(child)
					node_stack.append(child)
	except:
		pass
	try:
		while True:
			node = node_stack.pop()
			if node.children is None:
				sum_subtree_map[node.index] = node.data
			else:
				sum = node.data
				for child in node.children:
					sum += sum_subtree_map[child.index]
				sum_subtree_map[node.index] = sum
	except:
		pass
	return sum_subtree_map[root.index]
N = int(input())
vertices = [int(x) for x in input().split()]
edge_map = {}
edge_arry = []
for i in range(N - 1):
	(from_node, to_node) = [int(x) for x in input().split()]
	edge_arry.append(Edge(from_node, to_node))
	if edge_map.get(from_node) is None:
		edge_map[from_node] = [to_node]
	else:
		edge_map[from_node].append(to_node)
	if edge_map.get(to_node) is None:
		edge_map[to_node] = [from_node]
	else:
		edge_map[to_node].append(from_node)
root = Node(vertices[0], 1, None)
node_dict = {1: root}
build_tree(root, 1, vertices, edge_map, node_dict)
sum_subtree_map = {}
total = sum_sub_tree(root, sum_subtree_map)
min_tree_diff = total
for edge in edge_arry:
	sum_part = sum_subtree_map[edge.to_node]
	tree_diff = abs(sum_part * 2 - total)
	if tree_diff < min_tree_diff:
		min_tree_diff = tree_diff
print(min_tree_diff)


from collections import defaultdict

def read_graph():
	graph = defaultdict(set)
	for _ in range(n - 1):
		(v1, v2) = map(int, input().split())
		graph[v1 - 1].add(v2 - 1)
		graph[v2 - 1].add(v1 - 1)
	return graph

def dfs_sum():
	visited = set()
	stack = [0]
	visited.add(0)
	operations = []
	while stack:
		node = stack.pop()
		neighbours = set(graph[node]) - visited
		if neighbours:
			operations.append(node)
			visited.add(node)
			operations.append('=')
			for neigh in set(graph[node]) - visited:
				stack.append(neigh)
				operations.append(neigh)
			operations.append('+')
	sum_ = 0
	while operations:
		v = operations.pop()
		if v == '+':
			sum_ = 0
		elif v == '=':
			node = operations.pop()
			node_subtree_sum[node] += sum_
		else:
			sum_ += node_subtree_sum[v]

def dfs():
	visited = set()
	min_diff = values_sum
	stack = [0]
	while stack:
		x = stack.pop()
		visited.add(x)
		for neigh in set(graph[x]) - visited:
			stack.append(neigh)
			diff = abs(2 * node_subtree_sum[neigh] - values_sum)
			min_diff = min(diff, min_diff)
	return min_diff
n = int(input())
node_values = list(map(int, input().split()))
values_sum = sum(node_values)
node_subtree_sum = node_values
graph = read_graph()
dfs_sum()
print(dfs())


import sys
from collections import deque

def cutTree(weights, edges):
	nodes = []
	for weight in weights:
		nodes.append({'weight': weight, 'sum': weight, 'neighbors': []})
	edges = [[e - 1 for e in edge] for edge in edges]
	for edge in edges:
		nodes[edge[0]]['neighbors'].append(edge[1])
		nodes[edge[1]]['neighbors'].append(edge[0])
	visited = set([0])
	q = deque([0])
	nodeOrder = []
	while q:
		curNode = q.popleft()
		nodeOrder.append(curNode)
		for child in nodes[curNode]['neighbors']:
			if child not in visited:
				visited.add(child)
				q.append(child)
	nodeOrder.reverse()
	for node in nodeOrder:
		visited.remove(node)
		for child in nodes[node]['neighbors']:
			if child not in visited:
				nodes[node]['sum'] += nodes[child]['sum']
	totalSum = nodes[0]['sum']
	min_diff = sys.maxsize
	for edge in edges:
		subsum = min(nodes[edge[0]]['sum'], nodes[edge[1]]['sum'])
		min_diff = min(min_diff, abs(totalSum - 2 * subsum))
	print(min_diff)
n = int(input())
weights = list(map(int, input().split()))
edges = []
for _ in range(n - 1):
	edges.append(list(map(int, input().split())))
cutTree(weights, edges)


from collections import deque
n = int(input())
weights = list(map(int, input().split()))
weightsums = dict()
weights.insert(0, 0)
totalweight = sum(weights)
childrenof = dict()
parentof = dict()
adj = dict()
for _ in range(n - 1):
	(n1, n2) = map(int, input().split())
	if n1 in adj:
		adj[n1].append(n2)
	else:
		adj[n1] = [n2]
	if n2 in adj:
		adj[n2].append(n1)
	else:
		adj[n2] = [n1]
queue = deque()
root = 1
childrenof[root] = adj[root]
for child in childrenof[root]:
	parentof[child] = root
	queue.append(child)
while len(queue) > 0:
	node = queue.popleft()
	childrenof[node] = []
	parent = parentof[node]
	for child in adj[node]:
		if child != parent:
			childrenof[node].append(child)
			parentof[child] = node
			queue.append(child)
stack = [root]
visited = set()
found = -1
while found < 0:
	node = stack[len(stack) - 1]
	if node not in visited:
		visited.add(node)
		for child in childrenof[node]:
			stack.append(child)
	else:
		weightsums[node] = weights[node]
		mind = totalweight
		candidate = node
		for child in childrenof[node]:
			weightsums[node] += weightsums[child]
			d = abs(totalweight - weightsums[child] * 2)
			if d < mind:
				candidate = child
				mind = d
		d = abs(totalweight - weightsums[node] * 2)
		if d < mind:
			candidate = node
			mind = d
		if weightsums[node] > totalweight - weightsums[node]:
			found = node
			print(mind)
		else:
			stack.pop()


import sys
net = [x.split() for x in sys.stdin.readlines()]
values = list(map(int, net[1]))
N = int(net[0][0])
sv = sum(values)
valv = [0] * N
x1 = []
x2 = []
for i in range(2, len(net)):
	x = list(map(int, net[i]))
	x1 += [int(x[0]) - 1]
	x2 += [int(x[1]) - 1]
y1 = x1 + x2
y2 = x2 + x1
(graph, seen) = ({}, set())
for i in range(len(y1)):
	k_val = y1[i]
	if k_val not in seen:
		seen.add(k_val)
		graph[k_val] = set([y2[i]])
	else:
		graph[k_val].add(y2[i])
(visited, stack, mval) = (set(), [0], sv)
while stack:
	vertex = stack[-1]
	try:
		vch = graph[vertex] - visited
	except:
		valv[vertex] = values[vertex]
		val = abs(sv - 2 * valv[vertex])
		if mval > val:
			mval = val
		visited.add(vertex)
		stack.pop()
		continue
	if vertex in visited:
		if len(vch) == 0:
			chval = sum([valv[x] for x in graph[vertex]])
			valv[vertex] = chval + values[vertex]
			val = abs(sv - 2 * valv[vertex])
			if mval > val:
				mval = val
			stack.pop()
		else:
			break
	else:
		visited.add(vertex)
		stack.extend(vch)
print(mval)


class Node:

	def __init__(self, name, data, neighbors=()):
		self.name = name
		self.data = data
		self.neighbors = list(neighbors)

	def _key(self):
		return (len(self.neighbors), self.data)

class PriorityQueue:

	def __init__(self, iterable=()):
		self._heap = list(iterable)
		self._heap_index_by_name = {node.name: i for (i, node) in enumerate(self._heap)}
		self._build_heap()

	def __len__(self):
		return len(self._heap)

	def _lt(self, a, b):
		return a._key() < b._key()

	def _swap(self, i, j):
		(self._heap[i], self._heap[j]) = (self._heap[j], self._heap[i])
		self._heap_index_by_name[self._heap[i].name] = i
		self._heap_index_by_name[self._heap[j].name] = j

	def _heapify(self, i):
		least_index = i
		for child_index in range(2 * i + 1, min(2 * i + 3, len(self._heap))):
			if self._lt(self._heap[child_index], self._heap[least_index]):
				least_index = child_index
		if least_index == i:
			return
		self._swap(i, least_index)
		self._heapify(least_index)

	def _build_heap(self):
		for i in range((len(self._heap) - 2) // 2, -1, -1):
			self._heapify(i)

	def peek(self):
		return self._heap[0]

	def pop(self):
		front = self.peek()
		self._heap[0] = self._heap[-1]
		self._heap.pop()
		self._heapify(0)
		del self._heap_index_by_name[front.name]
		return front

	def notify_decrease_key(self, node):
		if type(node) is Node:
			i = self._heap_index_by_name[node.name]
		else:
			i = node
		if i <= 0:
			return
		parent_i = (i - 1) // 2
		if self._lt(self._heap[i], self._heap[parent_i]):
			self._swap(i, parent_i)
			self.notify_decrease_key(parent_i)
n = int(input().strip())
data = [int(x) for x in input().strip().split()]
edges = [set() for i in range(n)]
for i in range(n - 1):
	(u, v) = (int(x) for x in input().strip().split())
	(u, v) = (u - 1, v - 1)
	edges[u].add(v)
	edges[v].add(u)
nodes_by_name = []
for i in range(n):
	node = Node(i, data[i])
	for neighbor_i in edges[i]:
		if i <= neighbor_i:
			continue
		neighbor = nodes_by_name[neighbor_i]
		node.neighbors.append(neighbor)
		neighbor.neighbors.append(node)
	nodes_by_name.append(node)
queue = PriorityQueue(nodes_by_name)
while len(queue) > 2:
	least_leaf = queue.pop()
	parent = least_leaf.neighbors[0]
	parent.data += least_leaf.data
	parent.neighbors.remove(least_leaf)
	queue.notify_decrease_key(parent)
(u, v) = (queue.pop(), queue.pop())
print(abs(u.data - v.data))


from collections import defaultdict, deque

class Node:

	def __init__(self):
		self.value = 0
		self.parent = None
		self.edges = list()

	def set_parent(self):
		l = list([self])
		while l:
			s = l.pop()
			for i in s.edges:
				if i is not s.parent:
					i.parent = s
					l.append(i)

	def set_value(self):
		l = list([(self, True)])
		while l:
			(s, f) = l.pop()
			if f:
				l.append((s, False))
				for i in s.edges:
					if i is not s.parent:
						l.append((i, True))
			elif s.parent:
				s.parent.value += s.value

	def get_min_diff(self):
		l = list([self])
		min_diff = float('inf')
		while l:
			s = l.pop()
			for i in s.edges:
				if i is not s.parent:
					min_diff = min(min_diff, abs(self.value - 2 * i.value))
					l.append(i)
		return min_diff
n = int(input())
val = [int(x) for x in input().split()]
d = defaultdict(Node)
for i in range(n - 1):
	(a, b) = [int(x) for x in input().split()]
	d[a].value = val[a - 1]
	d[b].value = val[b - 1]
	d[a].edges.append(d[b])
	d[b].edges.append(d[a])
d[1].set_parent()
d[1].set_value()
min_diff = d[1].get_min_diff()
print(min_diff)


class Node:

	def __init__(self, num, data):
		self.num = num
		self.data = data
		self.arcs = set()
		self.parent = None
		self.done = False
		self.treesum = data

	def __str__(self):
		return '{ num: ' + str(self.num) + ', data: ' + str(self.data) + ', parent: ' + str(self.parent) + ', arcs: ' + str(self.arcs) + ' }'

	def __repr__(self):
		return str(self.num)
N = int(input())
data = list(map(int, input().split(' ')))
total = sum(data)
nodes = [Node(i, data[i]) for i in range(N)]
for i in range(N - 1):
	(u, v) = map(int, input().split(' '))
	nodes[u - 1].arcs.add(nodes[v - 1])
	nodes[v - 1].arcs.add(nodes[u - 1])
mini = total
stack = [nodes[0]]
while len(stack) > 0:
	curnode = stack[-1]
	if curnode.done:
		for child in curnode.arcs:
			curnode.treesum += child.treesum
		mini = min(mini, abs(total - curnode.treesum - curnode.treesum))
		stack.pop()
	else:
		for child in curnode.arcs:
			child.parent = curnode
			child.arcs.discard(child.parent)
			stack.append(child)
		curnode.done = True
print(mini)


from collections import namedtuple, defaultdict, deque
n = int(input().strip())
data = [0] + [int(x) for x in input().strip().split(' ')]
total_sum = sum(data)
min_diff = total_sum
sums = {}
children = defaultdict(set)
for _ in range(n - 1):
	(u, v) = [int(x) for x in input().strip().split(' ')]
	children[v].add(u)
	children[u].add(v)
stack = deque([-1])
while stack:
	node = stack.pop()
	if node > 0:
		sums[node] = data[node] + sum((sums[child] for child in children[node]))
		min_diff = min(min_diff, abs(total_sum - sums[node] - sums[node]))
	else:
		node = -node
		stack.append(node)
		for child in children[node]:
			children[child].remove(node)
			stack.append(-child)
print(min_diff)


from collections import defaultdict
values = {}
edges = defaultdict(list)

def get_total_sum(root, visited=None):
	visited = set([])
	total = 0
	stack = [root]
	while len(stack) > 0:
		node = stack.pop()
		total += values[node]
		visited.add(node)
		stack.extend([c for c in edges[node] if c not in visited])
	return total

def sum_dfs(root, total_sum):
	min_d = float('inf')
	visited = set([])
	completed = set([])
	stack = [root]
	desc_sums = {}
	while len(stack) > 0:
		node = stack[-1]
		if node in visited:
			stack.pop()
			desc_sum = values[node] + sum([desc_sums[c] for c in edges[node] if c in completed])
			desc_sums[node] = desc_sum
			other = total_sum - desc_sum
			d = abs(other - desc_sum)
			if d < min_d:
				min_d = d
			completed.add(node)
		else:
			stack.extend([c for c in edges[node] if c not in visited])
			visited.add(node)
	return min_d
n = int(input())
values = {i + 1: int(v) for (i, v) in enumerate(input().split())}
for i in range(n - 1):
	(u, v) = map(int, input().split())
	edges[u].append(v)
	edges[v].append(u)
total_sum = get_total_sum(1)
min_d = sum_dfs(1, total_sum)
print(min_d)


import sys

class Vertex:

	def __init__(self, key, val):
		self.key = key
		self.val = val
		self.visited = False
		self.connectedTo = {}
		self.pred = None

	def addNeighbor(self, nbr, weight=0):
		self.connectedTo[nbr] = weight

	def setVisited(self, state=True):
		self.visited = state

	def setPred(self, pred):
		self.pred = pred

	def getConnections(self):
		return self.connectedTo.keys()

	def getVisited(self):
		return self.visited

	def getPred(self):
		return self.pred

	def __str__(self):
		return ' value: ' + str(self.val)

class Graph:

	def __init__(self):
		self.vertices = {}
		self.numVertices = 0

	def addVertex(self, key, val):
		self.numVertices += 1
		newVertex = Vertex(key, val)
		self.vertices[key] = newVertex
		return newVertex

	def getVertex(self, key):
		if key in self.vertices:
			return self.vertices[key]
		else:
			return None

	def addEdge(self, f_co, t_co, cost=0):
		if f_co in self.vertices and t_co in self.vertices:
			self.vertices[f_co].addNeighbor(self.vertices[t_co], cost)
			self.vertices[t_co].addNeighbor(self.vertices[f_co], cost)

	def getVertices(self):
		return list(self.vertices.keys())

	def __iter__(self):
		return iter(self.vertices.values())

def dfs(g, start):
	stack = []
	stack2 = []
	ans = sys.maxsize
	stack.append(g.getVertex(start))
	while len(stack) != 0:
		a = stack.pop()
		a.setVisited()
		for i in a.getConnections():
			if i.getVisited() == False:
				i.setPred(a)
				stack.append(i)
				stack2.append(i)
	while len(stack2) != 0:
		a = stack2.pop()
		for i in a.getConnections():
			if i != a.pred:
				a.val += i.val
		ans = min(ans, abs(total - 2 * a.val))
	return ans
g = Graph()
n_vert = int(input().strip())
i = 1
total = 0
for val in input().split():
	g.addVertex(i, int(val))
	i += 1
	total += int(val)
for _ in range(n_vert - 1):
	(u, v) = [int(i) for i in input().split()]
	g.addEdge(u, v)
ans = dfs(g, 1)
print(ans)


__author__ = 'chrisgreening'
import sys
sys.setrecursionlimit(100000)
n = int(input().strip())
d = [0] + [int(x) for x in input().strip().split(' ')]
total = sum(d)
children = [[] for i in range(n + 1)]
totals = [0] * (n + 1)
visited = set()

def totalize(node):
	global best
	visited.add(node)
	total = d[node]
	for child in children[node]:
		if not child in visited:
			child_total = totalize(child)
			total += child_total
	totals[node] = total
	return total

def totalize2(node):
	global best
	frontier = [(node, None)]
	while len(frontier) > 0:
		(front, parent) = (frontier[-1][0], frontier[-1][1])
		if not front in visited:
			for child in children[front]:
				if not child in visited:
					frontier.append((child, front))
		else:
			totals[front] += d[front]
			if parent != None:
				totals[parent] += totals[front]
			frontier.pop()
		visited.add(front)
root = -1
for _ in range(n - 1):
	(parent, child) = [int(i) for i in input().strip().split(' ')]
	if root == -1:
		root = parent
	children[parent].append(child)
	children[child].append(parent)
totalize2(root)
best = total
for i in range(1, n + 1):
	if abs(total - 2 * totals[i]) < best:
		best = abs(total - 2 * totals[i])
print(best)


n = int(input())
Arr = [int(m) for m in input().strip().split()]
Vert = []
for i in range(n - 1):
	v = [int(m) - 1 for m in input().strip().split()]
	Vert.append(v)
Connections = [[] for m in range(n)]
for i in Vert:
	Connections[i[0]].append(i[1])
	Connections[i[1]].append(i[0])
Visited = [False for m in range(n)]
Jobstack = [0]
SumOrderStack = []
while len(Jobstack) > 0:
	ActiveInd = Jobstack.pop()
	SumOrderStack.append(ActiveInd)
	Visited[ActiveInd] = True
	for i in Connections[ActiveInd]:
		if not Visited[i]:
			Jobstack.append(i)
CumSum = [0 for m in range(n)]
for i in range(n):
	ActiveInd = SumOrderStack.pop()
	CumSum[ActiveInd] += Arr[ActiveInd]
	for i in Connections[ActiveInd]:
		CumSum[ActiveInd] += CumSum[i]
TreeSum = sum(Arr)
print(min([int(abs(m - TreeSum / 2) * 2) for m in CumSum]))


n = int(input())
data = [int(x) for x in input().split()]
edge = [[] for _ in range(n)]
for _ in range(n - 1):
	(u, v) = (int(x) for x in input().split())
	edge[u - 1].append(v - 1)
	edge[v - 1].append(u - 1)
leafs = [u for u in range(n) if len(edge[u]) == 1]
total = sum(data)
result = total
for i in range(n - 1):
	u = leafs[i + 1]
	result = min(result, abs(total - data[u] * 2))
	for v in edge[u]:
		data[v] += data[u]
		edge[v].remove(u)
		if len(edge[v]) == 1:
			leafs.append(v)
print(result)


class Graph:

	def __init__(self, weight, root):
		self.weight = weight
		self.root = root

class Vertex:

	def __init__(self, index, data):
		self.index = index
		self.data = data
		self.running_sum = data
		self.edges = []

	def add_edge(self, v):
		self.edges.append(v)
		v.edges.append(self)

def build_tree():
	N = int(input().strip())
	data = [int(val) for val in input().strip().split(' ')]
	vertices = [Vertex(i, data[i]) for i in range(len(data))]
	weight = 0
	for vertex in vertices:
		weight += vertex.data
	for _ in range(N - 1):
		(u, v) = map(int, input().strip().split(' '))
		vertices[u - 1].add_edge(vertices[v - 1])
	graph = Graph(weight, vertices[0])
	return graph

def dfs(graph):
	root = graph.root
	first_stack = [root]
	second_stack = [root]
	visited = {root.index: root}
	mn = graph.weight - root.running_sum
	while first_stack != []:
		n = first_stack.pop()
		for neighbor in n.edges:
			if not visited.get(neighbor.index):
				visited[neighbor.index] = neighbor
				first_stack.append(neighbor)
				second_stack.append(neighbor)
	visited = {root.index: root}
	mn = graph.weight - root.running_sum
	while second_stack != []:
		n = second_stack.pop()
		visited[n.index] = n
		for neighbor in n.edges:
			if not visited.get(neighbor.index):
				neighbor.running_sum += n.running_sum
		diff = abs(graph.weight - 2 * n.running_sum)
		if diff < mn:
			mn = diff
	print(mn)
graph = build_tree()
dfs(graph)


from collections import deque
n = int(input())
values = [int(x) for x in input().split(' ')]
total = sum(values)
best = 100000000
graph = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split(' '))
	graph[a - 1] += [b - 1]
	graph[b - 1] += [a - 1]
nextNodes = deque()
nextNodes.append(0)
nodesByDepth = [[0]]
parents = {}
sums = {}
visited = set()
while nextNodes:
	for _ in nodesByDepth[-1]:
		node = nextNodes.popleft()
		visited.add(node)
		for child in graph[node]:
			if child not in visited:
				nextNodes.append(child)
				parents[child] = node
		sums[node] = values[node]
	if nextNodes:
		nodesByDepth += [list(nextNodes)]
while nodesByDepth:
	nodes = nodesByDepth.pop()
	for node in nodes:
		if node in parents:
			sums[parents[node]] += sums[node]
for s in sums:
	side1 = total - sums[s]
	side2 = total - side1
	best = min(best, abs(side1 - side2))
print(best)


def bfs(root, graph):
	levels = [0 for i in range(len(graph))]
	parents = [None for i in range(len(graph))]
	flag = [0 for i in range(len(graph))]
	flag[root] = 1
	(queue, next_queue) = ([root], [])
	while queue:
		for node in queue:
			for child in graph[node]:
				if flag[child] == 0:
					flag[child] = 1
					levels[child] = levels[node] + 1
					parents[child] = node
					next_queue.append(child)
		(queue, next_queue) = (next_queue, [])
	return (levels, parents)

def get_tree_weights(root, graph, weights, levels, parents):
	values = [weights[node] for node in range(len(graph))]
	new_levels = [[] for level in range(max(levels) + 1)]
	for node in range(len(levels)):
		new_levels[levels[node]].append(node)
	for l in range(1, len(new_levels)):
		level = len(new_levels) - 1 - l
		for node in new_levels[level]:
			values[node] += sum((values[child] for child in graph[node] if child != parents[node]))
	return values
N = int(input())
weights = [int(w) for w in input().split()]
graph = [[] for i in range(N)]
for i in range(N - 1):
	(u, v) = input().split()
	(u, v) = (int(u) - 1, int(v) - 1)
	graph[u].append(v)
	graph[v].append(u)
root = 0
(levels, parents) = bfs(root, graph)
values = get_tree_weights(root, graph, weights, levels, parents)
t = values[root]
print(min((abs(t - 2 * t1) for t1 in values)))


from collections import defaultdict, deque
n = int(input())
data = (0,) + tuple(map(int, input().split()))
cumsum = list(data)
parent = [0, 1] + [0] * (n - 1)
conn = defaultdict(list)
for _ in range(n - 1):
	(x, y) = map(int, input().split())
	conn[x].append(y)
	conn[y].append(x)
cache = deque([1])
levelorder = []
while cache:
	i = cache.popleft()
	for j in conn[i]:
		if not parent[j]:
			cache.append(j)
			levelorder.append(j)
			parent[j] = i
for i in reversed(levelorder):
	cumsum[parent[i]] += cumsum[i]
print(min(map(abs, (cumsum[1] - 2 * x for x in cumsum[2:]))))


n = int(input())
nodes = [[int(x), int(x), 0] for x in input().split()]
for nn in range(n - 1):
	(a, b) = [int(x) - 1 for x in input().split()]
	nodes[a].append(b)
	nodes[a][2] += 1
	nodes[b].append(a)
	nodes[b][2] += 1
pendents = [x for x in range(n) if nodes[x][2] == 1]
fets = set()
while pendents:
	i = pendents.pop()
	if i == 0:
		continue
	pes = nodes[i][1]
	for v in nodes[i][3:]:
		if v not in fets:
			nodes[v][1] += pes
			nodes[v][2] -= 1
			if nodes[v][2] == 1:
				pendents.append(v)
	fets.add(i)
total = sum([nodes[i][0] for i in range(n)])
dif = [abs(total - nodes[i][1] * 2) for i in range(n)]
print(min(dif))


from collections import defaultdict, deque
import sys
sys.setrecursionlimit(100000)

def dfs():
	visited = set()
	o = []
	s = deque([1])
	while len(s):
		n = s.popleft()
		o.append(n)
		visited.add(n)
		for c in graph[n]:
			if c in visited:
				continue
			s.append(c)
	o.reverse()
	for n in o:
		depth[n] = l[n]
		for c in graph[n]:
			depth[n] += depth[c]
	return depth[1]

def calc_depth(graph, start):
	if depth[start] != -1:
		return depth[start]
	visited.add(start)
	d = l[start]
	new_nodes = graph[start] - visited
	if not new_nodes:
		depth[start] = d
		return depth[start]
	for i in new_nodes:
		d += calc_depth(graph, i)
	depth[start] = d
	return depth[start]
n = int(input())
l = [0] + [int(i) for i in input().split()]
s = sum(l)
graph = defaultdict(set)
depth = [0] * (n + 1)
visited = set()
for _ in range(n - 1):
	(i, j) = (int(i) for i in input().split())
	graph[i].add(j)
	graph[j].add(i)
dfs()
print(min((abs(s - 2 * depth[i]) for i in range(2, n + 1))))


N = int(input())
A = [int(a) for a in input().split()]
V = {i + 1: [] for i in range(N)}
for n0 in range(N - 1):
	(a, b) = [int(c) for c in input().split()]
	V[a].append(b)
	V[b].append(a)
Q = set()
for v in V:
	if len(V[v]) == 1:
		Q.add(v)
D = [0] * N
Q -= {1}
W = set()
E = set()
while len(Q) > 0:
	W.clear()
	for q in Q:
		if q == 1:
			continue
		t = V[q][0]
		V[t].remove(q)
		V[q].remove(V[q][0])
		A[t - 1] += A[q - 1]
		W.add(t)
	E.clear()
	for w in W:
		if len(V[w]) == 1:
			E.add(w)
	Q.clear()
	Q = Q | E
m = 10 ** 12
for i in range(1, len(D)):
	m = min(m, abs(A[0] - 2 * A[i]))
print(m)


n = int(input().strip())
data = list(map(int, input().strip().split()))
s = sum(data)
tree = tuple(map(lambda d: [d, [], None], data))
for _ in range(n - 1):
	(n1, n2) = map(int, input().strip().split())
	tree[n1 - 1][1].append(n2)
	tree[n2 - 1][1].append(n1)
sub_sum = [None for _ in range(n)]
st = [(1, 0, 0)]
while st:
	(n, i, p) = st.pop()
	node = tree[n - 1]
	if i == 0:
		if n != 1 and len(node[1]) <= 1:
			node[2] = node[0]
		else:
			st.append((n, 1, p))
			st.extend(map(lambda c: (c, 0, n), filter(lambda c: c != p, node[1])))
	elif i == 1:
		node[2] = sum(map(lambda m: tree[m - 1][2], filter(lambda n: n != p, node[1]))) + node[0]
from collections import deque
q = deque(map(lambda n: (n, 1), tree[0][1]))
m = s
while len(q) > 0:
	(n, p) = q.popleft()
	node = tree[n - 1]
	m = min(m, abs(s - 2 * node[2]))
	if node[2] >= s // 2:
		q.extend(map(lambda c: (c, n), filter(lambda c: c != p, node[1])))
print(m)


class Queue:

	def __init__(self):
		self.items = []

	def isEmpty(self):
		return self.items == []

	def enqueue(self, item):
		self.items.insert(0, item)

	def dequeue(self):
		return self.items.pop()

	def size(self):
		return len(self.items)
n = int(input())
adjacent = [[] for j in range(n)]
parent = [-1 for j in range(n)]
children = [[] for j in range(n)]
weight = list(map(int, input().split()))
total = [0 for j in range(n)]
visited = [False for j in range(n)]
leaves = []
for i in range(n - 1):
	(u, v) = input().split()
	(u, v) = (int(u) - 1, int(v) - 1)
	adjacent[u].append(v)
	adjacent[v].append(u)
Q = Queue()
stack = list()
Q.enqueue(0)
visited[0] = True
while not Q.isEmpty():
	vertex = Q.dequeue()
	stack.append(vertex)
	for child in adjacent[vertex]:
		if not visited[child]:
			visited[child] = True
			children[vertex].append(child)
			parent[child] = vertex
			Q.enqueue(child)
while len(stack) != 0:
	node = stack.pop()
	dad = parent[node]
	total[node] += weight[node]
	if dad >= 0:
		total[dad] += total[node]
Q.enqueue(0)
overall = total[0]
record = overall * 2
while not Q.isEmpty():
	vertex = Q.dequeue()
	for child in children[vertex]:
		score = abs(overall - 2 * total[child])
		if score < record:
			record = score
			Q.enqueue(child)
print(record)


import sys
import math
from collections import deque

class Node:

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

	def addChild(self, n):
		self.children.append(n)

	def sumChildren(self, tree):
		for c in range(len(self.children)):
			self.val += tree[self.children[c]].val

	def addChildren(self, outList):
		for c in range(len(self.children)):
			outList.append(self.children[c])

	def findCutLocation(self, tree):
		minDiff = 10000000000
		fullSum = tree[1].val
		for a in range(1, len(tree)):
			for c in range(len(tree[a].children)):
				child = tree[a].children[c]
				top = fullSum - tree[child].val
				diff = abs(top - tree[child].val)
				if diff == 0:
					return 0
				if diff < minDiff:
					minDiff = diff
		return minDiff

class Tree:

	def __init__(self, nodeValues):
		self.tree = []
		self.tree.append(Node(0, 0))
		for i in range(V):
			self.tree.append(Node(i + 1, nodeValues[i]))

	def getTree(self):
		return self.tree

	def sumAllSubtrees(self):
		visited = [False for i in range(len(self.tree) + 1)]
		stack = [1]
		while len(stack) > 0:
			v = stack[len(stack) - 1]
			if False == visited[v]:
				visited[v] = True
				self.tree[v].addChildren(stack)
			else:
				stack.pop()
				self.tree[v].sumChildren(self.tree)

	def findCutLocation(self, start):
		return self.tree[start].findCutLocation(self.tree)

class AdjacencyList:

	def __init__(self, nVert):
		self.adjList = []
		self.nVertices = nVert

	def build(self):
		self.adjList.append([])
		while True:
			try:
				(v, w) = map(int, input().split())
				m = max(v, w)
				while len(self.adjList) <= m:
					self.adjList.append([])
				self.adjList[v].append(w)
				self.adjList[w].append(v)
			except EOFError:
				break

	def createTree(self, root, tree):
		queue = deque([root])
		visited = [False for i in range(self.nVertices + 1)]
		while len(queue) > 0:
			v = queue.popleft()
			visited[v] = True
			for j in range(len(self.adjList[v])):
				child = self.adjList[v][j]
				if False == visited[child]:
					tree[v].addChild(child)
					queue.append(child)
V = int(input())
al = AdjacencyList(V)
lst = list(map(int, input().split(' ')))
if len(lst) != V:
	print('Not enough data !!\n')
	exit
tree = Tree(lst)
al.build()
al.createTree(1, tree.getTree())
tree.sumAllSubtrees()
print(tree.findCutLocation(1))


class Node:

	def __init__(self, val):
		self.val = val
		self.children = []
		self.ssum = 0
		self.depth = None

def fix_parents(root):
	Q = [root]
	while Q:
		node = Q.pop()
		for child in node.children:
			child.children.remove(node)
			Q.append(child)

def assign_depth(root):
	root.depth = 0
	Q = [root]
	while Q:
		node = Q.pop()
		for child in node.children:
			child.depth = node.depth + 1
			Q.append(child)

def assign_ssum(node):
	node.ssum = node.val + sum([child.ssum for child in node.children])

def best_cut(nodes, total):
	root = nodes[0]
	fix_parents(root)
	assign_depth(root)
	nodes.sort(key=lambda node: -node.depth)
	best = total
	for node in nodes:
		assign_ssum(node)
		best = min(best, abs(total - 2 * node.ssum))
	return best
n = int(input().strip())
vals = [int(x) for x in input().strip().split()]
nodes = [Node(val) for val in vals]
total = sum(vals)
for k in range(n - 1):
	edge = [int(x) - 1 for x in input().strip().split()]
	nodes[edge[0]].children.append(nodes[edge[1]])
	nodes[edge[1]].children.append(nodes[edge[0]])
print(best_cut(nodes, total))


N = int(input())
children = [[] for i in range(N)]
value = list(map(int, input().split()))
for i in range(N - 1):
	(frm, to) = map(int, input().split())
	children[frm - 1].append(to - 1)
	children[to - 1].append(frm - 1)
stack = [0]
while stack:
	parent = stack.pop()
	for i in children[parent]:
		children[i].remove(parent)
		stack.append(i)
tree_value = [0] * N
stack = [0]
i = 0
while i < len(stack):
	stack.extend(children[stack[i]])
	i += 1
while stack:
	parent = stack.pop()
	tree_value[parent] = sum((tree_value[x] for x in children[parent])) + value[parent]
print(min((abs(tree_value[0] - 2 * tree_value[x]) for x in range(1, N))))


def minimum_cut_tree_sums(vertex_values, edges):
	adj_list = build_adjacency_list(vertex_values, edges)
	visited = {v: False for v in adj_list}
	order = []
	children = {}
	queue = [1]
	while queue:
		vertex = queue.pop()
		visited[vertex] = True
		order.append(vertex)
		children[vertex] = [c for c in adj_list[vertex] if not visited[c]]
		queue.extend(children[vertex])
	sum_at_vertex = {}
	for vertex in order[::-1]:
		sum_at_vertex[vertex] = vertex_values[vertex - 1] + sum((sum_at_vertex[c] for c in children[vertex]))
	total = sum(vertex_values)
	return min((abs(total - 2 * s) for s in sum_at_vertex.values()))

def build_adjacency_list(vertex_values, edges):
	adj_list = {v: [] for v in range(1, len(vertex_values) + 1)}
	for (v1, v2) in edges:
		adj_list[v1].append(v2)
		adj_list[v2].append(v1)
	return adj_list
vertex_count = int(input().strip())
vertex_values = [int(v) for v in input().strip().split(' ')]
edges = [[int(_) for _ in input().split()] for _ in range(vertex_count - 1)]
print(minimum_cut_tree_sums(vertex_values, edges))


from collections import defaultdict as di
from collections import deque as dq
n = int(input())
valu = [int(x) for x in input().split()]
C = di(list)
for i in range(n):
	C[i] = []
for _ in range(n - 1):
	(a, b) = [int(x) - 1 for x in input().split()]
	C[a].append(b)
	C[b].append(a)
found = set()
que = dq()
que.append(0)
ordering = []
while que:
	node = que.popleft()
	if node in found:
		continue
	found.add(node)
	ordering.append(node)
	for ne in C[node]:
		que.append(ne)
cost = di(int)
for node in ordering[::-1]:
	cost[node] += valu[node]
	for ne in C[node]:
		cost[node] += cost[ne]
totalcost = cost[0]
mini = totalcost
for node in cost:
	mini = min(mini, abs(totalcost - 2 * cost[node]))
print(mini)


class Node(object):

	def __init__(self, i, data):
		self.id = i
		self.data = data
		self.connected = set()
		self.parent = None
		self.children = set()
		self.sum = 0

	def __eq__(self, other):
		return self.id == other.id

	def __lt__(self, other):
		return self.id < other.id

	def __hash__(self):
		return hash(self.id)

	def connect(self, other):
		self.connected.add(other)
		other.connected.add(self)

def treeify(root):
	stack = [root]
	while len(stack) > 0:
		node = stack.pop()
		node.children = node.connected.copy()
		node.connected = None
		node.children.discard(node.parent)
		for child in node.children:
			child.parent = node
			stack.append(child)
	return root

def calc_sum(node):
	stack = [node]
	node.sum = 0
	while len(stack) > 0:
		n = stack.pop()
		node.sum += n.data
		for child in n.children:
			if child.sum > 0:
				node.sum += child.sum
			else:
				stack.append(child)
n = int(input().strip())
data = [int(x) for x in input().split()]
i = 1
tree = []
for d in data:
	tree.append(Node(i, d))
	i += 1
for _ in range(n - 1):
	(n1, n2) = (int(x) for x in input().split())
	tree[n1 - 1].connect(tree[n2 - 1])
root = treeify(tree[0])
for node in tree:
	calc_sum(node)
sums = [abs(2 * node.sum - tree[0].sum) for node in tree]
print(min(sums))


import collections
n = int(input().strip())
d = dict(((idx + 1, int(v)) for (idx, v) in enumerate(input().strip().split())))
tree = collections.defaultdict(list)
for i in range(n - 1):
	(a, b) = [int(_) for _ in input().strip().split()]
	tree[a].append(b)
	tree[b].append(a)
all_sum = sum(d.values())
sums = []
stack = collections.deque()
post = collections.deque()
stack.append(1)
seen = set([])
while stack:
	v = stack.pop()
	post.append(v)
	seen.add(v)
	pure_children = []
	for child in tree[v]:
		if child not in seen:
			stack.append(child)
			pure_children.append(child)
	tree[v] = pure_children
min_diff = all_sum
while post:
	v = post.pop()
	if tree[v]:
		s = sum((d[c] for c in tree[v]))
		d[v] += s
	diff = abs(all_sum - 2 * d[v])
	if diff < min_diff:
		min_diff = diff
print(min_diff)


edges = []
n = int(input().strip())
d_list = list(map(int, input().strip().split()))
while True:
	try:
		(u, v) = list(map(int, input().strip().split()))
		edges.append((u, v))
	except EOFError:
		break
graph = {}
for edge in edges:
	u = edge[0]
	v = edge[1]
	if u not in graph:
		graph[u] = {'data': d_list[u - 1], 'edges': [], 'total_data': 0}
	if v not in graph:
		graph[v] = {'data': d_list[v - 1], 'edges': [], 'total_data': 0}
	graph[u]['edges'].append(v)
	graph[v]['edges'].append(u)

def dfs(v, visited):
	stack1 = []
	stack2 = []
	stack1.append({'id': v, 'parent': None})
	while stack1:
		vertex = stack1.pop()
		stack2.append(vertex)
		v = vertex['id']
		visited.add(v)
		for u in graph[v]['edges']:
			if u not in visited:
				stack1.append({'id': u, 'parent': v})
	while stack2:
		vertex = stack2.pop()
		v = vertex['id']
		p = vertex['parent']
		data = graph[v]['data']
		graph[v]['total_data'] += data
		if p:
			graph[p]['total_data'] += graph[v]['total_data']

def bfs_minimize(source, tree_total):
	q = []
	visited = set()
	q.append(source)
	min_diff = float('inf')
	while q:
		v = q.pop(0)
		visited.add(v)
		for u in graph[v]['edges']:
			if u not in visited:
				com1 = tree_total - graph[u]['total_data']
				com2 = graph[u]['total_data']
				diff = abs(com1 - com2)
				min_diff = min(diff, min_diff)
				q.append(u)
	return min_diff
root = 1
dfs(root, set())
tree_total = graph[root]['total_data']
min_diff = bfs_minimize(root, tree_total)
print(min_diff)


from collections import defaultdict
n = int(input())
data = list(map(int, input().split(' ')))
adj = defaultdict(set)
for _ in range(n - 1):
	(a, b) = map(int, input().split(' '))
	adj[a].add(b)
	adj[b].add(a)
seen = set()
datasum = defaultdict(int)
stack = [(1, None)]
while len(stack) != 0:
	if stack[-1][0] == 'UPDATE':
		(_, node, parent) = stack.pop()
		datasum[parent] += datasum[node]
	else:
		(node, parent) = stack.pop()
		seen.add(node)
		datasum[node] += data[node - 1]
		stack.append(('UPDATE', node, parent))
		stack.extend(((n, node) for n in adj[node] if not n in seen))
total = datasum[1]
min_diff = 2 ** 64
for (n, s) in datasum.items():
	min_diff = min(min_diff, abs(total - 2 * s))
print(min_diff)