Lakshy was walking around in the forest when he sees an odd-looking tree which he called the
Orz Tree. An
Orz Tree is a tree where each node is adjacent to at most other nodes.
A tree is defined as a connected graph with nodes and non-repeated bi-directional edges. There are no cycles in a tree.
Lakshy has a rooted tree that is rooted at node back at his house. However, a node in Lakshy's tree may be adjacent to more than 3 nodes. In addition, he can only remove a node if that node does not disconnect his current graph. To remove node will cost him kneecaps, and to keep his tree alive while he is pruning it, Lakshy may not remove the root (node ) from his tree. Can you help Lakshy determine the minimum amount of kneecaps he needs to modify his tree to make it into an
The first line contains an integer , the number of nodes in Lakshy's tree.
The second line contains space-separated integers , the cost to remove the node for from Lakshy's tree.
The next lines each contain two integers , describing that node connects to node in Lakshy's tree.
Output the minimum cost (in kneecaps) for Lakshy to make his tree into an
6 4 10 2 1 7 1 2 2 3 1 4 2 5 2 6
Explanation for Sample Output
Lakshy's tree is depicted below (the cost to remove each node is written in red):
It can be proven that it is optimal to remove node for a total cost of .