Towers
Contest: Codeforces Global Round 19
Difficulty rating: 2500
Tags: constructive algorithms, dfs and similar, dp, greedy, trees

You are given a tree with $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$. The height of the $$$i$$$-th vertex is $$$h_i$$$. 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 $$$e > 0$$$.

It is considered that a vertex $$$x$$$ gets a signal if for some pair of towers at the vertices $$$u$$$ and $$$v$$$ ($$$u \neq v$$$, but it is allowed that $$$x = u$$$ or $$$x = v$$$) with efficiencies $$$e_u$$$ and $$$e_v$$$, respectively, it is satisfied that $$$\min(e_u, e_v) \geq h_x$$$ 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.

Input format:
The first line contains an integer $$$n$$$ ($$$2 \le n \le 200\,000$$$) — the number of vertices in the tree.

The second line contains $$$n$$$ integers $$$h_i$$$ ($$$1 \le h_i \le 10^9$$$) — the heights of the vertices.

Each of the next $$$n - 1$$$ lines contain a pair of numbers $$$v_i, u_i$$$ ($$$1 \le v_i, u_i \le n$$$) — an edge of the tree. It is guaranteed that the given edges form a tree.

Output format:
Print one integer — the minimum required number of coins.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case it's optimal to install two towers with efficiencies $$$2$$$ at vertices $$$1$$$ and $$$3$$$.

In the second test case it's optimal to install a tower with efficiency $$$1$$$ at vertex $$$1$$$ and two towers with efficiencies $$$3$$$ at vertices $$$2$$$ and $$$5$$$.

In the third test case it's optimal to install two towers with efficiencies $$$6$$$ at vertices $$$1$$$ and $$$2$$$.

Example input:
3
1 2 1
1 2
2 3

Example output:
4

Example input:
5
1 3 3 1 3
1 3
5 4
4 3
2 3

Example output:
7

Editorial:
Main solution:
Let's consider all leaves. If $$$v$$$ is a leaf, then all paths, which cover $$$v$$$ should start in $$$v$$$. Then let's increase heights of all towers in the leaves by $$$1$$$ (it's necessary) and decrease all $$$h_v$$$ by $$$1$$$. Now we should remove all leaves with $$$h_v = 0$$$ (they will be already covered). We will repeat the operation until there are covered leaves. We will continue the algorithm but instead of increasing height in new leaves of the tree we will increase height in deleted vertexes (in its subtree). If at some point we have only 1 vertex left we should increase height in $$$2$$$ towers (due to the statement we should use $$$2$$$ different towers to cover the vertex). To speed up the solution we will sort vertexes by $$$h_v$$$ and we will store current level of current leaves. On each iteration we will add amount of leaves multiplied by change of level.
If it is not optimal then let's consider heights of towers in the optimal answer. Let $$$f(i)$$$ be amount of vertices in optimal answer with height larger or equal to $$$i$$$. It is easy to notice that $$$f(i) - f(i - 1)$$$ is at least amount of leaves in the tree on $$$i$$$-th iteration. If there is only one vertex left on iteration $$$i$$$ then $$$2 = f(i) - f(i - 1)$$$. That means that the algorithm is optimal.
Alternative solution:
Let $$$root$$$ be the vertex with the maximum height. Let's root tree at $$$root$$$. Now there must be two towers in the subtrees of the children of vertex $$$root$$$ of height $$$h_{root}$$$ (if there's only one child, then there must be a tower at the vertex $$$root$$$ of height $$$h_{root}$$$). Now we need to place towers in the subtrees of the children of vertex $$$root$$$, such that for for every vertex $$$v$$$ the highest tower in the subtree of vertex $$$v$$$ (including $$$v$$$) must be at least $$$h_v$$$. After it's done you need to select two highest towers in the subtrees of two different child of the vertex $$$root$$$ and set their height to $$$h_{root}$$$.
Now we need to optimally place towers in the subtrees so that for every vertex $$$v$$$ there must be a tower in the subtree of vertex $$$v$$$ of height at least $$$h_v$$$. To do that in the subtree of vertex $$$v$$$, let's recursively place towers in the subtrees of the children of vertex $$$v$$$, and then increase the height of the highest tower in the subtree of $$$v$$$ to $$$h_v$$$ if it's necessary. If vertex $$$v$$$ is a leaf then we need to place a tower of height $$$h_v$$$ in the vertex $$$v$$$.
This solutions can be implemented in $$$O(n)$$$. For a better understanding, we recommend you to see the implementation.