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

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

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

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


-----Input-----

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

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

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

It is guaranteed that the given edges form a tree.


-----Output-----

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


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

Output
121

Input
1
1337

Output
0



-----Note-----

Picture corresponding to the first example: [Image]

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

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

Difficulty: introductory

Starter code:

Solutions:
import traceback
import sys
sys.setrecursionlimit(200010)

try:
    # alpha = "abcdefghijklmnopqrstuvwxyz"

    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)

    # for i in range(1,n+1):
    #     if i not in D:
    #         D[i] = []

    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):  
        nonlocal visited
        nonlocal cost  
        nonlocal val  
        nonlocal a
        nonlocal 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))
                    # cost[s]+=cost[i]

    dfs(1, 0)

    # ans = 1
    max_cost = val
    # print(max_cost)
    visited = [False for i in range(n+1)]
    cost[0] = sum(a)
    def trav(s, some_val):
        nonlocal cost  
        nonlocal visited
        nonlocal max_cost
        nonlocal D 
        stack = [(s,some_val)]
        while stack:
            s, some_val = stack.pop()
            visited[s] = True
            # print(some_val, s)
            if some_val>max_cost:
                max_cost = some_val

            for i in D[s]:
                if not visited[i]:     
                    # print(i, some_val, cost[s], cost[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)

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

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

    n = int(input())
    a = [0] + list(map(int, input().split()))
    tota = sum(a)
    adj = [[] for _ in range(n + 1)]

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

    def dfs2(u, p, w) :
        totw[u] += w
        for v in adj[u] :
            if v == p : 
                continue
            dfs2(v, u, totw[u] - totw[v] - totsz[v] + tota - totsz[v])

    for _ in range(n - 1) :
        u, v = list(map(int, input().split()))
        adj[u].append(v)
        adj[v].append(u)

    dfs(1, 0)
    dfs2(1, 0, 0)
    print(max(totw))

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

__starting_point()

import 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 = list(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))


'''t=int(input())
while(t):
    t-=1
    n,k=[int(x) for x in input().split()]
    s=""
    while(len(s)!=n):
        i=0
        while(i<k):
            if len(s)==n:
                break
            s+=chr(97+i)
            i+=1
    print(s)'''

'''n=int(input())
arr=[int(x) for x in input().split()]
arr=sorted(arr)
ans=0
for i in range(0,n-1,2):
    ans+=abs(arr[i]-arr[i+1])

print(ans)'''
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))
def __starting_point():
    sys.setrecursionlimit(200050)
    threading.stack_size(80000000)
    thread = threading.Thread(target=work)
    thread.start()

__starting_point()

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)
#visited = set()
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
    #return (children,total)
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)]))