You are given a tree consisting of $n$ vertices. A tree is a connected undirected graph with $n-1$ edges. Each vertex $v$ of this tree has a color assigned to it ($a_v = 1$ if the vertex $v$ is white and $0$ if the vertex $v$ is black).

You have to solve the following problem for each vertex $v$: what is the maximum difference between the number of white and the number of black vertices you can obtain if you choose some subtree of the given tree that contains the vertex $v$? The subtree of the tree is the connected subgraph of the given tree. More formally, if you choose the subtree that contains $cnt_w$ white vertices and $cnt_b$ black vertices, you have to maximize $cnt_w - cnt_b$.


-----Input-----

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

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 1$), where $a_i$ is the color of the $i$-th vertex.

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 $n$ integers $res_1, res_2, \dots, res_n$, where $res_i$ is the maximum possible difference between the number of white and black vertices in some subtree that contains the vertex $i$.


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

Output
2 2 2 2 2 1 1 0 2 

Input
4
0 0 1 0
1 2
1 3
1 4

Output
0 -1 1 -1 



-----Note-----

The first example is shown below:

[Image]

The black vertices have bold borders.

In the second example, the best subtree for vertices $2, 3$ and $4$ are vertices $2, 3$ and $4$ correspondingly. And the best subtree for the vertex $1$ is the subtree consisting of vertices $1$ and $3$.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Graph algorithms

Graph traversal

Dynamic programming


Solutions:
from math import factorial
from collections import Counter, defaultdict
from heapq import heapify, heappop, heappush
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')

def RL():
	return 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 = 1000000007
INF = float('inf')
from types import GeneratorType

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

def main():
	n = N()
	arr = list(RL())
	gp = defaultdict(list)
	for i in range(n - 1):
		(a, b) = RL()
		gp[a].append(b)
		gp[b].append(a)
	dp = [0] * (n + 1)
	ret = [0] * (n + 1)

	@bootstrap
	def dfs1(node, par):
		dp[node] = arr[node - 1] if arr[node - 1] == 1 else -1
		for nex in gp[node]:
			if nex == par:
				continue
			yield dfs1(nex, node)
			if dp[nex] > 0:
				dp[node] += dp[nex]
		yield None

	@bootstrap
	def dfs2(node, par):
		ret[node] = dp[node]
		for nex in gp[node]:
			if nex == par:
				continue
			dp[node] -= max(0, dp[nex])
			dp[nex] += max(0, dp[node])
			yield dfs2(nex, node)
			dp[nex] -= max(0, dp[node])
			dp[node] += max(0, dp[nex])
		yield None
	dfs1(1, 0)
	dfs2(1, 0)
	print(' '.join([str(i) for i in ret[1:]]))
main()


def main():
	n = int(input())
	a = list(map(int, input().split()))
	g = [list() for _ in range(n)]
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		g[u - 1].append(v - 1)
		g[v - 1].append(u - 1)
	st = [x * 2 - 1 for x in a] + [0]
	p = [-1] * n
	q = [0]
	while q:
		v = q.pop()
		for x in g[v]:
			if x == p[v]:
				continue
			p[x] = v
			q.append(x)
	seen = [0] * n
	q = [0]
	while q:
		v = q[-1]
		if seen[v]:
			q.pop()
			if st[v] > 0:
				st[p[v]] += st[v]
		else:
			for x in g[v]:
				if x == p[v]:
					continue
				q.append(x)
		seen[v] = 1
	seen = [0] * n
	q = [0]
	while q:
		v = q.pop()
		for x in g[v]:
			if x == p[v]:
				continue
			c = st[v]
			if st[x] > 0:
				c -= st[x]
			if c > 0:
				st[x] += c
			q.append(x)
	return st[:n]
print(*main())


import sys
input = lambda : sys.stdin.readline().rstrip()
n = int(input())
A = [int(i) for i in input().split()]
edge = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	edge[a - 1].append(b - 1)
	edge[b - 1].append(a - 1)
Ans = []
inf = 10 ** 6
Par = [inf] * n
Par[0] = -1
Deg = [0] * n
Deg[0] = 0
Chk = [0]
while Chk:
	c = Chk.pop()
	for next in edge[c]:
		if Par[next] == inf:
			Par[next] = c
			Deg[next] += 1
			Chk.append(next)
from collections import deque
TS = list((v for v in range(n) if Deg[v] == 0))
D = deque(TS)
while D:
	v = D.popleft()
	for t in edge[v]:
		if t != Par[v]:
			Deg[t] -= 1
			if Deg[t] == 0:
				D.append(t)
				TS.append(t)
C = [0] * n
for i in reversed(range(n)):
	v = TS[i]
	if A[v] == 1:
		C[v] += 1
	else:
		C[v] -= 1
	if Par[v] != -1:
		C[Par[v]] += max(0, C[v])
D = [0] * n
for i in range(n):
	v = TS[i]
	cur = max(0, D[v])
	for g in edge[v]:
		if g != Par[v]:
			cur += max(0, C[g])
	if A[v] == 1:
		cur += 1
	else:
		cur -= 1
	for g in edge[v]:
		if g != Par[v]:
			D[g] += cur - max(0, C[g])
Ans = [0] * n
for i in range(n):
	Ans[i] = C[i] + max(0, D[i])
print(*Ans)


import sys
input = sys.stdin.readline
from collections import deque
N = int(input())
COL = [int(a) for a in input().split()]
X = [[] for i in range(N)]
for i in range(N - 1):
	(x, y) = map(int, input().split())
	X[x - 1].append(y - 1)
	X[y - 1].append(x - 1)
P = [-1] * N
Q = deque([0])
R = []
while Q:
	i = deque.popleft(Q)
	R.append(i)
	for a in X[i]:
		if a != P[i]:
			P[a] = i
			X[a].remove(i)
			deque.append(Q, a)
unit = 0
merge = lambda a, b: max(a, 0) + max(b, 0)
adj_bu = lambda a, i: a + 1 if COL[i] else a - 1
adj_td = lambda a, i: a + 1 if COL[P[i]] else a - 1
ans = lambda i: BU[i] + max(TD[i], 0)
BU = [unit] * N
TD = [unit] * N
for i in R[1:][::-1]:
	BU[i] = adj_bu(BU[i], i)
	p = P[i]
	BU[p] = merge(BU[p], BU[i])
BU[R[0]] = adj_bu(BU[R[0]], R[0])
AX = [0] * N
for i in R:
	ac = unit
	for j in X[i]:
		AX[j] = ac
		ac = merge(ac, BU[j])
	ac = unit
	for j in X[i][::-1]:
		AX[j] = merge(AX[j], ac)
		TD[j] = adj_td(merge(TD[i], AX[j]), j)
		ac = merge(ac, BU[j])
ANS = [ans(i) for i in range(N)]
print(*ANS)


import sys
input = sys.stdin.readline
N = int(input())
C = list(map(int, input().split()))
T = [[] for _ in range(N)]
edges = []
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	edges.append([a, b])
	T[a].append(b)
	T[b].append(a)
root = [0] * N
root[0] = -1
rank = [0] * N
Q = [0]
visited = {0}
ra = 1
while Q:
	P = []
	for i in Q:
		for j in T[i]:
			if j in visited:
				continue
			rank[j] = ra
			root[j] = i
			visited.add(j)
			P.append(j)
	Q = P
	ra += 1
rankk = [[rank[i], i] for i in range(N)]
rankk.sort()
D = [0] * N
for i in reversed(range(1, N)):
	k = rankk[i][1]
	if C[k] == 0:
		D[k] -= 1
	else:
		D[k] += 1
	D[root[k]] += max(0, D[k])
if C[0] == 0:
	D[0] -= 1
else:
	D[0] += 1
for i in range(1, N):
	k = rankk[i][1]
	D[k] = max(D[k], min(D[k], 0) + D[root[k]])
print(*D)


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 deque
n = int(input())
wt = list(map(int, input().split()))
e = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	e[a - 1].append(b - 1)
	e[b - 1].append(a - 1)
(q, seq) = (deque([0]), [])
p = [-1] * n
p[0] = 0
while q:
	cur = q.popleft()
	seq.append(cur)
	for nex in e[cur]:
		if nex == p[cur]:
			continue
		q.append(nex)
		p[nex] = cur
seq.reverse()
dp = [0] * n
for cur in seq:
	for nex in e[cur]:
		if nex == p[cur]:
			continue
		dp[cur] += max(0, dp[nex])
	dp[cur] += 1 if wt[cur] else -1
seq.reverse()
dp2 = [0] * n
for cur in seq:
	if cur == p[cur]:
		dp2[cur] = dp[cur]
	else:
		cost = 0
		if dp[cur] < 0:
			cost = dp2[p[cur]]
		else:
			cost = dp2[p[cur]] - dp[cur]
		dp2[cur] = dp[cur] + max(0, cost)
print(*dp2)


import sys
input = sys.stdin.readline
INF = 10 ** 18
N = int(input())
Color = list(map(int, input().split()))
graph = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)
Score = [{} for _ in range(N)]
Max = [-INF] * N
for (i, c) in enumerate(Color):
	Max[i] = 1 if c else -1

def dfs(s):
	stack = [s]
	Ind = [0] * N
	while stack:
		p = stack[-1]
		if Ind[p] == len(graph[p]):
			stack.pop()
			if stack:
				par = stack[-1]
				Max[par] += max(Max[p], 0)
		elif len(stack) > 1 and graph[p][Ind[p]] == stack[-2]:
			Ind[p] += 1
		else:
			stack.append(graph[p][Ind[p]])
			Ind[p] += 1
ans = [-INF] * N

def dfs2(s):
	ans[s] = Max[s]
	stack = [s]
	Ind = [0] * N
	while stack:
		p = stack[-1]
		if Ind[p] == len(graph[p]):
			stack.pop()
		elif len(stack) > 1 and graph[p][Ind[p]] == stack[-2]:
			Ind[p] += 1
		else:
			ch = graph[p][Ind[p]]
			ans[ch] = max(ans[p] - max(Max[ch], 0), 0) + Max[ch]
			stack.append(ch)
			Ind[p] += 1
dfs(0)
dfs2(0)
print(*ans)


def main():
	import sys
	input = sys.stdin.readline
	N = int(input())
	A = list(map(int, input().split()))
	adj = [[] for _ in range(N + 1)]
	for _ in range(N - 1):
		(a, b) = map(int, input().split())
		adj[a].append(b)
		adj[b].append(a)

	def op(a, b):
		return a + max(0, b)
	ident_op = 0

	def cum_merge(a, b):
		return a + b
	ident_cum_merge = 0

	def Rerooting(adj):
		N = len(adj) - 1
		st = [1]
		seen = [0] * (N + 1)
		seen[1] = 1
		par = [0] * (N + 1)
		child = [[] for _ in range(N + 1)]
		seq = []
		while st:
			v = st.pop()
			seq.append(v)
			for u in adj[v]:
				if not seen[u]:
					seen[u] = 1
					par[u] = v
					child[v].append(u)
					st.append(u)
		seq.reverse()
		dp = [ident_op] * (N + 1)
		left = [ident_cum_merge] * (N + 1)
		right = [ident_cum_merge] * (N + 1)
		for v in seq:
			tmp = ident_cum_merge
			for u in child[v]:
				left[u] = tmp
				tmp = op(tmp, dp[u])
			tmp = ident_cum_merge
			for u in reversed(child[v]):
				right[u] = tmp
				tmp = op(tmp, dp[u])
			dp[v] = tmp
			if A[v - 1]:
				dp[v] += 1
			else:
				dp[v] -= 1
		seq.reverse()
		from_par = [ident_op] * (N + 1)
		for v in seq:
			if v == 1:
				continue
			from_par[v] = op(cum_merge(left[v], right[v]), from_par[par[v]])
			if A[par[v] - 1]:
				from_par[v] += 1
			else:
				from_par[v] -= 1
			dp[v] = op(dp[v], from_par[v])
		return dp
	dp = Rerooting(adj)
	print(*dp[1:])
main()


from types import GeneratorType

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
import math
from bisect import bisect_left, bisect_right
from sys import stdin, stdout, setrecursionlimit
from collections import Counter
input = lambda : stdin.readline().strip()
print = stdout.write
n = int(input())
ls = list(map(int, input().split()))
children = {}
for i in range(1, n + 1):
	children[i] = []
for i in range(n - 1):
	(a, b) = map(int, input().split())
	children[a].append(b)
	children[b].append(a)
