You are given a tree consisting exactly of $n$ vertices. Tree is a connected undirected graph with $n-1$ edges. Each vertex $v$ of this tree has a value $a_v$ assigned to it.

Let $dist(x, y)$ be the distance between the vertices $x$ and $y$. The distance between the vertices is the number of edges on the simple path between them.

Let's define the cost of the tree as the following value: firstly, let's fix some vertex of the tree. Let it be $v$. Then the cost of the tree is $\sum\limits_{i = 1}^{n} dist(i, v) \cdot a_i$.

Your task is to calculate the maximum possible cost of the tree if you can choose $v$ arbitrarily.


-----Input-----

The first line contains one integer $n$, the number of vertices in the tree ($1 \le n \le 2 \cdot 10^5$).

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2 \cdot 10^5$), where $a_i$ is the value of the vertex $i$.

Each of the next $n - 1$ lines describes an edge of the tree. Edge $i$ is denoted by two integers $u_i$ and $v_i$, the labels of vertices it connects ($1 \le u_i, v_i \le n$, $u_i \ne v_i$).

It is guaranteed that the given edges form a tree.


-----Output-----

Print one integer — the maximum possible cost of the tree if you can choose any vertex as $v$.


-----Examples-----
Input
8
9 4 1 7 10 1 6 5
1 2
2 3
1 4
1 5
5 6
5 7
5 8

Output
121

Input
1
1337

Output
0



-----Note-----

Picture corresponding to the first example: [Image]

You can choose the vertex $3$ as a root, then the answer will be $2 \cdot 9 + 1 \cdot 4 + 0 \cdot 1 + 3 \cdot 7 + 3 \cdot 10 + 4 \cdot 1 + 4 \cdot 6 + 4 \cdot 5 = 18 + 4 + 0 + 21 + 30 + 4 + 24 + 20 = 121$.

In the second example tree consists only of one vertex so the answer is always $0$.

Difficulty: HARD
Tags: Tree algorithms

Dynamic programming

Graph traversal
Skill types: Dynamic programming

Starter code:

Solutions:
from sys import stdin, setrecursionlimit
n = int(stdin.readline())
ay = [int(x) for x in stdin.readline().split()]
graph = [set() for x in range(n)]
for e in range(n - 1):
	(a, b) = [int(x) - 1 for x in stdin.readline().split()]
	graph[a].add(b)
	graph[b].add(a)
dists = {}
child = {}
bruh = sum(ay)
path = [(0, 0)]
for (x, p) in path:
	for y in graph[x]:
		if y != p:
			path.append((y, x))
for (x, parent) in path[::-1]:
	total = 0
	children = ay[x]
	for v in graph[x]:
		if v != parent:
			(c, sm) = (child[v], dists[v])
			children += c
			total += sm + c
	dists[x] = total
	child[x] = children
(b2, b3) = (child[0], dists[0])
for (x, parent) in path:
	for v in graph[x]:
		if v != parent:
			dists[v] = dists[x] + bruh - child[v] * 2
print(max([dists[y] for y in range(n)]))


