Codeforces Round 958 (Div. 2) |
---|
Finished |
You, the monster killer, want to kill a group of monsters. The monsters are on a tree with $$$n$$$ vertices. On vertex with number $$$i$$$ ($$$1\le i\le n$$$), there is a monster with $$$a_i$$$ attack points. You want to battle with monsters for $$$10^{100}$$$ rounds.
In each round, the following happens in order:
There is a restriction: in one round, you cannot kill two monsters that are directly connected by an edge.
If you choose what monsters to attack optimally, what is the smallest health decrement you can have after all rounds?
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). Description of the test cases follows.
The first line of each test case contains an integer $$$n$$$ ($$$1\le n\le 3\cdot 10^5$$$).
The second line of each test case contains $$$n$$$ integers $$$a_1,\ldots,a_n$$$ ($$$1\le a_i\le 10^{12}$$$).
The following $$$n-1$$$ lines each contain two integers $$$x,y$$$ ($$$1\le x,y\le n$$$), denoting an edge on the tree connecting vertex $$$x$$$ and $$$y$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3\cdot 10^5$$$.
For each test case, print one integer: the minimum possible health decrement.
311000000000000547 15 32 29 231 21 32 42 578 10 2 3 5 7 41 21 43 25 36 27 5
1000000000000 193 57
In the first test case, an optimal sequence of operations would be:
The total health decrement is $$$10^{12}$$$.
In the second test case, an optimal sequence of operations would be:
The total health decrement is $$$193$$$.
In the third test case, an optimal sequence of operations would be:
The total health decrement is $$$57$$$.
Name |
---|