parent = [-1]
ans = [-1]
for i in range(1, n + 1):
	parent.append(-1)
	ans.append(-1)
visited = [False]
for i in range(1, n + 1):
	visited.append(False)

@bootstrap
def dfs(node):
	visited[node] = True
	ans[node] = 1 if ls[node - 1] else -1
	for i in children[node]:
		if not visited[i]:
			parent[i] = node
			tmp = (yield dfs(i))
			if tmp > 0:
				ans[node] += tmp
	ans[node] = max(ans[node], 1 if ls[node - 1] else -1)
	yield ans[node]
dfs(1)
visited = [False]
for i in range(1, n + 1):
	visited.append(False)

@bootstrap
def dfs(node):
	visited[node] = True
	if node != 1:
		ans[node] = max(ans[node], ans[parent[node]] if ans[node] >= 0 else ans[parent[node]] - 1)
	for i in children[node]:
		if not visited[i]:
			yield dfs(i)
	yield
dfs(1)
for i in range(1, n + 1):
	print(str(ans[i]) + ' ')
print('\n')


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		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 = self.os.read(self._fd, max(self.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 = self.os.read(self._fd, max(self.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:
			self.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')
import time
start_time = time.time()
import collections as col
import math, string
from functools import reduce

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
MOD = 10 ** 9 + 7

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

def solve():
	N = getInt()
	A = [0] + getInts()
	for (i, a) in enumerate(A):
		if a == 0:
			A[i] = -1
	graph = col.defaultdict(set)
	for n in range(N - 1):
		(U, V) = getInts()
		graph[U].add(V)
		graph[V].add(U)
	dp = [0 for n in range(N + 1)]
	ans = [0 for n in range(N + 1)]

	@bootstrap
	def dfs(node, parent=0):
		dp[node] = A[node]
		for neighbour in graph[node]:
			if neighbour == parent:
				continue
			yield dfs(neighbour, node)
			dp[node] += max(dp[neighbour], 0)
		yield

	@bootstrap
	def reroot(node, parent=0):
		ans[node] = dp[node]
		for neighbour in graph[node]:
			if neighbour == parent:
				continue
			dp[node] -= max(0, dp[neighbour])
			dp[neighbour] += max(0, dp[node])
			yield reroot(neighbour, node)
			dp[neighbour] -= max(0, dp[node])
			dp[node] += max(0, dp[neighbour])
		yield
	dfs(1)
	reroot(1)
	print(*ans[1:])
	return
solve()


import sys
input = sys.stdin.readline
getint = lambda : int(input())
getints = lambda : [int(a) for a in input().split()]
n = getint()
colors = [i * 2 - 1 for i in getints()]
tree = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = getints()
	tree[a - 1].append(b - 1)
	tree[b - 1].append(a - 1)
parent = [-1] * n
order = [0]
for i in range(n):
	node = order[i]
	for child in tree[node]:
		if child == parent[node]:
			continue
		parent[child] = node
		order.append(child)
order.reverse()
points = [0] * n
for node in order:
	children = tree[node]
	point = colors[node]
	for child in children:
		if child == parent[node]:
			continue
		point += max(0, points[child])
	points[node] = point
order.reverse()
for node in order:
	children = tree[node]
	for child in children:
		if child == parent[node]:
			continue
		points[child] += max(0, points[node] - max(0, points[child]))
print(' '.join([str(i) for i in points]))


import sys, threading
N = 2 * 10 ** 5 + 1
l = [[] for x in range(N)]
dp = [0 for i in range(N)]

def dfs1(v, color, par=-1):
	dp[v] = color[v]
	for i in l[v]:
		if i == par:
			continue
		dfs1(i, color, v)
		dp[v] += max(0, dp[i])

def dfs2(v, color, ans, par=-1):
	ans[v] = dp[v]
	for i in l[v]:
		if i == par:
			continue
		dp[v] -= max(0, dp[i])
		dp[i] += max(0, dp[v])
		dfs2(i, color, ans, v)
		dp[i] -= max(0, dp[v])
		dp[v] += max(0, dp[i])

def main():
	n = int(input())
	color = [int(x) for x in input().split()]
	for i in range(n):
		if color[i] == 0:
			color[i] = -1
	for i in range(n - 1):
		(a, b) = input().split()
		a = int(a)
		b = int(b)
		a -= 1
		b -= 1
		l[a].append(b)
		l[b].append(a)
	ans = [0 for i in range(n)]
	dfs1(0, color)
	dfs2(0, color, ans)
	print(*ans)
sys.setrecursionlimit(10 ** 6)
threading.stack_size(10 ** 8)
t = threading.Thread(target=main)
t.start()
t.join()


from collections import defaultdict

class ReRooting:

	def __init__(self, f, g, merge, ie):
		self.tree = defaultdict(list)
		self.f = f
		self.g = g
		self.merge = merge
		self.ie = ie
		self.dp = defaultdict(dict)

	def add_edge(self, u, v):
		self.tree[u].append(v)
		self.tree[v].append(u)

	def __dfs1(self, u, p):
		o = []
		s = [(u, -1)]
		while s:
			(u, p) = s.pop()
			o.append((u, p))
			for v in self.tree[u]:
				if v == p:
					continue
				s.append((v, u))
		for (u, p) in reversed(o):
			r = self.ie
			for v in self.tree[u]:
				if v == p:
					continue
				r = self.merge(r, self.f(self.dp[u][v], v))
			self.dp[p][u] = self.g(r, u)

	def __dfs2(self, u, p, a):
		s = [(u, p, a)]
		while s:
			(u, p, a) = s.pop()
			self.dp[u][p] = a
			pl = [0] * (len(self.tree[u]) + 1)
			pl[0] = self.ie
			for (i, v) in enumerate(self.tree[u]):
				pl[i + 1] = self.merge(pl[i], self.f(self.dp[u][v], v))
			pr = [0] * (len(self.tree[u]) + 1)
			pr[-1] = self.ie
			for (i, v) in reversed(list(enumerate(self.tree[u]))):
				pr[i] = self.merge(pr[i + 1], self.f(self.dp[u][v], v))
			for (i, v) in enumerate(self.tree[u]):
				if v == p:
					continue
				r = self.merge(pl[i], pr[i + 1])
				s.append((v, u, self.g(r, u)))

	def build(self, root=1):
		self.__dfs1(root, -1)
		self.__dfs2(root, -1, self.ie)

	def slv(self, u):
		r = self.ie
		for v in self.tree[u]:
			r = self.merge(r, self.f(self.dp[u][v], v))
		return self.g(r, u)

def atcoder_dp_dp_v():
	(N, M) = map(int, input().split())
	XY = [list(map(int, input().split())) for _ in range(N - 1)]
	f = lambda x, y: x
	g = lambda x, y: x + 1
	merge = lambda x, y: x * y % M
	rr = ReRooting(f, g, merge, 1)
	for (x, y) in XY:
		rr.add_edge(x, y)
	rr.build()
	for u in range(1, N + 1):
		print(rr.slv(u) - 1)

def atcoder_abc60_f():
	N = int(input())
	AB = [list(map(int, input().split())) for _ in range(N - 1)]
	M = 10 ** 9 + 7
	from functools import reduce
	fact = [1]
	for i in range(1, 10 ** 6):
		fact.append(fact[-1] * i % M)

	def f(x, _):
		c = x[0]
		s = x[1]
		c *= pow(fact[s], M - 2, M)
		c %= M
		return (c, s)

	def g(x, _):
		c = x[0]
		s = x[1]
		c *= fact[s]
		c %= M
		return (c, s + 1)

	def merge(x, y):
		return (x[0] * y[0] % M, x[1] + y[1])
	rr = ReRooting(f, g, merge, (1, 0))
	for (a, b) in AB:
		rr.add_edge(a, b)
	rr.build()
	for u in range(1, N + 1):
		print(rr.slv(u)[0])

def codeforces_1324_f():
	import sys
	input = sys.stdin.buffer.readline
	from operator import add
	N = int(input())
	A = list(map(int, input().split()))
	UV = [list(map(int, input().split())) for _ in range(N - 1)]
	A = [1 if A[i] == 1 else -1 for i in range(N)]

	def f(x, _):
		return max(0, x)

	def g(x, v):
		return x + A[v - 1]
	rr = ReRooting(f, g, add, 0)
	for (u, v) in UV:
		rr.add_edge(u, v)
	rr.build()
	ans = []
	for u in range(1, N + 1):
		ans.append(rr.slv(u))
	print(*ans)
codeforces_1324_f()


from collections import deque
import sys
input = sys.stdin.readline

def bfs(root):
	queue = [root]
	queue = deque(queue)
	vis = [0] * n
	while len(queue) != 0:
		element = queue.popleft()
		vis[element] = 1
		for i in graph[element]:
			if vis[i] == 0:
				queue.append(i)
				vis[i] = 1
				parent[i] = element

def dfs(root):
	stack = [root]
	vis = [0] * n
	vis[root] = 1
	stack2 = []
	while len(stack) != 0:
		element = stack.pop()
		vis[element] = 1
		stack2.append(element)
		for i in graph[element]:
			if vis[i] == 0:
				vis[i] = 1
				stack.append(i)
	while len(stack2) != 0:
		element = stack2.pop()
		m = 0
		for i in graph[element]:
			if i != parent[element]:
				m += max(0, values[i])
		if l[element] == 0:
			values[element] = m - 1
		else:
			values[element] = m + 1

def reroot(root):
	stack = [root]
	vis = [0] * n
	while len(stack) != 0:
		element = stack[-1]
		if vis[element] == 1:
			stack.pop()
			if parent[element] == -1:
				continue
			values[element] -= max(0, values[parent[element]])
			values[parent[element]] += max(0, values[element])
			continue
		vis[element] = 1
		for i in graph[element]:
			if vis[i] == 0:
				stack.append(i)
		if parent[element] == -1:
			continue
		values[parent[element]] -= max(0, values[element])
		values[element] += max(0, values[parent[element]])
		ans[element] = values[element]
n = int(input())
l = list(map(int, input().split()))
graph = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)
values = [-n] * n
parent = [-1] * n
bfs(0)
dfs(0)
ans = [-1] * n
ans[0] = values[0]
reroot(0)
print(*ans)


import io
import os
from collections import defaultdict
from functools import lru_cache

def dfs(g, root, preorder=None, postorder=None):
	stack = [root]
	parent = {root: None}
	seen = set()
	while stack:
		u = stack.pop()
		p = parent[u]
		if u not in seen:
			if preorder:
				preorder(u, p)
			stack.append(u)
			seen.add(u)
			for v in reversed(g[u]):
				if v != p:
					stack.append(v)
					parent[v] = u
		elif postorder:
			postorder(u, p)

def solve(N, A, g):

	@lru_cache(maxsize=None)
	def subTreeMaxDiff(u, p):
		ans = 1 if A[u] else -1
		for v in g[u]:
			if v != p:
				ans += max(0, subTreeMaxDiff(v, u))
		return ans
	dfs(g, 0, None, subTreeMaxDiff)
	cache = {}

	def maxDiff(u, p):
		ans = subTreeMaxDiff(u, p)
		if p is not None:
			ans += max(0, cache[p] - max(0, subTreeMaxDiff(u, p)))
		cache[u] = ans
	dfs(g, 0, maxDiff)
	out = []
	for u in range(N):
		out.append(str(cache[u]))
	return ' '.join(out)
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(N,) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
g = defaultdict(list)
for i in range(N - 1):
	(u, v) = (int(x) - 1 for x in input().split())
	g[u].append(v)
	g[v].append(u)
ans = solve(N, A, g)
print(ans)


import sys
from array import array
import typing as Tp

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def gen_dfstree(adj: Tp.List[Tp.List[int]], root: int):
	(dfstree, par) = ([], [-1] * len(adj))
	stack = [root]
	while stack:
		v = stack.pop()
		dfstree.append(v)
		for dest in adj[v]:
			if dest == par[v]:
				continue
			par[dest] = v
			stack.append(dest)
	return (dfstree, par)

def solve1(order: Tp.Iterable[int], par: Tp.List[int], *args):
	color = args[0]
	dp = [0] * len(par)
	for v in order:
		dp[v] += 1 if color[v] else -1
		if par[v] != -1 and dp[v] > 0:
			dp[par[v]] += dp[v]
	return dp

def solve2(order: Tp.Iterable[int], par: Tp.List[int], *args):
	(dp, adj) = args
	dp_par = [0] * len(par)
	ans = [0] * len(par)
	for v in order:
		ans[v] = val = dp[v] + dp_par[v]
		for dest in adj[v]:
			if dest == par[v]:
				continue
			dp_par[dest] = max(0, val - max(0, dp[dest]))
	return ans

def main():
	n = int(input())
	a = list(map(int, input().split()))
	adj = [[] for _ in range(n)]
	for (u, v) in (map(int, input().split()) for _ in range(n - 1)):
		adj[u - 1].append(v - 1)
		adj[v - 1].append(u - 1)
	(dfstree, par) = gen_dfstree(adj, 0)
	dp = solve1(reversed(dfstree), par, a)
	ans = solve2(dfstree, par, dp, adj)
	print(*ans)
main()


from collections import defaultdict, Counter, deque
import threading
import sys

def ri():
	return int(input())

def rs():
	return input()

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

def rls():
	return list(input().split())
threading.stack_size(10 ** 8)
sys.setrecursionlimit(10 ** 6)

def main():
	n = ri()
	a = [0] + rl()
	for i in range(n + 1):
		if i != 0 and a[i] == 0:
			a[i] = -1
	g = defaultdict(list)
	for _ in range(n - 1):
		(u, v) = rl()
		g[u].append(v)
		g[v].append(u)
	par = [-1] * (n + 1)
	dp = [0] * (n + 1)

	def d1(cn, p):
		par[cn] = p
		dp[cn] = a[cn]
		for nn in g[cn]:
			if nn != p:
				dp[cn] += max(0, d1(nn, cn))
		return dp[cn]
	d1(1, 0)

	def d2(cn, p):
		if cn != 1:
			if dp[cn] > 0:
				res[cn] = max(res[par[cn]], dp[cn])
			else:
				res[cn] = max(res[par[cn]] + dp[cn], dp[cn])
		for nn in g[cn]:
			if nn != p:
				d2(nn, cn)
	res = [0] * (n + 1)
	res[1] = dp[1]
	d2(1, 0)
	print(*res[1:])
	pass
threading.Thread(target=main).start()


import os, sys
from io import BytesIO, IOBase
from collections import defaultdict
from copy import deepcopy

def main():
	n = int(input())
	a = list(map(lambda y: 1 if y == '1' else -1, input().split()))
	path = defaultdict(list)
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		path[u].append(v)
		path[v].append(u)
	path1 = deepcopy(path)
	sub = [0] * (n + 1)
	st = [1]
	while len(st):
		if not len(path[st[-1]]):
			x = st.pop()
			sub[x] += a[x - 1]
			if len(st):
				if sub[x] > 0:
					sub[st[-1]] += sub[x]
			continue
		i = path[st[-1]].pop()
		path[i].remove(st[-1])
		st.append(i)
	ans = [sub[1]] + [0] * (n - 1)
	st = [1]
	while len(st):
		if not len(path1[st[-1]]):
			st.pop()
			continue
		i = path1[st[-1]].pop()
		path1[i].remove(st[-1])
		if sub[i] >= 0:
			ans[i - 1] = max(sub[i], ans[st[-1] - 1])
		else:
			ans[i - 1] = max(ans[st[-1] - 1] + sub[i], sub[i])
		st.append(i)
	print(' '.join(map(str, ans)))
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')
main()


import sys
sys.setrecursionlimit(2000000)
import threading
threading.stack_size(2 ** 26)

def main():
	n = int(input())
	s = list(map(int, input().split()))
	for (i, x) in enumerate(s):
		if x == 0:
			s[i] = -1
	go = [[] for _ in range(n)]
	for _ in range(n - 1):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		go[a].append(b)
		go[b].append(a)
	gone = [False] * n

	def f(p):
		gone[p] = True
		SUM = 0
		for x in go[p]:
			if gone[x] == False:
				SUM += max(0, f(x))
		s[p] += SUM
		return s[p]

	def g(p):
		gone[p] = True
		for x in go[p]:
			if gone[x] == False:
				s[x] += max(0, s[p] - max(0, s[x]))
				g(x)
	f(0)
	gone = [False] * n
	g(0)
	print(' '.join((str(x) for x in s)))
threading.Thread(target=main).start()


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 sys
from collections import deque

def solve():
	input = sys.stdin.readline
	N = int(input())
	A = [int(a) for a in input().split()]
	for (i, a) in enumerate(A):
		if a == 0:
			A[i] = -1
	Edge = [[] for _ in range(N)]
	for _ in range(N - 1):
		(x, y) = map(int, input().split())
		Edge[x - 1].append(y - 1)
		Edge[y - 1].append(x - 1)
	par = [-1] * N
	son = [[] for _ in range(N)]
	sonNum = [0] * N
	q = deque()
	q.append((0, 0))
	while q:
		(now, pre) = q.popleft()
		par[now] = pre
		if now != pre:
			son[pre].append(now)
			sonNum[pre] += 1
		for nextN in Edge[now]:
			if nextN != pre:
				q.append((nextN, now))
	for (i, s) in enumerate(son):
		if s == []:
			q.append((par[i], A[i]))
	under = [A[i] for i in range(N)]
	visited = [0] * N
	while q:
		(now, v) = q.popleft()
		under[now] = max(under[now], v + under[now])
		visited[now] += 1
		if visited[now] == sonNum[now] and now > 0:
			visited[now] = True
			q.append((par[now], under[now]))
	for s in son[0]:
		q.append((s, under[0]))
	while q:
		(now, v) = q.popleft()
		if under[now] >= 0:
			under[now] = max(under[now], v)
		else:
			under[now] = max(under[now] + v, under[now])
		for s in son[now]:
			q.append((s, under[now]))
	print(' '.join(map(str, under)))
	return 0
solve()


import sys
input = sys.stdin.readline
import collections
from collections import defaultdict

def dfs():
	q = collections.deque([(1, 0)])
	while q:
		(v, par_val) = q.pop()
		tmp = {}
		for nxt_v in graph[v]:
			if nxt_v == par[v]:
				tmp[nxt_v] = par_val
			else:
				tmp[nxt_v] = ans[nxt_v]
		res = a[v - 1]
		for nxt_v in tmp:
			if res + tmp[nxt_v] > res:
				res = res + tmp[nxt_v]
		dist2[v] = res
		for nxt_v in graph[v]:
			if nxt_v == par[v]:
				continue
			else:
				q.append((nxt_v, res - max(tmp[nxt_v], 0)))
n = int(input())
a = [int(i) for i in input().split() if i != '\n']
for i in range(len(a)):
	if a[i] == 0:
		a[i] = -1
graph = defaultdict(list)
for i in range(n - 1):
	(u, v) = map(int, input().split())
	graph[u].append(v)
	graph[v].append(u)
ans = [0] * (n + 1)
OBSERVE = 0
CHECK = 1
stack = [(OBSERVE, 1, 0)]
par = {1: 0}
dist2 = [0] * (n + 1)
while len(stack):
	(state, vertex, parent) = stack.pop()
	if state == OBSERVE:
		stack.append((CHECK, vertex, parent))
		for child in graph[vertex]:
			if child != parent:
				stack.append((OBSERVE, child, vertex))
				par[child] = vertex
	else:
		res = a[vertex - 1]
		for child in graph[vertex]:
			if child == parent:
				continue
			elif child != parent:
				if res + ans[child] > res:
					res = res + ans[child]
		ans[vertex] = res
dfs()
print(*dist2[1:])


import os
import sys
from io import BytesIO, IOBase

def dfs1(graph, dp, a, start=0):
	n = len(graph)
	(visited, finished) = ([False] * n, [False] * n)
	stack = [start]
	while stack:
		start = stack[-1]
		if not visited[start]:
			visited[start] = True
			for child in graph[start]:
				if not visited[child]:
					stack.append(child)
		else:
			stack.pop()
			dp[start] += a[start]
			for child in graph[start]:
				if finished[child]:
					dp[start] += max(0, dp[child])
			finished[start] = True

def dfs2(graph, ans, a, start=0):
	n = len(graph)
	dp = [0] * n
	(visited, finished) = ([False] * n, [False] * n)
	stack = [start]
	while stack:
		start = stack[-1]
		if not visited[start]:
			visited[start] = True
			cnt = dp[start] + a[start]
			for child in graph[start]:
				if not visited[child]:
					stack.append(child)
					cnt += max(0, ans[child])
			for child in graph[start]:
				if not visited[child]:
					dp[child] = max(0, cnt - max(0, ans[child]))
					ans[child] += dp[child]
		else:
			stack.pop()
			finished[start] = True

def main():
	n = int(input())
	a = [1 if x == '1' else -1 for x in input().split()]
	graph = [[] for _ in range(n)]
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		(u, v) = (u - 1, v - 1)
		graph[u].append(v)
		graph[v].append(u)
	ans = [0] * n
	dfs1(graph, ans, a)
	dfs2(graph, ans, a)
	print(*ans)
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')
main()


from collections import defaultdict as dd
import sys
input = sys.stdin.readline

def dfs(cur, prev, par, val, d):
	st = [(cur, prev)]
	bst = []
	while st:
		(cur, prev) = st.pop()
		bst.append((cur, prev))
		par[cur] = prev
		for i in d[cur]:
			if i != prev:
				st.append((i, cur))
	while bst:
		(cur, prev) = bst.pop()
		for i in d[cur]:
			if i != prev:
				if val[i] > 0:
					val[cur] += val[i]

def dfs1(cur, prev, par, val, d):
	st = [(cur, prev)]
	while st:
		(cur, prev) = st.pop()
		if cur != 1:
			if val[cur] >= 0:
				val[cur] = max(val[cur], val[par[cur]])
			else:
				val[cur] = max(val[cur], val[par[cur]] + val[cur])
		for i in d[cur]:
			if i != prev:
				st.append((i, cur))
n = int(input())
val = [0] + list(map(int, input().split()))
for i in range(1, n + 1):
	if val[i] == 0:
		val[i] = -1
d = dd(list)
for i in range(n - 1):
	(u, v) = map(int, input().split())
	d[u].append(v)
	d[v].append(u)
par = [0] * (n + 1)
dfs(1, -1, par, val, d)
dfs1(1, -1, par, val, d)
for i in range(1, n + 1):
	print(val[i], end=' ')


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
import threading
from collections import defaultdict
threading.stack_size(10 ** 8)
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
sys.setrecursionlimit(300000)
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')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=2 ** 51, func=lambda a, b: a & b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater

def main():
	n = int(input())
	m = n - 1
	graph = defaultdict(list)
	l = list(map(int, input().split()))
	for i in range(n):
		if l[i] == 0:
			l[i] = -1
	for i in range(m):
		(a, b) = map(int, input().split())
		graph[a - 1].append(b - 1)
		graph[b - 1].append(a - 1)
	visited = [False] * n
	pre = [0] * n
	dp = [0] * n

	def dfs(v, k):
		pre[v] = k
		dp[v] = l[v]
		visited[v] = True
		for i in graph[v]:
			if visited[i] == False:
				er = dfs(i, v)
				if er >= 0:
					dp[v] += er
		return dp[v]

	def dfs1(v):
		if v != 0:
			if dp[v] > 0:
				ans[v] = max(ans[pre[v]], dp[v])
			else:
				ans[v] = max(ans[pre[v]] + dp[v], dp[v])
		visited[v] = True
		for i in graph[v]:
			if visited[i] == False:
				dfs1(i)
	dfs(0, -1)
	ans = [0] * n
	visited = [False] * n
	ans[0] = dp[0]
	dfs1(0)
	print(*ans)
t = threading.Thread(target=main)
t.start()
t.join()


def main():
	import sys
	from collections import deque
	input = sys.stdin.buffer.readline
	N = int(input())
	A = list(map(int, input().split()))
	A = [-1] + A
	adj = [[] for _ in range(N + 1)]
	for _ in range(N - 1):
		(a, b) = map(int, input().split())
		adj[a].append(b)
		adj[b].append(a)
	que = deque()
	que.append(1)
	seen = [-1] * (N + 1)
	seen[1] = 0
	par = [0] * (N + 1)
	child = [[] for _ in range(N + 1)]
	seq = []
	while que:
		v = que.popleft()
		seq.append(v)
		for u in adj[v]:
			if seen[u] == -1:
				seen[u] = seen[v] + 1
				par[u] = v
				child[v].append(u)
				que.append(u)
	seq.reverse()
	dp = [0] * (N + 1)
	for v in seq:
		for u in child[v]:
			dp[v] += dp[u]
		if A[v]:
			dp[v] += 1
		else:
			dp[v] -= 1
		if dp[v] < 0:
			dp[v] = 0
	seq.reverse()
	dp2 = [0] * (N + 1)
	for v in seq:
		for u in child[v]:
			dp2[v] += dp[u]
		if v != 1:
			dp2[v] += max(0, dp2[par[v]] - dp[v])
		if A[v]:
			dp2[v] += 1
		else:
			dp2[v] -= 1
	print(*[max(-1, ans) for ans in dp2[1:]])
main()


class Graph:

	def __init__(self, n_vertices, edges, directed=True):
		self.n_vertices = n_vertices
		self.edges = edges
		self.directed = directed

	@property
	def adj(self):
		try:
			return self._adj
		except AttributeError:
			adj = [[] for _ in range(self.n_vertices)]
			if self.directed:
				for (u, v) in self.edges:
					adj[u].append(v)
			else:
				for (u, v) in self.edges:
					adj[u].append(v)
					adj[v].append(u)
			self._adj = adj
			return adj

class RootedTree(Graph):

	def __init__(self, n_vertices, edges, root_vertex):
		self.root = root_vertex
		super().__init__(n_vertices, edges, False)

	@property
	def parent(self):
		try:
			return self._parent
		except AttributeError:
			adj = self.adj
			parent = [None] * self.n_vertices
			parent[self.root] = -1
			stack = [self.root]
			for _ in range(self.n_vertices):
				v = stack.pop()
				for u in adj[v]:
					if parent[u] is None:
						parent[u] = v
						stack.append(u)
			self._parent = parent
			return parent

	@property
	def children(self):
		try:
			return self._children
		except AttributeError:
			children = [None] * self.n_vertices
			for (v, (l, p)) in enumerate(zip(self.adj, self.parent)):
				children[v] = [u for u in l if u != p]
			self._children = children
			return children

	@property
	def dfs_order(self):
		try:
			return self._dfs_order
		except AttributeError:
			order = [None] * self.n_vertices
			children = self.children
			stack = [self.root]
			for i in range(self.n_vertices):
				v = stack.pop()
				order[i] = v
				for u in children[v]:
					stack.append(u)
			self._dfs_order = order
			return order
from functools import reduce
from itertools import accumulate, chain

def rerooting(rooted_tree, merge, identity, finalize):
	N = rooted_tree.n_vertices
	parent = rooted_tree.parent
	children = rooted_tree.children
	order = rooted_tree.dfs_order
	dp_down = [None] * N
	for v in reversed(order[1:]):
		dp_down[v] = finalize(reduce(merge, (dp_down[c] for c in children[v]), identity), v)
	dp_up = [None] * N
	dp_up[0] = identity
	for v in order:
		if len(children[v]) == 0:
			continue
		temp = (dp_up[v],) + tuple((dp_down[u] for u in children[v])) + (identity,)
		left = accumulate(temp[:-2], merge)
		right = tuple(accumulate(reversed(temp[2:]), merge))
		for (u, l, r) in zip(children[v], left, reversed(right)):
			dp_up[u] = finalize(merge(l, r), v)
	res = [None] * N
	for (v, l) in enumerate(children):
		res[v] = reduce(merge, (dp_down[u] for u in children[v]), identity)
		res[v] = finalize(merge(res[v], dp_up[v]), v)
	return res

def solve(N, A, E):
	rooted_tree = RootedTree(N, E, 0)

	def merge(x, y):
		(c1, ta1) = x
		(c2, ta2) = y
		return (c1 + c2, ta1 + ta2)

	def finalize(x, v):
		(c, ta) = x
		return (c + ta, ta + A[v])
	res = rerooting(rooted_tree, merge, (0, 0), finalize)
	return max(res)[0]
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
N = int(readline())
A = tuple(map(int, readline().split()))
t = iter(read().split())
E = tuple(((int(x) - 1, int(y) - 1) for (x, y) in zip(t, t)))
print(solve(N, A, E))


import threading
import sys
from sys import stdin
input = stdin.readline
sys.setrecursionlimit(10 ** 8)
from collections import defaultdict

def main():
	n = int(input())
	arr = list(map(int, input().split()))
	graph = [[] for _ in range(n)]
	for _ in range(n - 1):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		graph[a].append(b)
		graph[b].append(a)
	idea = {}

	def dfs(node, par):
		ans = 0
		f = False
		for nie in graph[node]:
			if nie != par:
				dfs(nie, node)
				if idea[nie] >= 0:
					ans += idea[nie]
					f = True
		ans -= 1 if arr[node] == 0 else -1
		idea[node] = ans
	dfs(0, -1)
	ans = [0] * n

	def dfs1(node, par):
		if par == -1:
			ans[node] = idea[node]
		else:
			ans[node] = idea[node] + max(0, idea[par] - (idea[node] if idea[node] >= 0 else 0))
			idea[node] += max(0, idea[par] - (idea[node] if idea[node] >= 0 else 0))
		for nie in graph[node]:
			if nie != par:
				dfs1(nie, node)
	dfs1(0, -1)
	print(*ans)
threading.stack_size(10 ** 8)
t = threading.Thread(target=main)
t.start()
t.join()


import os
import io
from collections import Counter
from collections import defaultdict
import math
import random
import heapq as hq
from math import sqrt
import sys
from functools import reduce
from collections import deque
import threading
sys.setrecursionlimit(2000000)

def input():
	return sys.stdin.readline().strip()

def iinput():
	return int(input())

def tinput():
	return input().split()

def rinput():
	return map(int, tinput())

def rlinput():
	return list(rinput())
mod = int(1000000000.0) + 7

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

def dfs1(i, dp1, a, visited, g):
	dp1[i] = 1 if a[i - 1] == 1 else -1
	visited[i] = True
	for nd in g[i]:
		if not visited[nd]:
			dfs1(nd, dp1, a, visited, g)
			dp1[i] += max(0, dp1[nd])

def dfs2(dp1, dp2, g, n):
	visited = [False] * (n + 1)
	parent = [0] * (n + 1)
	stk = [1]
	visited[1] = True
	top = 0
	while top != -1:
		node = stk.pop()
		top -= 1
		dp2[node] = dp1[node]
		if parent[node] != 0:
			val = max(0, dp2[parent[node]] - max(0, dp1[node]))
			dp2[node] += val
		for nd in g[node]:
			if not visited[nd]:
				stk.append(nd)
				visited[nd] = True
				parent[nd] = node
				top += 1

def main():
	n = iinput()
	a = rlinput()
	g = defaultdict(list)
	dp1 = [0] * (n + 1)
	dp2 = [0] * (n + 1)
	visited = [False] * (n + 1)
	for _ in range(n - 1):
		(u, v) = rinput()
		g[u].append(v)
		g[v].append(u)
	dfs1(1, dp1, a, visited, g)
	dfs2(dp1, dp2, g, n)
	dp2.pop(0)
	print(*dp2)
threading.stack_size(10 ** 8)
t = threading.Thread(target=main)
t.start()
t.join()


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):
	r = 0
	for j in adj[u]:
		if j != p:
			yield dfs(j, u)
			r += max(dp[j], 0)
	if col[u - 1]:
		dp[u] = r + 1
	else:
		dp[u] = r - 1
	yield

@bootstrap
def dfs2(u, p, v):
	for j in adj[u]:
		if j != p:
			yield dfs2(j, u, dp[u] - max(0, dp[j]) + max(0, v))
	val[u] = dp[u] + max(0, v)
	yield
n = int(input())
col = list(map(int, input().split()))
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)
dp = [0] * (n + 1)
dfs(1, 0)
val = [0] * (n + 1)
dfs2(1, 0, 0)
print(*val[1:])


from __future__ import division, print_function
_interactive = False

def main():
	n = int(input())
	color = [(-1, 1)[int(t)] for t in input().split()]
	g = array_of(list, n)
	for _ in range(n - 1):
		(u, v) = input_with_offset(-1)
		g[u].append(v)
		g[v].append(u)

	def solve(root):
		res = color[:]
		vis = array_of(bool, n)
		vis[root] = True

		@bootstrap
		def dfs(ver):
			for nei in g[ver]:
				if not vis[nei]:
					vis[nei] = True
					yield dfs(nei)
					res[ver] += max(0, res[nei])
			yield
		dfs(root)
		return res
	root = 0
	dp = solve(root)

	def reroot_dfs(root):
		ans = dp[:]
		vis = array_of(bool, n)
		vis[root] = True

		def reroot(v, to):
			dp[v] -= max(0, dp[to])
			dp[to] += max(0, dp[v])
			ans[to] = max(ans[to], dp[to])

		@bootstrap
		def dfs(ver):
			for nei in g[ver]:
				if not vis[nei]:
					vis[nei] = True
					reroot(ver, nei)
					yield dfs(nei)
					reroot(nei, ver)
			yield
		dfs(root)
		return ans
	ans = reroot_dfs(root)
	print(*ans)
INF = float('inf')
MOD = 10 ** 9 + 7
import os, sys, itertools
if sys.version_info[0] < 3:
	input = raw_input
	range = xrange
	filter = itertools.ifilter
	map = itertools.imap
	zip = itertools.izip
if _interactive:
	flush = sys.stdout.flush

	def printf(*args, **kwargs):
		print(*args, **kwargs)
		flush()
LOCAL = 'LOCAL_' in os.environ
debug_print = print if LOCAL else lambda *x, **y: None
if not LOCAL and (not _interactive):
	input = sys.stdin.readline

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

def input_with_offset(o):
	return [int(x) + o for x in input().split()]

def input_as_matrix(n, m):
	return [input_as_list() for _ in range(n)]

def array_of(f, *dim):
	return [array_of(f, *dim[1:]) for _ in range(dim[0])] if dim else f()
from types import GeneratorType

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
main()


from collections import Counter, defaultdict, deque
from heapq import heapify, heappush, heappop, heappushpop
from sys import stdin
import sys
sys.setrecursionlimit(2000000)
import threading
threading.stack_size(2 ** 26)

def main():
	int_inp = lambda : int(stdin.readline().strip())
	lst_inp = lambda : [int(i) for i in stdin.readline().strip().split(' ')]
	str_inp = lambda : stdin.readline().strip()
	n = int_inp()
	a = lst_inp()
	G = defaultdict(list)
	for _ in range(n - 1):
		(u, v) = lst_inp()
		G[u - 1].append(v - 1)
		G[v - 1].append(u - 1)

	def dfs(u, G, a, vis, scores):
		vis[u] = 1
		scores[u] = 1 if a[u] == 1 else -1
		for v in G[u]:
			if not vis[v]:
				dfs(v, G, a, vis, scores)
				scores[u] += scores[v] if scores[v] > 0 else 0
	vis = [0] * n
	scores = [0] * n
	dfs(0, G, a, vis, scores)
	done = [0] * n
	Q = deque([(v, 0) for v in G[0]])
	done[0] = 1
	while Q:
		(v, u) = Q.popleft()
		scores[v] += max(0, scores[u] - max(0, scores[v]))
		done[v] = 1
		for w in G[v]:
			if not done[w]:
				Q.append((w, v))
	print(*scores)
threading.Thread(target=main).start()


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()


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

class Tree:

	def __init__(self, n, decrement=1):
		self.n = n
		self.edges = [[] for _ in range(n)]
		self.root = None
		self.size = [1] * n
		self.decrement = decrement

	def add_edge(self, u, v):
		(u, v) = (u - self.decrement, v - self.decrement)
		self.edges[u].append(v)
		self.edges[v].append(u)

	def add_edges(self, edges):
		for (u, v) in edges:
			(u, v) = (u - self.decrement, v - self.decrement)
			self.edges[u].append(v)
			self.edges[v].append(u)

	def set_root(self, root):
		root -= self.decrement
		self.depth = [-1] * self.n
		self.root = root
		self.par = [-1] * self.n
		self.depth[root] = 0
		self.order = [root]
		next_set = [root]
		while next_set:
			p = next_set.pop()
			for q in self.edges[p]:
				if self.depth[q] != -1:
					continue
				self.par[q] = p
				self.depth[q] = self.depth[p] + 1
				self.order.append(q)
				next_set.append(q)
		for p in self.order[::-1]:
			for q in self.edges[p]:
				if self.par[p] == q:
					continue
				self.size[p] += self.size[q]

	def rerooting(self, op, merge, id):
		dp1 = [id] * self.n
		dp2 = [id] * self.n
		for p in self.order[::-1]:
			t = id
			for q in self.edges[p]:
				if self.par[p] == q:
					continue
				dp2[q] = t
				t = merge(t, op(dp1[q], p, q))
			t = id
			for q in self.edges[p][::-1]:
				if self.par[p] == q:
					continue
				dp2[q] = merge(t, dp2[q])
				t = merge(t, op(dp1[q], p, q))
			dp1[p] = t
		for q in self.order[1:]:
			pq = self.par[q]
			dp2[q] = op(merge(dp2[q], dp2[pq]), q, pq)
			dp1[q] = merge(dp1[q], dp2[q])
		return dp1

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 = IOWrapper(sys.stdin)
input = sys.stdin.readline
N = int(input())
T = Tree(N)
C = list(map(int, input().split()))
for _ in range(N - 1):
	(x, y) = map(int, input().split())
	T.add_edge(x, y)
T.set_root(1)

def op(a, p, q):
	return max(a + 2 * C[q] - 1, 0)

def merge(a, b):
	return a + b
id = 0
dp = T.rerooting(op, merge, id)
res = [''] * N
for i in range(N):
	res[i] = str(dp[i] + 2 * C[i] - 1)
print(' '.join(res))


import sys
input = sys.stdin.readline
n = int(input())
c = list(map(int, input().split()))
t = [[] for _ in range(n)]
ab = []
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	ab.append([a, b])
	t[a].append(b)
	t[b].append(a)
root = [0] * n
root[0] = -1
rank = [0] * n
Q = [0]
visited = {0}
ra = 1
while Q:
	P = []
	for i in Q:
		for j in t[i]:
			if j in visited:
				continue
			rank[j] = ra
			root[j] = i
			visited.add(j)
			P.append(j)
	Q = P
	ra += 1
rankk = [[rank[i], i] for i in range(n)]
rankk.sort()
d = [0] * n
for i in range(n - 1, 0, -1):
	k = rankk[i][1]
	if c[k] == 0:
		d[k] -= 1
	else:
		d[k] += 1
	d[root[k]] += max(0, d[k])
if c[0] == 0:
	d[0] -= 1
else:
	d[0] += 1
for i in range(1, n):
	k = rankk[i][1]
	d[k] = max(d[k], min(d[k], 0) + d[root[k]])
print(*d)


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 collections import deque, defaultdict
n = int(input())
col = list(map(int, input().split()))
tree = [[] for s in range(n)]
root = 0
for s in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	tree[a].append(b)
	tree[b].append(a)
queue = deque([root])
vis = set([root])
cv = 0
pr = 1
depth = defaultdict(list)
dd = {}
while len(queue) > 0:
	v0 = queue.popleft()
	for s in tree[v0]:
		if not s in vis:
			vis.add(s)
			queue.append(s)
	pr -= 1
	depth[cv].append(v0)
	dd[v0] = cv
	if pr == 0:
		cv += 1
		pr = len(queue)
cv -= 1
dp = {}
for s in range(n):
	if col[s] == 1:
		dp[s] = 1
	else:
		dp[s] = -1
while cv >= 0:
	for s in depth[cv]:
		for node in tree[s]:
			if dd[node] < cv:
				if col[node] == 1:
					cur = 1
				else:
					cur = -1
				dp[node] = dp[node] + max(0, dp[s])
	cv -= 1
ans = [0 for s in range(n)]
ans[0] = dp[0]
queue = deque([root])
vis = set([root])
while len(queue) > 0:
	v0 = queue.popleft()
	for s in tree[v0]:
		if not s in vis:
			vis.add(s)
			queue.append(s)
			ans[s] = dp[s] + max(0, ans[v0] - max(0, dp[s]))
print(*ans)


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)]))


from collections import defaultdict
import sys
import threading
threading.stack_size(10 ** 8)
sys.setrecursionlimit(10 ** 6)
n = int(input())
size = list(map(int, input().split()))
adj = defaultdict(list)
size = [0] + size
for i in range(1, n + 1):
	size[i] = -1 if size[i] == 0 else 1

def dfs1(node, parent):
	for child in adj[node]:
		if child != parent:
			dfs1(child, node)
			size[node] += max(0, size[child])

def dfs2(node, parent):
	size[node] = max(max(0, size[node]), size[parent]) + min(size[node], 0)
	for child in adj[node]:
		if child != parent:
			dfs2(child, node)

def main():
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		adj[u].append(v)
		adj[v].append(u)
	dfs1(1, -1)
	for child in adj[1]:
		dfs2(child, 1)
	print(*size[1:])
t = threading.Thread(target=main)
t.start()
t.join()


import sys, os, io
from sys import stdin
import math
from collections import defaultdict
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right
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')
alphabets = list('abcdefghijklmnopqrstuvwxyz')
from types import GeneratorType

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

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

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 sieveForSmallestPrimeFactor():
	MAXN = 100001
	spf = [0 for i in range(MAXN)]
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, math.ceil(math.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
	return spf

def getPrimeFactorizationLOGN(x):
	spf = sieveForSmallestPrimeFactor()
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret

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

def si():
	return input()

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
	input = lambda : sys.stdin.readline().rstrip('\r\n')
n = ii()
a = li()
adj = [[] for i in range(n)]
indeg = [0] * n
for i in range(n - 1):
	(u, v) = li()
	u -= 1
	v -= 1
	indeg[u] += 1
	indeg[v] += 1
	adj[u].append(v)
	adj[v].append(u)
leaf = indeg.index(1)
dp = [0] * n

@bootstrap
def dfs(node, parent):
	ans = 0
	for kid in adj[node]:
		if kid != parent:
			x = (yield dfs(kid, node))
			ans += max(x, 0)
	ans = max(0, ans)
	if a[node]:
		ans += 1
	else:
		ans -= 1
	dp[node] = ans
	yield ans
dfs(0, -1)
leaf = 0
answer = [0] * n

@bootstrap
def dfs1(node, parent, curanswer):
	answer[node] = curanswer
	for kid in adj[node]:
		if kid != parent:
			pos = answer[node] - max(dp[kid], 0)
			yield dfs1(kid, node, max(pos, 0) + dp[kid])
	yield
dfs1(0, -1, dp[0])
print(*answer)


import sys
_INPUT_LINES = sys.stdin.read().splitlines()
input = iter(_INPUT_LINES).__next__

def go():
	n = int(input())
	a = list(map(int, input().split()))
	e = {i: set() for i in range(n)}
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		(u, v) = (u - 1, v - 1)
		e[u].add(v)
		e[v].add(u)
	ranks = [len(e[i]) for i in range(n)]
	leafs = [i for i in range(n) if ranks[i] == 1]
	index = 0
	vs = {i: {} for i in range(n)}
	done = set()
	while index < len(leafs):
		cur = leafs[index]
		mysum = sum(vs[cur].values())
		if a[cur] == 0:
			mysum -= 1
		else:
			mysum += 1
		for i in e[cur] - done:
			vs[i][cur] = max(mysum, 0)
			ranks[i] -= 1
			if ranks[i] == 1:
				leafs.append(i)
		done.add(cur)
		index += 1
	sums = [0] * n
	que = [ranks.index(0)]
	done = set()
	index = 0
	while index < len(que):
		cur = que[index]
		mysum = sum(vs[cur].values())
		if a[cur] == 0:
			mysum -= 1
		else:
			mysum += 1
		sums[cur] = mysum
		for i in e[cur] - done:
			vs[i][cur] = max(mysum - vs[cur][i], 0)
			que.append(i)
		done.add(cur)
		index += 1
	return ' '.join(map(str, sums))
for _ in range(1):
	print(go())


class Tree:

	def __init__(self, n, decrement=1):
		self.n = n
		self.edges = [[] for _ in range(n)]
		self.root = None
		self.size = [1] * n
		self.decrement = decrement

	def add_edge(self, u, v):
		(u, v) = (u - self.decrement, v - self.decrement)
		self.edges[u].append(v)
		self.edges[v].append(u)

	def add_edges(self, edges):
		for (u, v) in edges:
			(u, v) = (u - self.decrement, v - self.decrement)
			self.edges[u].append(v)
			self.edges[v].append(u)

	def set_root(self, root):
		root -= self.decrement
		self.depth = [-1] * self.n
		self.root = root
		self.par = [-1] * self.n
		self.depth[root] = 0
		self.order = [root]
		next_set = [root]
		while next_set:
			p = next_set.pop()
			for q in self.edges[p]:
				if self.depth[q] != -1:
					continue
				self.par[q] = p
				self.depth[q] = self.depth[p] + 1
				self.order.append(q)
				next_set.append(q)
		for p in self.order[::-1]:
			for q in self.edges[p]:
				if self.par[p] == q:
					continue
				self.size[p] += self.size[q]

	def rerooting(self, op, merge, id):
		dp1 = [id] * self.n
		dp2 = [id] * self.n
		for p in self.order[::-1]:
			t = id
			for q in self.edges[p]:
				if self.par[p] == q:
					continue
				dp2[q] = t
				t = merge(t, op(dp1[q], p, q))
			t = id
			for q in self.edges[p][::-1]:
				if self.par[p] == q:
					continue
				dp2[q] = merge(t, dp2[q])
				t = merge(t, op(dp1[q], p, q))
			dp1[p] = t
		for q in self.order[1:]:
			pq = self.par[q]
			dp2[q] = op(merge(dp2[q], dp2[pq]), q, pq)
			dp1[q] = merge(dp1[q], dp2[q])
		return dp1
import sys
input = sys.stdin.readline
N = int(input())
T = Tree(N)
C = list(map(int, input().split()))
for _ in range(N - 1):
	(x, y) = map(int, input().split())
	T.add_edge(x, y)
T.set_root(1)

def op(a, p, q):
	return max(a + 2 * C[q] - 1, 0)

def merge(a, b):
	return a + b
id = 0
dp = T.rerooting(op, merge, id)
res = [''] * N
for i in range(N):
	res[i] = str(dp[i] + 2 * C[i] - 1)
print(' '.join(res))


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
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)

