Relay Tower Decommission Yield

A regional broadcast operator runs a relay network laid out as a tree of n towers, numbered 0 through n - 1, with tower 0 serving as the central hub. The network is described by n - 1 direct links between towers, and every tower is reachable from the hub through exactly one path (there are no cycles). Tower i currently holds an active equipment reserve worth strength[i] units.

You may decommission any subset of the towers. Decommissioning tower i banks strength[i] units of scrap value for you and drops that tower's contribution to zero. The network must remain live: for every path running from the hub down to an outpost tower (a tower with no towers beyond it), at least one tower on that path must be left active — the towers you decommission may never cover an entire hub-to-outpost path. Choose which towers to decommission so as to maximize the total scrap value collected while the network stays live.

Input format

• Line 1: a single integer n.
• Line 2: n space-separated integers strength[0] through strength[n-1].
• Each of the next n - 1 lines: two integers u and v, meaning towers u and v are directly linked. The n - 1 links form a tree rooted at tower 0.

Output format

A single integer: the maximum total scrap value obtainable while keeping the network live.

Constraints

• 2 <= n <= 2000
• 1 <= strength[i] <= 10^9
• 0 <= u, v <= n - 1, u != v
• The given links form a valid tree with tower 0 as its root.

4
3 5 2 4
0 1
0 2
2 3

11

4
10 1 1 1
0 1
0 2
0 3

10