**Towers solution codeforces** – You are given a tree with 𝑛n vertices numbered from 11 to 𝑛n. The height of the 𝑖i-th vertex is ℎ𝑖hi. You can place any number of towers into vertices, for each tower you can choose which vertex to put it in, as well as choose its efficiency. Setting up a tower with efficiency 𝑒e costs 𝑒e coins, where 𝑒>0e>0.

It is considered that a vertex 𝑥x gets a signal if for some pair of towers at the vertices 𝑢u and 𝑣v (𝑢≠𝑣u≠v, but it is allowed that 𝑥=𝑢x=u or 𝑥=𝑣x=v) with efficiencies 𝑒𝑢eu and 𝑒𝑣ev, respectively, it is satisfied that min(𝑒𝑢,𝑒𝑣)≥ℎ𝑥min(eu,ev)≥hx and 𝑥x lies on the path between 𝑢u and 𝑣v.

Find the minimum number of coins required to set up towers so that you can get a signal at all vertices.

# Towers solution codeforces

The first line contains an integer 𝑛n (2≤𝑛≤2000002≤n≤200000) — the number of vertices in the tree.

The second line contains 𝑛n integers ℎ𝑖hi (1≤ℎ𝑖≤1091≤hi≤109) — the heights of the vertices.

Each of the next 𝑛−1n−1 lines contain a pair of numbers 𝑣𝑖,𝑢𝑖vi,ui (1≤𝑣𝑖,𝑢𝑖≤𝑛1≤vi,ui≤n) — an edge of the tree. It is guaranteed that the given edges form a tree.

Print one integer — the minimum required number of coins.

## Towers solution codeforces

3 1 2 1 1 2 2 3

4

5 1 3 3 1 3 1 3 5 4 4 3 2 3

7

2 6 1 1 2

12

### Towers solution codeforces Note

In the first test case it’s optimal to install two towers of height 22 at vertices 11 and 33.

In the second test case it’s optimal to install a tower of height 11 at vertex 11 and two towers of height 33 at vertices 22 and 55.

In the third test case it’s optimal to install two towers of height 66 at vertices 11 and 22.