def ctd(chr):
	return ord(chr) - ord('a')
mod = 998244353
INF = float('inf')

def main():
	n = N()
	arr = [-1] + 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]
	vis = [0] * (n + 1)
	vis[1] = 1
	par = [0] * (n + 1)
	chd = [[] for _ in range(n + 1)]
	seq = []
	for i in q:
		seq.append(i)
		for nex in gp[i]:
			if vis[nex] == 1:
				continue
			par[nex] = i
			chd[i].append(nex)
			q.append(nex)
			vis[nex] = 1
	dp = [0] * (n + 1)
	for i in seq[::-1]:
		if arr[i] == 1:
			dp[i] += 1
		else:
			dp[i] -= 1
		for nex in chd[i]:
			dp[i] += dp[nex]
		dp[i] = max(dp[i], 0)
	dp1 = [0] * (n + 1)
	for i in seq:
		for nex in chd[i]:
			dp1[i] += dp[nex]
		if i != 1:
			dp1[i] += max(dp1[par[i]] - dp[i], 0)
		if arr[i] == 1:
			dp1[i] += 1
		else:
			dp1[i] -= 1
	print(*[max(-1, i) for i in dp1[1:]])
main()


import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))
A = [-1 if a == 0 else 1 for a in A]
g = [[] for i 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
order = []
while s:
	v = s.pop()
	order.append(v)
	for u in g[v]:
		if parent[v] == u:
			continue
		parent[u] = v
		s.append(u)
order.reverse()
dp = [0] * n
for v in order:
	dp[v] += A[v]
	u = parent[v]
	if u == -1:
		continue
	dp[u] += max(0, dp[v])
ans = [0] * n
order.reverse()
for v in order:
	ans[v] = dp[v]
	for u in g[v]:
		if parent[v] == u:
			continue
		dp[u] += max(0, ans[v] - max(0, dp[u]))
print(*ans)


from sys import stdin, gettrace, setrecursionlimit
from collections import deque
if not gettrace():

	def input():
		return next(stdin)[:-1]

def main():
	n = int(input())
	aa = [int(a) for a in input().split()]
	adj = [set() for _ in range(n)]
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		adj[u - 1].add(v - 1)
		adj[v - 1].add(u - 1)
	parent = [-2] + [-1] * (n - 1)
	rtol = []
	q = deque()
	q.append(0)
	while q:
		c = q.popleft()
		rtol.append(c)
		for a in adj[c]:
			if parent[a] == -1:
				parent[a] = c
				q.append(a)
	res = [2 * a - 1 for a in aa]
	for nd in rtol[:0:-1]:
		if res[nd] > 0:
			res[parent[nd]] += res[nd]
	q = deque()
	q.append(0)
	while q:
		c = q.popleft()
		for a in adj[c]:
			if not parent[c] == a:
				if res[a] >= 0:
					res[a] = max(res[a], res[c])
				else:
					res[a] = max(res[c] - 1, -1)
				q.append(a)
	print(' '.join(map(str, res)))
main()


import sys
inp = sys.stdin.readline

def input():
	return inp().strip()

def iin():
	return int(input())

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

def dfs(adj, start=1):
	n = len(adj)
	visited = [False] * n
	first = [-1] * n
	euler = []
	srt = [start]
	parent = [-1] * n
	while srt:
		v = srt.pop()
		if visited[v]:
			euler.append(v)
			continue
		first[v] = len(euler)
		euler.append(v)
		visited[v] = True
		if parent[v] != -1:
			srt.append(parent[v])
		for u in adj[v]:
			if not visited[u]:
				parent[u] = v
				srt.append(u)
	return euler

def main():
	from collections import defaultdict
	T = 1
	while T:
		T -= 1
		n = iin()
		a = [0] + [1 if i else -1 for i in lin()]
		adj = [[] for i in range(n + 1)]
		for _ in range(n - 1):
			(i, j) = lin()
			adj[i].append(j)
			adj[j].append(i)
		path = dfs(adj)
		dp = [0] * (n + 1)
		ch = defaultdict(int)
		for i in path:
			ch[i] += 1
		done = set()
		for i in path:
			ch[i] -= 1
			done.add(i)
			if ch[i] == 0:
				sm = 0
				for j in adj[i]:
					if j not in done:
						sm += max(0, dp[j])
				dp[i] = a[i] + sm
				done.remove(i)
		ans = [0] * (n + 1)
		ans[1] = dp[1]
		l = len(path)
		for i in range(1, l):
			pv = path[i - 1]
			x = path[i]
			dp[pv] -= max(0, dp[x])
			dp[x] += max(0, dp[pv])
			ans[x] = dp[x]
		print(*ans[1:])
main()


from sys import stdin
input = lambda : stdin.readline().strip()
lin = lambda : list(map(int, input().split()))
iin = lambda : int(input())
main = lambda : map(int, input().split())
from math import ceil, sqrt, factorial, log
from collections import deque
from bisect import bisect_left

def solve():
	n = iin()
	l = lin()
	l = [1 if i == 1 else -1 for i in l]
	graph = {i: set() for i in range(n)}
	for i in range(n - 1):
		(a, b) = main()
		a -= 1
		b -= 1
		graph[a].add(b)
		graph[b].add(a)
	stack = [0]
	order = []
	papa = [-1] * n
	while stack:
		x = stack.pop()
		order.append(x)
		for i in graph[x]:
			if papa[x] != i:
				papa[i] = x
				stack.append(i)
	order.reverse()
	dp = [0] * n
	for i in order:
		dp[i] += l[i]
		p = papa[i]
		if p != -1:
			dp[p] += max(0, dp[i])
	ans = [0] * n
	order.reverse()
	for i in order:
		ans[i] = dp[i]
		for j in graph[i]:
			if papa[i] != j:
				dp[j] += max(0, ans[i] - max(0, dp[j]))
	print(*ans)
qwe = 1
for _ in range(qwe):
	solve()


class WhiteSubtree:

	def __init__(self, vertex_is_white, edges, root=1):
		self.vertex_is_white = vertex_is_white
		self.root = root
		self.adj = self.__build_adj_list__(edges)
		self.subtree_best_polarity = self.__compute_subtree_best_polarity__()
		self.score_at_nodes = self.__compute_final_score_at_nodes__()

	def __build_adj_list__(self, edges):
		n = len(self.vertex_is_white) - 1
		adj = [[] for _ in range(n + 1)]
		adj[0] = None
		for (v1, v2) in edges:
			adj[v1].append(v2)
			adj[v2].append(v1)
		return adj

	def __compute_subtree_best_polarity__(self):
		n = len(self.vertex_is_white) - 1
		subtree_best_polarity = [None for _ in range(n + 1)]
		visited = [False for _ in range(n + 1)]
		stack = [(self.root, None)]
		while len(stack) > 0:
			(u, up) = stack[-1]
			if not visited[u]:
				for v in self.adj[u]:
					if v != up:
						stack.append((v, u))
				visited[u] = True
			else:
				node_score = 1 if self.vertex_is_white[u] else -1
				for v in self.adj[u]:
					if v != up:
						node_score += max(0, subtree_best_polarity[v])
				subtree_best_polarity[u] = node_score
				stack.pop()
		return subtree_best_polarity

	def __compute_final_score_at_nodes__(self):
		subtree_best_polarity = self.subtree_best_polarity
		n = len(self.vertex_is_white) - 1
		score_at_nodes = [None for _ in range(n + 1)]
		stack = [(self.root, None, 0)]
		while len(stack) > 0:
			(u, up, contrib_from_parent) = stack.pop()
			score_at_nodes[u] = subtree_best_polarity[u] + contrib_from_parent
			for v in self.adj[u]:
				if v != up:
					contrib_to_parent = max(subtree_best_polarity[v], 0)
					stack.append((v, u, max(score_at_nodes[u] - contrib_to_parent, 0)))
		return score_at_nodes

def construct_tree():
	n = int(input())
	vertex_is_white = [int(elm.strip()) == 1 for elm in input().split()]
	vertex_is_white = [[]] + vertex_is_white
	edges = []
	for _ in range(n - 1):
		(v1, v2) = [int(elm.strip()) for elm in input().split()]
		edges.append((v1, v2))
	return WhiteSubtree(vertex_is_white, edges)
tree = construct_tree()
scores = tree.score_at_nodes[1:]
print(' '.join([str(elm) for elm in scores]))


from sys import stdin
from collections import deque
n = int(stdin.readline().strip())
a = list(map(int, stdin.readline().split()))
t = {}
for _ in range(n - 1):
	(u, v) = map(int, stdin.readline().split())
	t.setdefault(u, set()).add(v)
	t.setdefault(v, set()).add(u)
M = {}

def dfs_dn(r):
	stk = deque([(0, r)])
	s = set()
	while stk:
		(f, u) = stk.pop()
		if f:
			M[u] = 1 if a[u - 1] else -1
			for v in t[u]:
				if v in M and M[v] > 0:
					M[u] += M[v]
			continue
		stk.append((1, u))
		s.add(u)
		for v in t[u]:
			if v in s:
				continue
			stk.append((0, v))

def dfs_up(r):
	stk = deque([(r, 0)])
	s = set()
	while stk:
		(u, m) = stk.pop()
		if m > 0:
			M[u] += m
		s.add(u)
		for v in t[u]:
			if v in s:
				continue
			if M[v] > 0:
				stk.append((v, M[u] - M[v]))
			else:
				stk.append((v, M[u]))
dfs_dn(1)
dfs_up(1)
print(' '.join([str(M[i]) for i in range(1, n + 1)]))


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__
n = int(input())
a = list(map(int, input().split()))
G = [[] for i in range(n)]
for i in range(n - 1):
	(x, y) = map(int, input().split())
	(x, y) = (x - 1, y - 1)
	G[x].append(y)
	G[y].append(x)
cost = [2 * i - 1 for i in a]

def bfs1(root):
	rev = [(root, -1)]
	for i in range(n):
		(cur, par) = rev[i]
		for to in G[cur]:
			if to != par:
				rev.append((to, cur))
	for i in reversed(range(1, n)):
		(cur, par) = rev[i]
		if cost[cur] > 0:
			cost[par] += cost[cur]
cost2 = [2 * i - 1 for i in a]

def bfs2(root):
	rev = [(root, -1, 0)]
	for i in range(n):
		(cur, par, d_par) = rev[i]
		d_nxt_tmp = d_par + cost2[cur]
		tmp = []
		for to in G[cur]:
			if to != par:
				c = cost[to] if cost[to] > 0 else 0
				tmp.append(c)
		cost2[cur] += sum(tmp) + d_par
		sum1 = [0]
		for j in tmp:
			sum1.append(sum1[-1] + j)
		sum2 = [0]
		for j in reversed(tmp):
			sum2.append(sum2[-1] + j)
		m = len(sum2)
		i = 0
		for to in G[cur]:
			if to != par:
				d_nxt = d_nxt_tmp + sum1[i] + sum2[m - 2 - i]
				if d_nxt < 0:
					d_nxt = 0
				rev.append((to, cur, d_nxt))
				i += 1
root = n // 2
bfs1(root)
bfs2(root)
print(*cost2)


from collections import defaultdict
import sys
import threading
sys.setrecursionlimit(10 ** 6)
threading.stack_size(10 ** 8)
input = sys.stdin.readline
inf = 1000000000
mod = 998244353

def dfs1(now, fa):
	for to in A[now]:
		if to == fa:
			continue
		F[now] += max(0, dfs1(to, now))
	F[now] += B[now]
	return F[now]

def dfs2(now, fa):
	ANS[now] = max(ANS[now], F[now])
	for to in A[now]:
		if to == fa:
			continue
		if F[to] > 0:
			F[now] -= F[to]
		if F[now] > 0:
			F[to] += F[now]
		dfs2(to, now)
		if F[now] > 0:
			F[to] -= F[now]
		if F[to] > 0:
			F[now] += F[to]

def main():
	dfs1(0, -1)
	dfs2(0, -1)
	print(*ANS)
(n,) = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
for i in range(len(B)):
	if B[i] == 0:
		B[i] = -1
A = defaultdict(list)
F = [0] * n
ANS = [-inf] * n
for i in range(n - 1):
	(x, y) = (i - 1 for i in map(int, input().split()))
	A[x].append(y)
	A[y].append(x)
t = threading.Thread(target=main)
t.start()
t.join()


import sys
input = sys.stdin.readline
n = int(input())
A = [0] + list(map(int, input().split()))
for i in range(n + 1):
	if A[i] == 0:
		A[i] = -1
E = [[] for i in range(n + 1)]
for i in range(n - 1):
	(x, y) = map(int, input().split())
	E[x].append(y)
	E[y].append(x)
DP_C = [0] * (n + 1)
DP_G = [0] * (n + 1)
Q = [1]
USE = [0] * (n + 1)
USE[1] = 1
Q2 = []
P = [-1] * (n + 1)
SORTED = []
while Q:
	x = Q.pop()
	SORTED.append(x)
	for to in E[x]:
		if len(E[to]) == 1 and USE[to] == 0:
			SORTED.append(to)
			P[to] = x
			USE[to] = 1
		elif USE[to] == 0:
			USE[to] = 1
			Q.append(to)
			P[to] = x
for x in SORTED[::-1]:
	DP_C[x] = max(0, DP_C[x] + A[x])
	if P[x] == -1:
		continue
	DP_C[P[x]] += max(0, DP_C[x])
for x in SORTED:
	SUM = DP_G[x]
	for to in E[x]:
		if P[x] == to:
			continue
		SUM += DP_C[to]
	for to in E[x]:
		if P[x] == to:
			continue
		DP_G[to] = max(0, SUM - DP_C[to] + A[x])
ANS = []
SC = A[1]
for to in E[1]:
	SC += DP_C[to]
ANS.append(SC)
for i in range(2, n + 1):
	SC = A[i]
	SC += max(0, DP_G[i])
	for to in E[i]:
		if P[i] == to:
			continue
		SC += max(0, DP_C[to])
	ANS.append(SC)
print(*ANS)


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')
n = int(input())
tree = {1: []}
arr = [0] + [int(x) for x in input().split()]
dp = [0 for x in range(n + 1)]
for i in range(1, n + 1):
	if arr[i] == 0:
		dp[i] = -1
	else:
		dp[i] = 1
for i in range(n - 1):
	(a, b) = [int(x) for x in input().split()]
	if a not in tree:
		tree[a] = [b]
	else:
		tree[a].append(b)
	if b not in tree:
		tree[b] = [a]
	else:
		tree[b].append(a)

def dfs(graph, n, currnode):
	visited = [False for x in range(n + 1)]
	stack = [currnode]
	parent = [0 for x in range(n + 1)]
	index = [0 for x in range(n + 1)]
	while stack:
		currnode = stack[-1]
		if visited[currnode] == False:
			visited[currnode] = True
		for i in range(index[currnode], len(graph[currnode])):
			neighbour = graph[currnode][i]
			if visited[neighbour] == False:
				visited[neighbour] = True
				stack.append(neighbour)
				parent[neighbour] = currnode
				index[currnode] += 1
				break
		else:
			dp[parent[currnode]] += max(0, dp[currnode])
			stack.pop()
	return
dfs(tree, n, 1)
ans = [0 for x in range(n + 1)]
ans[1] = dp[1]

def dfs1(graph, n, currnode):
	visited = [False for x in range(n + 1)]
	stack = [currnode]
	parent = [0 for x in range(n + 1)]
	index = [0 for x in range(n + 1)]
	while stack:
		currnode = stack[-1]
		if visited[currnode] == False:
			visited[currnode] = True
		for i in range(index[currnode], len(graph[currnode])):
			neighbour = graph[currnode][i]
			if visited[neighbour] == False:
				visited[neighbour] = True
				stack.append(neighbour)
				parent[neighbour] = currnode
				index[currnode] += 1
				dp[parent[neighbour]] -= max(dp[neighbour], 0)
				dp[neighbour] += max(0, dp[parent[neighbour]])
				ans[neighbour] = dp[neighbour]
				break
		else:
			dp[currnode] -= max(0, dp[parent[currnode]])
			dp[parent[currnode]] += max(dp[currnode], 0)
			stack.pop()
	return
dfs1(tree, n, 1)
print(*ans[1:])


class Graph:

	def __init__(self, n_vertices, edges, directed=True):
		self.n_vertices = n_vertices
		self.edges = edges
		self.directed = directed

	@property
	def adj(self):
		try:
			return self._adj
		except AttributeError:
			adj = [[] for _ in range(self.n_vertices)]
			if self.directed:
				for (u, v) in self.edges:
					adj[u].append(v)
			else:
				for (u, v) in self.edges:
					adj[u].append(v)
					adj[v].append(u)
			self._adj = adj
			return adj

	def draw(self):
		import matplotlib.pyplot as plt
		import networkx as nx
		if self.directed:
			G = nx.DiGraph()
		else:
			G = nx.Graph()
		for (x, y) in self.edges:
			G.add_edge(x, y)
		pos = nx.spring_layout(G)
		nx.draw_networkx(G, pos)
		plt.axis('off')
		plt.show()

class RootedTree(Graph):

	def __init__(self, n_vertices, edges, root_vertex=0):
		self.root = root_vertex
		super().__init__(n_vertices, edges, False)

	@property
	def parent(self):
		try:
			return self._parent
		except AttributeError:
			adj = self.adj
			parent = [None] * self.n_vertices
			parent[self.root] = -1
			stack = [self.root]
			for _ in range(self.n_vertices):
				v = stack.pop()
				for u in adj[v]:
					if parent[u] is None:
						parent[u] = v
						stack.append(u)
			self._parent = parent
			return parent

	@property
	def children(self):
		try:
			return self._children
		except AttributeError:
			children = [None] * self.n_vertices
			for (v, (l, p)) in enumerate(zip(self.adj, self.parent)):
				children[v] = [u for u in l if u != p]
			self._children = children
			return children

	@property
	def dfs_order(self):
		try:
			return self._dfs_order
		except AttributeError:
			order = [None] * self.n_vertices
			children = self.children
			stack = [self.root]
			for i in range(self.n_vertices):
				v = stack.pop()
				order[i] = v
				for u in children[v]:
					stack.append(u)
			self._dfs_order = order
			return order

def rerooting_fast(rooted_tree, merge, identity, finalize):
	N = rooted_tree.n_vertices
	parent = rooted_tree.parent
	children = rooted_tree.children
	order = rooted_tree.dfs_order
	dp1 = [identity] * N
	dp2 = [identity] * N
	for v in reversed(order):
		t = identity
		for u in children[v]:
			dp2[u] = t
			t = merge(t, finalize(dp1[u], v, u))
		t = identity
		for u in reversed(children[v]):
			dp2[u] = merge(t, dp2[u])
			t = merge(t, finalize(dp1[u], v, u))
		dp1[v] = t
	for v in order[1:]:
		p = parent[v]
		dp2[v] = finalize(merge(dp2[v], dp2[p]), v, p)
		dp1[v] = merge(dp1[v], dp2[v])
	return dp1

def solve(N, A, E):
	rooted_tree = RootedTree(N, E)

	def merge(x, y):
		(c1, ta1) = x
		(c2, ta2) = y
		return (c1 + c2, ta1 + ta2)

	def finalize(x, u, v):
		(c, ta) = x
		return (c + ta, ta + A[v])
	res = rerooting_fast(rooted_tree, merge, (0, 0), finalize)
	return max((a + b for (a, b) in res))
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
N = int(readline())
A = tuple(map(int, readline().split()))
t = iter(read().split())
E = tuple(((int(x) - 1, int(y) - 1) for (x, y) in zip(t, t)))
print(solve(N, A, E))


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) = map(int, input().split())
		adj[u].append(v)
		adj[v].append(u)
	dfs(1, 0)
	dfs2(1, 0, 0)
	print(max(totw))
