P8564 ρars/ey

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?

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 one positive integer in a single line, representing the answer.

[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