Problem Description

You are given a rooted tree with $n$ nodes, where the root is node $1$. You can perform the following operation any number of times:

• Choose a node, and delete all nodes in its subtree except itself.

The cost of this operation is $f_i$, where $i$ is the size of the subtree of the chosen node.

You want to delete all nodes except node $1$. What is the minimum total cost?

Input Format

The first line contains a positive integer $n$.

The second line contains $n-1$ positive integers. The $i$-th integer represents $f_{i+1}$.

The next $n-1$ lines each contain two positive integers, representing an edge of the tree.

Output Format

Output one positive integer in a single line, representing the answer.

8
11000 18640 32793 36187 45104 64932 66425 
6 8
3 6
3 7
1 8
1 4
3 5
2 7

63744

Hint

[Sample Explanation]

First, delete the $5$ nodes in the subtree of node $8$ except itself, and then delete the $2$ nodes in the subtree of node $1$ except itself. The total cost is $f_6 + f_3 = 63744$. It can be proven that this is the minimum cost.

[Constraints]

For all testdata, it is guaranteed that $1 \le n \le 5000$ and $1 \le f_i \le 10^9$.

$$\def\arraystretch{1.5} \begin{array}{c|c|c}\hline \textbf{Test Point ID}&\bm{~~~~~~~~n\le~~~~~~~~}&~~~~\textbf{Special Constraints}~~~~\cr\hline \textsf1\sim \sf2 & 8& \cr\hline \sf3\sim 6 & 15& \cr\hline \sf7\sim 8 & 400&\textsf{A}\cr\hline \textsf9 & 400 &\sf B\cr\hline \sf10\sim 12 & 400&\cr\hline \sf13\sim 14 & &\sf C\cr\hline \sf15\sim 20 & &\cr\hline \end{array}$$

$\textsf A$: It is guaranteed that the degree of every node in the tree is at most $2$, and the degree of node $1$ is $1$.

$\textsf B$: It is guaranteed that only node $1$ has degree at least $2$.

$\textsf C$: It is guaranteed that the tree is generated randomly. The generation method is: for $i \ge 2$, randomly choose an integer $x$ from $[1, i-1]$ and add an edge between $x$ and $i$. Then randomly shuffle the labels of all nodes.

Translated by ChatGPT 5