sys.setrecursionlimit(200050)
threading.stack_size(80000000)
thread = threading.Thread(target=work)
thread.start()


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)


from collections import deque
import sys
from typing import Pattern
input = sys.stdin.readline

def bfs(s):
	q = deque()
	q.append(s)
	visit = [0] * (n + 1)
	visit[s] = 1
	p = []
	parent = [-1] * (n + 1)
	H = [[] for _ in range(n + 1)]
	while q:
		i = q.popleft()
		p.append(i)
		for j in G[i]:
			if not visit[j]:
				q.append(j)
				visit[j] = 1
				parent[j] = i
				H[i].append(j)
	return (p, parent, H)
n = int(input())
a = list(map(int, input().split()))
sw = sum(a)
sb = n - sw
G = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	G[u].append(v)
	G[v].append(u)
(p, parent, H) = bfs(1)
s = [0] * (n + 1)
dp1 = [0] * (n + 1)
p0 = []
while p:
	i = p.pop()
	p0.append(i)
	s = 1 if a[i - 1] else -1
	for j in H[i]:
		s += max(0, dp1[j])
	dp1[i] = s
dp2 = [0] * (n + 1)
while p0:
	i = p0.pop()
	j = parent[i]
	if j == -1:
		continue
	dp2[i] = max(0, dp1[j] - max(0, dp1[i]) + dp2[j])
