maximum-sum-path-on-a-tree

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 Ci.

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:
For each test case output the answer in new line.
Constraints:

1 ≤ T ≤ 5 
1 ≤ N ≤ 50000
-100000000 ≤ Ci ≤ 100000000
1 ≤ X, Y ≤ N

See sample I/O for more clarification.

Scoring:

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

SAMPLE INPUT
1
4
2 2 1 4
1 2
2 3
2 4

SAMPLE OUTPUT
8

Explanation

The maximum amount he can avail is by goin from city 1 to 4 via 2.

Source: hackerearth | Difficulty: EASY
Tags: Tree algorithms

Dynamic programming


Solutions: