Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

EIDIS221222FQ1 - EIUSUBTREE

Given a tree which has n nodes, numbered from 0 to n-1. Node 0 is the root of the tree. Each node has its weight which is an integer number. Write a program to calculate the weight of all subtrees, which is the total weight of all the subtree’s nodes.

Input

The first line contains the number of nodes n (1 ≤ n ≤ 105).

The second line contains n integers which are the weight of node 0 to node (n-1) respectively.

Each of the next n-1 lines contains 2 integers u, v representing an edge between u and v.

Output

Print out the maximum weight of all subtrees.

Sample

Input

Output

6

1 5 0 2 -5 1

1 0

2 0

2 3

2 4

2 5

5


Added by:Ha Minh Ngoc
Date:2022-03-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.