ans = [dp1[i] + dp2[i] for i in range(1, n + 1)]
print(*ans)


import sys
input = sys.stdin.readline
from collections import deque
nn = 200200
mod = 10 ** 9 + 7
fa = [1] * (nn + 1)
fainv = [1] * (nn + 1)
for i in range(nn):
	fa[i + 1] = fa[i] * (i + 1) % mod
fainv[-1] = pow(fa[-1], mod - 2, mod)
for i in range(nn)[::-1]:
	fainv[i] = fainv[i + 1] * (i + 1) % mod
inv = lambda i: fainv[i] * fa[i - 1] % mod
N = int(input())
COL = [int(a) for a in input().split()]
X = [[] for i in range(N)]
for i in range(N - 1):
	(x, y) = map(int, input().split())
	X[x - 1].append(y - 1)
	X[y - 1].append(x - 1)
P = [-1] * N
Q = deque([0])
R = []
while Q:
	i = deque.popleft(Q)
	R.append(i)
	for a in X[i]:
		if a != P[i]:
			P[a] = i
			X[a].remove(i)
			deque.append(Q, a)
unit = 0
merge = lambda a, b: max(a, 0) + max(b, 0)
adj_bu = lambda a, i: a + 1 if COL[i] else a - 1
adj_td = lambda a, i: a + 1 if COL[P[i]] else a - 1
ans = lambda i: BU[i] + max(TD[i], 0)
use_size = False
if use_size:
	SIZE = [1] * N
	for i in R[1:][::-1]:
		SIZE[P[i]] += SIZE[i]
