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$.
[{"code": "import traceback\nimport sys\nsys.setrecursionlimit(200010)\n\ntry:\n    # alpha = \"abcdefghijklmnopqrstuvwxyz\"\n\n    n = int(input())\n    a = [0]\n    a.extend(list(map(int, input().split())))\n    D = [[] for i in range(n+1)]\n    for i in range(n-1):\n        e1,e2 = (map(int, input().split()))\n        D[e1].append(e2)\n        D[e2].append(e1)\n\n    # for i in range(1,n+1):\n    #     if i not in D:\n    #         D[i] = []\n\n    visited = [False for i in range(n+1)]\n    cost = [a[i] for i in range(n+1)]\n    parent = [0 for i in range(n+1)]\n    val = 0\n\n    def dfs(s, depth):  \n        nonlocal visited\n        nonlocal cost  \n        nonlocal val  \n        nonlocal a\n        nonlocal D\n        stack = [(s,depth)]\n        while stack:\n            s, depth = stack[-1]\n            if visited[s]:\n                stack.pop()\n                cost[parent[s]]+=cost[s]\n                continue\n            else:    \n                visited[s] = True\n                val += depth*a[s]\n            for i in D[s]:\n                if not visited[i]:   \n                    parent[i] = s\n                    stack.append((i, depth+1))\n                    # cost[s]+=cost[i]\n\n    dfs(1, 0)\n\n    # ans = 1\n    max_cost = val\n    # print(max_cost)\n    visited = [False for i in range(n+1)]\n    cost[0] = sum(a)\n    def trav(s, some_val):\n        nonlocal cost  \n        nonlocal visited\n        nonlocal max_cost\n        nonlocal D \n        stack = [(s,some_val)]\n        while stack:\n            s, some_val = stack.pop()\n            visited[s] = True\n            # print(some_val, s)\n            if some_val>max_cost:\n                max_cost = some_val\n\n            for i in D[s]:\n                if not visited[i]:     \n                    # print(i, some_val, cost[s], cost[i])\n                    stack.append((i, some_val+(cost[0]-cost[i])-cost[i] ))\n\n\n    trav(1, val)\n    print(max_cost)\nexcept Exception as ex:\n    traceback.print_tb(ex.__traceback__)\n    print(ex)", "passed": true, "time": 0.14, "memory": 14468.0, "status": "done"}, {"code": "import sys\nfrom collections import deque\nfrom types import GeneratorType\nsys.setrecursionlimit(200000)\ninput = sys.stdin.readline\ndef bootstrap(f, stack=[]):\n    def wrappedfunc(*args, **kwargs):\n        if stack:\n            return f(*args, **kwargs)\n        else:\n            to = f(*args, **kwargs)\n            while True:\n                if type(to) is GeneratorType:\n                    stack.append(to)\n                    to = next(to)\n                else:\n                    stack.pop()\n                    if not stack:\n                        break\n                    to = stack[-1].send(to)\n            return to\n \n    return wrappedfunc\n\nn = int(input())\nval = [int(i) for i in input().split()]\ntree = [[] for i in range(n + 1)]\ndp = [0 for i in range(n + 1)]\ns = [0 for i in range(n + 1)]\nans = [0 for i in range(n + 1)]\nfor i in range(n - 1):\n    a,b = list(map(int,input().split()))\n    tree[a].append(b)\n    tree[b].append(a)\n@bootstrap\ndef dfs1(node,dist,pd):\n\n    for child in tree[node]:\n        if child == pd:\n            continue\n        yield dfs1(child,dist + 1, node)\n        dp[node] += dp[child]\n        s[node] += s[child]\n    dp[node] += val[node - 1] * dist\n    s[node] += val[node - 1]\n    yield dp[node]\ndfs1(1,0,1)\nq = deque(); ans[1] = dp[1]\nfor node in tree[1]:\n    q.append((node,1))\n\nwhile len(q) > 0:\n    node,pd = q.popleft()\n    sub_dp = ans[pd] - (dp[node] + s[node])\n    added = s[1] - s[node]\n    ans[node] = sub_dp + added + dp[node]\n    for child in tree[node]:\n        if child == pd:\n            continue\n        q.append((child,node))\nprint(max(ans))\n", "passed": true, "time": 0.14, "memory": 14300.0, "status": "done"}, {"code": "'''t=int(input())\nwhile(t):\n    t-=1\n    n,k=[int(x) for x in input().split()]\n    s=\"\"\n    while(len(s)!=n):\n        i=0\n        while(i<k):\n            if len(s)==n:\n                break\n            s+=chr(97+i)\n            i+=1\n    print(s)'''\n\n'''n=int(input())\narr=[int(x) for x in input().split()]\narr=sorted(arr)\nans=0\nfor i in range(0,n-1,2):\n    ans+=abs(arr[i]-arr[i+1])\n\nprint(ans)'''\nfrom collections import defaultdict\nimport sys,threading\n\ndef work():\n    sys.setrecursionlimit(1 << 18)\n    def fun(u,level,p):\n        l[1]+=level*arr[u-1]\n        summ[u]=arr[u-1]\n        for i in graph[u]:\n            if i!=p:\n                fun(i,level+1,u)\n                summ[u]+=summ[i]\n    def fun2(u,p):\n        for i in graph[u]:\n            if i!=p:\n                l[i]=l[u]+s-2*summ[i]\n                fun2(i,u)\n    n=int(input())\n    n1=n\n    arr=[int(x) for x in input().split()]\n    graph=defaultdict(list)\n    while(n1-1):\n        n1-=1\n        u,v=[int(x) for x in input().split()]\n        graph[u].append(v)\n        graph[v].append(u)\n    s=0\n    for i in arr:\n        s+=i\n    summ=[0]*(n+1)\n    l=[0]*(n+1)\n    fun(1,0,0)\n    fun2(1,0)\n    print(max(l))\ndef __starting_point():\n    sys.setrecursionlimit(200050)\n    threading.stack_size(80000000)\n    thread = threading.Thread(target=work)\n    thread.start()\n\n__starting_point()", "passed": true, "time": 0.14, "memory": 15340.0, "status": "done"}, {"code": "from sys import stdin,setrecursionlimit\n\n\nn = int(stdin.readline())\nay = [int(x) for x in stdin.readline().split()]\n\ngraph = [set() for x in range(n)]\n\nfor e in range(n-1):\n    a,b = [int(x)-1 for x in stdin.readline().split()]\n    graph[a].add(b)\n    graph[b].add(a)\n\ndists = {}\nchild = {}\n\nbruh = sum(ay)\n#visited = set()\npath = [(0,0)]\n\nfor x,p in path:\n    for y in graph[x]:\n        if y != p:\n            path.append((y,x))\n\nfor x,parent in path[::-1]:\n    total = 0\n    children = ay[x]\n    for v in graph[x]:\n        if v != parent:\n            c, sm = child[v], dists[v]\n            children += c\n            total += sm+c\n    dists[x] = total\n    child[x] = children\n    #return (children,total)\nb2,b3 = child[0], dists[0]\n\nfor x,parent in path:\n    for v in graph[x]:\n        if v != parent:\n            dists[v] = dists[x]+bruh-child[v]*2\nprint(max([dists[y] for y in range(n)]))\n    \n", "passed": true, "time": 0.14, "memory": 14152.0, "status": "done"}]