import sys
from collections import deque
from types import GeneratorType
sys.setrecursionlimit(200000)
input = sys.stdin.readline

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
n = int(input())
val = [int(i) for i in input().split()]
tree = [[] for i in range(n + 1)]
dp = [0 for i in range(n + 1)]
s = [0 for i in range(n + 1)]
ans = [0 for i in range(n + 1)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	tree[a].append(b)
	tree[b].append(a)

@bootstrap
def dfs1(node, dist, pd):
	for child in tree[node]:
		if child == pd:
			continue
		yield dfs1(child, dist + 1, node)
		dp[node] += dp[child]
		s[node] += s[child]
	dp[node] += val[node - 1] * dist
	s[node] += val[node - 1]
	yield dp[node]
dfs1(1, 0, 1)
q = deque()
ans[1] = dp[1]
for node in tree[1]:
	q.append((node, 1))
while len(q) > 0:
	(node, pd) = q.popleft()
	sub_dp = ans[pd] - (dp[node] + s[node])
	added = s[1] - s[node]
	ans[node] = sub_dp + added + dp[node]
	for child in tree[node]:
		if child == pd:
			continue
		q.append((child, node))
print(max(ans))


import traceback
import sys
sys.setrecursionlimit(200010)
try:
	n = int(input())
	a = [0]
	a.extend(list(map(int, input().split())))
	D = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(e1, e2) = map(int, input().split())
		D[e1].append(e2)
		D[e2].append(e1)
	visited = [False for i in range(n + 1)]
	cost = [a[i] for i in range(n + 1)]
	parent = [0 for i in range(n + 1)]
	val = 0

	def dfs(s, depth):
		global visited
		global cost
		global val
		global a
		global D
		stack = [(s, depth)]
		while stack:
			(s, depth) = stack[-1]
			if visited[s]:
				stack.pop()
				cost[parent[s]] += cost[s]
				continue
			else:
				visited[s] = True
				val += depth * a[s]
			for i in D[s]:
				if not visited[i]:
					parent[i] = s
					stack.append((i, depth + 1))
	dfs(1, 0)
	max_cost = val
	visited = [False for i in range(n + 1)]
	cost[0] = sum(a)

	def trav(s, some_val):
		global cost
		global visited
		global max_cost
		global D
		stack = [(s, some_val)]
		while stack:
			(s, some_val) = stack.pop()
			visited[s] = True
			if some_val > max_cost:
				max_cost = some_val
			for i in D[s]:
				if not visited[i]:
					stack.append((i, some_val + (cost[0] - cost[i]) - cost[i]))
	trav(1, val)
	print(max_cost)
except Exception as ex:
	traceback.print_tb(ex.__traceback__)
	print(ex)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')

def main():
	n = N()
	arr = [0] + RLL()
	gp = [[] for _ in range(n + 1)]
	for _ in range(n - 1):
		(f, t) = RL()
		gp[f].append(t)
		gp[t].append(f)
	q = [(1, 0, 0)]
	par = [0] * (n + 1)
	now = 0
	rec = [0] * (n + 1)
	sm = [0] * (n + 1)
	while q:
		(nd, st, dp) = q.pop()
		if st == 0:
			now += 1
			q.append((nd, 1, dp))
			for nex in gp[nd]:
				if nex == par[nd]:
					continue
				par[nex] = nd
				q.append((nex, 0, dp + 1))
		else:
			rec[nd] += dp * arr[nd]
			rec[par[nd]] += rec[nd]
			sm[nd] += arr[nd]
			sm[par[nd]] += sm[nd]
	q = [(1, 0)]
	res = rec[1]
	ret = res
	while q:
		(nd, st) = q.pop()
		if st == 0:
			if nd != 1:
				res -= sm[nd]
				res += sm[par[nd]] - sm[nd]
				sm[par[nd]] -= sm[nd]
				sm[nd] += sm[par[nd]]
				ret = max(res, ret)
			q.append((nd, 1))
			for nex in gp[nd]:
				if nex == par[nd]:
					continue
				q.append((nex, 0))
		elif nd != 1:
			sm[nd] -= sm[par[nd]]
			sm[par[nd]] += sm[nd]
			res -= sm[par[nd]] - sm[nd]
			res += sm[nd]
	print(ret)
main()


import io, os
from collections import deque
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

class Node:

	def __init__(self, val):
		self.val = int(val)
		self.cul = 0
		self.child = set()
		self.path = {}

	def __str__(self):
		return f'{self.val} {self.child} {self.path}'
n = int(input())
a = list(map(Node, input().split()))
su = 0
for i in a:
	su += i.val
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	a[u - 1].child.add(v)
	a[v - 1].child.add(u)
st = [1]
while len(st):
	x = st[-1]
	if not len(a[x - 1].child):
		curr = a[st.pop() - 1].val + a[x - 1].cul
		if len(st):
			a[x - 1].path[st[-1]] = su - a[x - 1].val - sum(a[x - 1].path.values())
			a[st[-1] - 1].path[x] = curr
			a[st[-1] - 1].cul += curr
	else:
		y = a[x - 1].child.pop()
		a[y - 1].child.remove(x)
		st.append(y)
(curr, visi, ans) = (deque([1]), {1}, 0)
while len(curr):
	x = curr.popleft()
	for y in a[x - 1].path:
		if y not in visi:
			ans += a[x - 1].path[y]
			visi.add(y)
			curr.append(y)
(maxi, val) = (ans, [0] * n)
val[0] = ans
(curr, visi) = (deque([1]), {1})
while len(curr):
	x = curr.popleft()
	for y in a[x - 1].path:
		if y not in visi:
			val[y - 1] = val[x - 1] - a[x - 1].path[y] + a[y - 1].path[x]
			maxi = max(maxi, val[y - 1])
			visi.add(y)
			curr.append(y)
print(maxi)


from collections import defaultdict
import sys, threading

def work():
	sys.setrecursionlimit(1 << 18)

	def fun(u, level, p):
		l[1] += level * arr[u - 1]
		summ[u] = arr[u - 1]
		for i in graph[u]:
			if i != p:
				fun(i, level + 1, u)
				summ[u] += summ[i]

	def fun2(u, p):
		for i in graph[u]:
			if i != p:
				l[i] = l[u] + s - 2 * summ[i]
				fun2(i, u)
	n = int(input())
	n1 = n
	arr = [int(x) for x in input().split()]
	graph = defaultdict(list)
	while n1 - 1:
		n1 -= 1
		(u, v) = [int(x) for x in input().split()]
		graph[u].append(v)
		graph[v].append(u)
	s = 0
	for i in arr:
		s += i
	summ = [0] * (n + 1)
	l = [0] * (n + 1)
	fun(1, 0, 0)
	fun2(1, 0)
	print(max(l))
sys.setrecursionlimit(200050)
threading.stack_size(80000000)
thread = threading.Thread(target=work)
thread.start()


from functools import *
from operator import *
import sys, threading

def work():
	sys.setrecursionlimit(1 << 18)
	n = int(input())
	a = [0] + list(map(int, input().split()))
	tota = sum(a)
	adj = [[] for _ in range(n + 1)]
	totsz = [0] * (n + 1)
	totw = [0] * (n + 1)

	def dfs(u, p):
		totsz[u] = a[u]
		for v in adj[u]:
			if v == p:
				continue
			dfs(v, u)
			totsz[u] += totsz[v]
			totw[u] += totw[v] + totsz[v]

	def dfs2(u, p, w):
		totw[u] += w
		for v in adj[u]:
			if v == p:
				continue
			dfs2(v, u, totw[u] - totw[v] - totsz[v] + tota - totsz[v])
	for _ in range(n - 1):
		(u, v) = list(map(int, input().split()))
		adj[u].append(v)
		adj[v].append(u)
	dfs(1, 0)
	dfs2(1, 0, 0)
	print(max(totw))

def __starting_point():
	sys.setrecursionlimit(200050)
	threading.stack_size(80000000)
	thread = threading.Thread(target=work)
	thread.start()
__starting_point()


import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType
from collections import defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
sys.setrecursionlimit(2 * 10 ** 5)
ans = 0

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

@bootstrap
def dfs(now, lay, fa):
	SUM[now] = 0
	NUM[now] = C[now]
	for to in A[now]:
		if to != fa:
			yield dfs(to, lay + 1, now)
			SUM[now] += SUM[to]
			SUM[now] += NUM[to]
			NUM[now] += NUM[to]
	yield

@bootstrap
def change(now, fa):
	global ans
	ans = max(ans, SUM[now])
	for to in A[now]:
		if to != fa:
			SUM[now] -= SUM[to]
			SUM[now] -= NUM[to]
			NUM[now] -= NUM[to]
			NUM[to] += NUM[now]
			SUM[to] += SUM[now]
			SUM[to] += NUM[now]
			yield change(to, now)
			SUM[to] -= SUM[now]
			SUM[to] -= NUM[now]
			NUM[to] -= NUM[now]
			NUM[now] += NUM[to]
			SUM[now] += SUM[to]
			SUM[now] += NUM[to]
	yield
n = int(input())
A = [[] for i in range(n + 1)]
C = [0] + list(map(int, input().split()))
NUM = [0] * (n + 1)
SUM = [0] * (n + 1)
for i in range(n - 1):
	(x, y) = map(int, input().split())
	A[x].append(y)
	A[y].append(x)
dfs(1, 0, 0)
change(1, 0)
print(ans)


import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType
from collections import defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
sys.setrecursionlimit(2 * 10 ** 5)

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

@bootstrap
def dfs(u, p):
	for j in adj[u]:
		if j != p:
			yield dfs(j, u)
			f[u] += f[j] + res[j]
			res[u] += res[j]
	res[u] += b[u - 1]
	yield

@bootstrap
def dfs2(u, p, val):
	for j in adj[u]:
		if j != p:
			yield dfs2(j, u, f[u] - (f[j] + res[j]) + val + (s - res[u]))
	ans[u] = f[u] + val + (s - res[u])
	yield
n = int(input())
b = list(map(int, input().split()))
s = sum(b)
adj = [[] for i in range(n + 1)]
for j in range(n - 1):
	(u, v) = map(int, input().split())
	adj[u].append(v)
	adj[v].append(u)
f = [0] * (n + 1)
res = [0] * (n + 1)
dfs(1, 0)
ans = [0] * (n + 1)
dfs2(1, 0, 0)
print(max(ans[1:]))


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import *
from copy import *
from collections import deque
from collections import Counter as counter
from itertools import combinations as comb
from itertools import permutations as permutate
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for pp in range(t):
		solve(pp)

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

@iterative
def dfs(v, visited, st, sum, par):
	visited[st] = 1
	for i in v[st]:
		if visited[i] == 0:
			ok = (yield dfs(v, visited, i, sum, par))
			par[i] = st
			sum[st] += sum[i]
	yield True

def bfs(g, st):
	visited = [-1] * len(g)
	visited[st] = 0
	queue = deque([])
	queue.append(st)
	new = []
	while len(queue) != 0:
		s = queue.popleft()
		new.append(s)
		for i in g[s]:
			if visited[i] == -1:
				visited[i] = visited[s] + 1
				queue.append(i)
	return visited

def solve(case):
	n = int(inp())
	val = lis()
	g = [[] for i in range(n)]
	for i in range(n - 1):
		(a, b) = sep()
		a -= 1
		b -= 1
		g[a].append(b)
		g[b].append(a)
	a = deepcopy(val)
	vis = [False] * n
	par = [-1] * n
	dfs(g, vis, 0, val, par)
	currans = 0
	dist = bfs(g, 0)
	for i in range(n):
		currans += a[i] * dist[i]
	ans = currans
	ss = sum(a)
	q = []
	q.append((0, currans))
	while len(q) != 0:
		s = q.pop()
		currans = s[1]
		s = s[0]
		for i in g[s]:
			if i == par[s]:
				continue
			temp = currans - val[i] + (ss - val[i])
			ans = max(ans, temp)
			q.append((i, temp))
	print(ans)
testcase(1)


import sys
import io, os
input = sys.stdin.buffer.readline
n = int(input())
A = list(map(int, input().split()))
g = [[] for _ in range(n)]
for i in range(n - 1):
	(u, v) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	g[u].append(v)
	g[v].append(u)
s = []
s.append(0)
parent = [-1] * n
dist = [0] * n
order = []
while s:
	v = s.pop()
	order.append(v)
	for u in g[v]:
		if u == parent[v]:
			continue
		parent[u] = v
		dist[u] = dist[v] + 1
		s.append(u)
order.reverse()
dp = [0] * n
res = 0
for v in order:
	dp[v] += A[v]
	res += A[v] * dist[v]
	if parent[v] != -1:
		dp[parent[v]] += dp[v]
ans = [0] * n
ans[0] = res
for v in reversed(order):
	for u in g[v]:
		if u == parent[v]:
			continue
		res = ans[v]
		res -= dp[u]
		dp[v] -= dp[u]
		res += dp[v]
		ans[u] = res
		dp[v] += dp[u]
		dp[u] += dp[v] - dp[u]
print(max(ans))


from collections import defaultdict
from sys import stdin, setrecursionlimit
import threading
input = stdin.buffer.readline

def work():
	res = 0
	ans = 0
	setrecursionlimit(1 << 18)
	n = int(input())
	a = list(map(int, input().split()))
	a.insert(0, 0)
	graph = defaultdict(list)
	dist = dict()
	for v in range(n - 1):
		(a1, b) = map(int, input().split())
		graph[a1].append(b)
		graph[b].append(a1)

	def dfs(v, par, h=0):
		nonlocal res
		res += h * a[v]
		dist[v] = a[v]
		for node in graph[v]:
			if node != par:
				dfs(node, v, h + 1)
				dist[v] += dist[node]

	def dfs2(v, par):
		nonlocal ans, res
		ans = max(ans, res)
		for node in graph[v]:
			if node != par:
				res -= dist[node]
				dist[v] -= dist[node]
				res += dist[v]
				dist[node] += dist[v]
				dfs2(node, v)
				dist[node] -= dist[v]
				res -= dist[v]
				dist[v] += dist[node]
				res += dist[node]
	dfs(1, -1)
	dfs2(1, -1)
	print(ans)
setrecursionlimit(300050)
threading.stack_size(100000000)
thread = threading.Thread(target=work)
thread.start()