BU = [unit] * N
TD = [unit] * N
for i in R[1:][::-1]:
	BU[i] = adj_bu(BU[i], i)
	p = P[i]
	BU[p] = merge(BU[p], BU[i])
BU[R[0]] = adj_bu(BU[R[0]], R[0])
AX = [0] * N
for i in R:
	ac = unit
	for j in X[i]:
		AX[j] = ac
		ac = merge(ac, BU[j])
	ac = unit
	for j in X[i][::-1]:
		AX[j] = merge(AX[j], ac)
		TD[j] = adj_td(merge(TD[i], AX[j]), j)
		ac = merge(ac, BU[j])
ANS = [ans(i) for i in range(N)]
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)
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 sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

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

def MI1():
	return map(int1, sys.stdin.readline().split())

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

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

def main():

	def dfs():
		stack = [(0, -1, False)]
		while stack:
			(u, pu, re) = stack.pop()
			if re:
				dp1[u] += aa[u] * 2 - 1 + sum((dp1[cu] for cu in to[u] if cu != pu and dp1[cu] > 0))
			else:
				stack.append((u, pu, True))
				for cu in to[u]:
					if cu == pu:
						continue
					stack.append((cu, u, False))

	def dfs2():
		stack = [(0, -1)]
		while stack:
			(u, pu) = stack.pop()
			ans[u] = sum((dp1[cu] for cu in to[u] if cu != pu and dp1[cu] > 0)) + aa[u] * 2 - 1
			if u and dp2[u] > 0:
				ans[u] += dp2[u]
			for cu in to[u]:
				if cu == pu:
					continue
				d = dp1[cu] if dp1[cu] > 0 else 0
				dp2[cu] = ans[u] - d
				stack.append((cu, u))
	n = II()
	aa = LI()
	to = [[] for _ in range(n)]
	for _ in range(n - 1):
		(u, v) = MI1()
		to[u].append(v)
		to[v].append(u)
	dp1 = [0] * n
	dfs()
	dp2 = [0] * n
	ans = [0] * n
	dfs2()
	print(*ans)
main()


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 sys
input = lambda : sys.stdin.readline().rstrip()
from collections import deque
N = int(input())
A = [int(a) * 2 - 1 for a in input().split()]
X = [[] for i in range(N)]
for i in range(N - 1):
	(x, y) = map(int, input().split())
	X[x - 1].append(y - 1)
	X[y - 1].append(x - 1)
P = [-1] * N
Q = deque([0])
R = []
while Q:
	i = deque.popleft(Q)
	R.append(i)
	for a in X[i]:
		if a != P[i]:
			P[a] = i
			X[a].remove(i)
			deque.append(Q, a)
BU = [0] * N
TD = [0] * N
for i in R[::-1]:
	a = A[i]
	for j in X[i]:
		a += max(BU[j], 0)
	BU[i] = a
for i in R:
	c = len(X[i])
	AL = [0] * (c + 1)
	AR = [0] * (c + 1)
	for j in range(c):
		AL[j + 1] = AL[j] + max(BU[X[i][j]], 0)
	for j in range(c)[::-1]:
		AR[j] = AR[j + 1] + max(BU[X[i][j]], 0)
	for j in range(c):
		TD[X[i][j]] = max(TD[i] + AL[j] + AR[j + 1] + A[i], 0)
print(*[BU[i] + TD[i] for i in range(N)])


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from collections import defaultdict, deque
n = int(input())
arr = list(map(int, input().split()))

def bfs(node):
	vis[node] = n
	q = deque([node])
	while q:
		cur = q.popleft()
		order.append(cur)
		for j in edge[cur]:
			if vis[j] == 0:
				q.append(j)
				vis[j] = 1
				child[cur].append(j)
				parent[j] = cur
edge = defaultdict(list)
child = defaultdict(list)
for i in range(n - 1):
	(u, v) = list(map(int, input().split()))
	edge[u].append(v)
	edge[v].append(u)
vis = [0] * (n + 1)
order = []
parent = [0] * (n + 1)
bfs(1)
order.reverse()
lis = [-1] * (n + 1)
for i in range(n):
	if arr[order[i] - 1] == 0:
		temp = -1
	else:
		temp = 1
	for j in child[order[i]]:
		if lis[j] > 0:
			temp += lis[j]
	lis[order[i]] = temp
order.reverse()
ans = [-1] * (n + 1)
for i in range(n):
	val = lis[order[i]]
	if ans[parent[order[i]]] > 0:
		if val >= 0:
			val += max(0, ans[parent[order[i]]] - val)
		else:
			val += max(0, ans[parent[order[i]]])
	ans[order[i]] = val
print(' '.join((str(x) for x in ans[1:])))


from collections import deque
import sys
input = sys.stdin.readline

