[Solution] Towers solution codeforces – Find the minimum number of coins required to set up towers so that you can get a signal at all vertices.

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.

Output

Print one integer — the minimum required number of coins.

Towers solution codeforces

3
1 2 1
1 2
2 3
output

Copy
4
input

Copy
5
1 3 3 1 3
1 3
5 4
4 3
2 3
output

Copy
7
input

Copy
2
6 1
1 2
output

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

Leave a Comment