Ma5termind's best friend Shasha won a lucky draw. As a prize he got a travel ticket to travel from any country X to any country Y in this world. Note that it is possible to travel from some country X to itself.

Let us consider this world as a undirected acyclic graph ( aka tree ) where N different countries numbered from 1 to N are connected by bidirectional roads. Each country has an entrance fee associated with it which is denoted by an integer C_i.

Let's define travelling cost ( say V ) of a path from some country X to some country Y as the sum of entrance fees of all countries coming on the unique path from country X to Y.

Shasha being the most clever guy wants to make maximum utilization of free coupon and therefore he wants to visit a path with maximum possible cost.

It should be noted that entry fee of a country is an integer ( possibly negative or positive ).

Input

Each input file will contain a T test case.
First line will contain a single integer N denoting number of cities.
Next line will contain N space-seperated integers
Next N-1 will contain two space-seperated integer X and Y denoting that there exists a bidirectional edge between the countries X and Y.

Ouput:

Constraints:

• 1 ≤ T ≤ 5
• 1 ≤ N ≤ 50000
• -100000000 ≤ C_i ≤ 100000000
• 1 ≤ X, Y ≤ N

Scoring:

• subtask 1: 1 ≤ N ≤ 1000 ( 40 pts )
• subtask 2: 1 ≤ N ≤ 50000 ( 60 pts )