def solve(tree, root, a):

	def merge_add(res, num):
		return res + max(0, num)

	def dfs1():
		q1 = deque([root])
		q2 = deque([root])
		while q1:
			v = q1.pop()
			for nxt_v in tree[v]:
				if nxt_v in par:
					continue
				else:
					par[nxt_v] = v
					q1.append(nxt_v)
					q2.append(nxt_v)
		while q2:
			v = q2.pop()
			res = a[v]
			for nxt_v in tree[v]:
				if nxt_v == par[v]:
					continue
				else:
					res = merge_add(res, dist1[nxt_v])
			dist1[v] = res

	def dfs2():
		q = deque([(root, 0)])
		while q:
			(v, par_val) = q.pop()
			tmp = {}
			for nxt_v in tree[v]:
				if nxt_v == par[v]:
					tmp[nxt_v] = par_val
				else:
					tmp[nxt_v] = dist1[nxt_v]
			res = a[v]
			for nxt_v in tmp:
				res = merge_add(res, tmp[nxt_v])
			dist2[v] = res
			for nxt_v in tree[v]:
				if nxt_v == par[v]:
					continue
				else:
					q.append((nxt_v, res - max(tmp[nxt_v], 0)))
	par = {root: -1}
	dist1 = [0] * n
	dist2 = [0] * n
	dfs1()
	dfs2()
	return dist2
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
	if a[i] == 0:
		a[i] -= 1
info = [list(map(int, input().split())) for i in range(n - 1)]
tree = [[] for i in range(n)]
for (u, v) in info:
	u -= 1
	v -= 1
	tree[u].append(v)
	tree[v].append(u)
print(*solve(tree, 0, a))


import sys
input = sys.stdin.readline
N = int(input())
Color = list(map(int, input().split()))
Adj = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	Adj[a].append(b)
	Adj[b].append(a)
Parent = [0] * N
Parent[0] = -1
rank = [0] * N
Q = [0]
visited = {0}
depth = 1
while Q:
	P = []
	for i in Q:
		for j in Adj[i]:
			if j in visited:
				continue
			rank[j] = depth
			Parent[j] = i
			visited.add(j)
			P.append(j)
	Q = P
	depth += 1
rankk = [[rank[i], i] for i in range(N)]
rankk.sort()
Ans = [0] * N
for i in reversed(range(1, N)):
	k = rankk[i][1]
	if Color[k] == 0:
		Ans[k] -= 1
	else:
		Ans[k] += 1
	Ans[Parent[k]] += max(0, Ans[k])
if Color[0] == 0:
	Ans[0] -= 1
else:
	Ans[0] += 1
for i in range(1, N):
	k = rankk[i][1]
	Ans[k] = max(Ans[k], min(Ans[k], 0) + Ans[Parent[k]])
print(*Ans)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5 * 2)
n = int(input())
c = [int(item) for item in input().split()]
edge = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	edge[a].append(b)
	edge[b].append(a)
memo = [None] * n

def dfs(p, v):
	st = []
	st.append((p, v, 0))
	while st:
		(p, v, is_return) = st.pop()
		if is_return:
			val = 0
			for nv in edge[v]:
				if nv == p:
					continue
				if memo[nv] > 0:
					val += memo[nv]
			if c[v] == 0:
				val = max(val - 1, -1)
			else:
				val = max(val + 1, 1)
			memo[v] = val
		else:
			st.append((p, v, 1))
			for nv in edge[v]:
				if nv == p:
					continue
				st.append((v, nv, 0))

def dfs_dp(p, v):
	st = []
	st.append((p, v))
	while st:
		(p, v) = st.pop()
		val = memo[v]
		if val < 0:
			up = memo[p]
		else:
			up = memo[p] - memo[v]
		if up > 0:
			val += up
		if p != -1:
			memo[v] = val
		for nv in edge[v]:
			if nv == p:
				continue
			st.append((v, nv))
dfs(-1, 0)
dfs_dp(-1, 0)
print(*memo)


from types import GeneratorType

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

def main():
	n = int(input())
	arr = [-1] + readIntArr()
	for i in range(1, n + 1):
		if arr[i] == 0:
			arr[i] = -1
	adj = [[] for _ in range(n + 1)]
	for _ in range(n - 1):
		(u, v) = readIntArr()
		adj[u].append(v)
		adj[v].append(u)
	ans = [None for _ in range(n + 1)]
	memo = [None for _ in range(n + 1)]

	@bootstrap
	def initialSolve(node, parent):
		diff = arr[node]
		for child in adj[node]:
			if child != parent:
				diff2 = (yield initialSolve(child, node))
				if diff2 > 0:
					diff += diff2
		memo[node] = diff
		yield diff
	initialSolve(1, 0)
	ans[1] = memo[1]

	@bootstrap
	def rerootDFS(node):
		for child in adj[node]:
			if ans[child] == None:
				nodeVal = memo[node]
				childVal = memo[child]
				if childVal > 0:
					memo[node] -= childVal
				if memo[node] > 0:
					memo[child] += memo[node]
				ans[child] = memo[child]
				yield rerootDFS(child)
				memo[node] = nodeVal
				memo[child] = childVal
		yield None
	rerootDFS(1)
	ans.pop(0)
	oneLineArrayPrint(ans)
	return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]
inf = float('inf')
MOD = 10 ** 9 + 7
for _ in range(1):
	main()


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 sys import stdin, stdout
from math import gcd, sqrt, factorial, pi, inf
from collections import deque, defaultdict
from bisect import bisect, bisect_left
from time import time
from itertools import permutations as per
from heapq import heapify, heappush, heappushpop
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\r\n')
L = lambda : list(R())
P = lambda x: stdout.write(str(x) + '\n')
lcm = lambda x, y: x * y // gcd(x, y)
nCr = lambda x, y: f[x] * inv(f[y] * f[x - y] % N) % N
inv = lambda x: pow(x, N - 2, N)
sm = lambda x: (x ** 2 + x) // 2
N = 10 ** 9 + 7
n = I()
val = [0] + L()
a = [[] for i in range(n + 1)]
dg = [0] * (n + 1)
for i in range(n - 1):
	(x, y) = R()
	dg[x] += 1
	dg[y] += 1
	a[x] += (y,)
	a[y] += (x,)
vst = [False] * (n + 1)
stk = [dg.index(1)]
vst[stk[-1]] = True
pr = [0] * (n + 1)
ch = [stk[-1]]
while stk:
	p = stk.pop()
	for el in a[p]:
		if not vst[el]:
			stk += (el,)
			ch += (el,)
			pr[el] = p
			vst[el] = True
v = [1 if i else -1 for i in val]
for i in ch[1:][::-1]:
	v[pr[i]] += max(0, v[i])
stk = [ch[0]]
vst = [False] * (n + 1)
vst[stk[-1]] = True
while stk:
	p = stk.pop()
	for el in a[p]:
		if not vst[el]:
			if v[el] < 0:
				v[el] = max(-1, v[p] + v[el])
			else:
				v[el] = max(v[el], v[p])
			stk += (el,)
			vst[el] = True
print(*v[1:])


class Graph:

	def __init__(self, n_vertices, edges, directed=True):
		self.n_vertices = n_vertices
		self.edges = edges
		self.directed = directed

	@property
	def adj(self):
		try:
			return self._adj
		except AttributeError:
			adj = [[] for _ in range(self.n_vertices)]
			if self.directed:
				for (u, v) in self.edges:
					adj[u].append(v)
			else:
				for (u, v) in self.edges:
					adj[u].append(v)
					adj[v].append(u)
			self._adj = adj
			return adj

class RootedTree(Graph):

	def __init__(self, n_vertices, edges, root_vertex=0):
		self.root = root_vertex
		super().__init__(n_vertices, edges, False)

	@property
	def parent(self):
		try:
			return self._parent
		except AttributeError:
			adj = self.adj
			parent = [None] * self.n_vertices
			parent[self.root] = -1
			stack = [self.root]
			for _ in range(self.n_vertices):
				v = stack.pop()
				for u in adj[v]:
					if parent[u] is None:
						parent[u] = v
						stack.append(u)
			self._parent = parent
			return parent

	@property
	def children(self):
		try:
			return self._children
		except AttributeError:
			children = [None] * self.n_vertices
			for (v, (l, p)) in enumerate(zip(self.adj, self.parent)):
				children[v] = [u for u in l if u != p]
			self._children = children
			return children

	@property
	def dfs_order(self):
		try:
			return self._dfs_order
		except AttributeError:
			order = [None] * self.n_vertices
			children = self.children
			stack = [self.root]
			for i in range(self.n_vertices):
				v = stack.pop()
				order[i] = v
				for u in children[v]:
					stack.append(u)
			self._dfs_order = order
			return order
from functools import reduce
from itertools import accumulate, chain

def rerooting(rooted_tree, merge, identity, finalize):
	N = rooted_tree.n_vertices
	parent = rooted_tree.parent
	children = rooted_tree.children
	order = rooted_tree.dfs_order
	dp_down = [None] * N
	for v in reversed(order):
		dp_down[v] = finalize(reduce(merge, (dp_down[c] for c in children[v]), identity), parent[v], v)
	dp_up = [None] * N
	dp_up[0] = identity
	for v in order:
		if len(children[v]) == 0:
			continue
		temp = (dp_up[v],) + tuple((dp_down[u] for u in children[v])) + (identity,)
		left = accumulate(temp[:-2], merge)
		right = tuple(accumulate(reversed(temp[2:]), merge))
		for (u, l, r) in zip(children[v], left, reversed(right)):
			dp_up[u] = finalize(merge(l, r), u, v)
	res = [None] * N
	for (v, l) in enumerate(children):
		res[v] = reduce(merge, (dp_down[u] for u in children[v]), identity)
		res[v] = finalize(merge(res[v], dp_up[v]), -1, v)
	return (res, dp_up, dp_down)
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
n = int(readline())
color = tuple(map(int, readline().split()))
temp = map(lambda x: int(x) - 1, read().split())
edges = zip(temp, temp)
min2 = lambda x, y: x if x < y else y
t = RootedTree(n, edges)

def merge(x, y):
	(b1, w1, s1) = x
	(b2, w2, s2) = y
	return (b1 + b2, w1 + w2, s1 + s2)

def finalize(x, u, v):
	(b, w, s) = x
	if color[v]:
		w += 1
	else:
		b += 1
	if u >= 0 and w - b < s:
		s = w - b
	return (b, w, s)
e = sum(color) * 2 - n
(res, _, _) = rerooting(t, merge, (0, 0, 0), finalize)
print(*(e - s for (_, _, s) in res))


import sys
inp = sys.stdin.readline

def input():
	return inp().strip()

def iin():
	return int(input())

def lin():
	return list(map(int, input().split()))
from types import GeneratorType

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

def dfs(adj, start=1):
	n = len(adj)
	visited = [False] * n
	first = [-1] * n
	euler = []
	srt = [start]
	parent = [-1] * n
	while srt:
		v = srt.pop()
		if visited[v]:
			euler.append(v)
			continue
		first[v] = len(euler)
		euler.append(v)
		visited[v] = True
		if parent[v] != -1:
			srt.append(parent[v])
		for u in adj[v]:
			if not visited[u]:
				parent[u] = v
				srt.append(u)
	return euler

def DFS1(adj, v, a):
	parent = {}
	dp = [0] * len(adj)

	@bootstrap
	def DFS_use(adj, s):
		sm = 0
		for i in adj[s]:
			if i not in parent:
				parent[i] = s
				sm += max(0, (yield DFS_use(adj, i)))
		dp[s] = a[s] + sm
		yield dp[s]
	for s in v:
		if s not in parent:
			parent[s] = None
			DFS_use(adj, s)
	return dp

def main():
	from collections import defaultdict
	T = 1
	while T:
		T -= 1
		n = iin()
		a = [0] + [1 if i else -1 for i in lin()]
		adj = [[] for i in range(n + 1)]
		for _ in range(n - 1):
			(i, j) = lin()
			adj[i].append(j)
			adj[j].append(i)
		path = dfs(adj)
		dp = DFS1(adj, list(range(n + 1)), a)
		ans = [0] * (n + 1)
		ans[1] = dp[1]
		l = len(path)
		for i in range(1, l):
			pv = path[i - 1]
			x = path[i]
			dp[pv] -= max(0, dp[x])
			dp[x] += max(0, dp[pv])
			ans[x] = dp[x]
		print(*ans[1:])
main()


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))