K. Campus Partition
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Mr. Ham is one of the most famous architects in Hefei and has been invited to participate in the planning of the new campus of USTC.

Specifically, the campus of USTC can be considered as a tree $$$T=(V, E)$$$, with $$$n$$$ buildings and $$$n-1$$$ undirected edges, building $$$i$$$ having an importance value $$$w_i$$$. It is guaranteed that the USTC campus is connected.

The university hopes that Mr. Ham can divide the campus into several regions. We consider a partition plan is legal if and only if it satisfies the following conditions:

  • Each building belongs to exactly one region.
  • The induced subgraph of any region is connected.

The university considers the weight of a region to be the second highest importance value among all buildings in that region, and if the region contains only one building, its weight is $$$0$$$. The university hopes that Mr. Ham can maximize the sum weights of all regions. Can you help Mr. Ham get the answer?

Induced subgraph: If a region is composed of buildings from the set $$$S\subseteq V$$$, then its induced subgraph contains all the buildings in the set $$$S$$$ and edges whose endpoints are both in the set $$$S$$$.

Input

The first line contains a positive integer $$$n(1\le n\le 5\times 10^5)$$$ indicating the number of buildings.

The second line contains $$$n$$$ positive integers $$$w_i(1\le w_i\le 10^9)$$$ indicating the weight of each building.

The next $$$n-1$$$ lines contain the edges of the USTC campus, one edge per line. The $$$i$$$-th line contains two integers $$$u_i$$$, $$$v_i$$$$$$(1\le u_i,v_i\le n,u_i\ne v_i)$$$ indicating an edge $$$(u,v)$$$. It is guaranteed that it forms a tree.

Output

Output a single line containing only one integer indicating the maximum sum weight of all regions.

Example
Input
8
2 5 4 5 3 1 1 3
1 2
1 3
1 4
2 5
2 6
3 7
4 8
Output
8