Tree Decrements :
Difficulty Level : Medium
Submissions : 64
Asked In :
Marks :15
: 1 | : 0
You are given a tree $$$T$$$ containing $$$n$$$ nodes. There is a value associated with each node. You can perform the following operation on this tree:
- Select two nodes and decrement thier values by 1 at a cost equal to the distance between the two nodes, i.e., the number of edges in the simple path between them. It is possible to select the same node for the operation and decrease its value by $$$2$$$ at a cost of $$$0$$$.
Find the minimum cost to decrease the values of all the nodes to $$$0$$$ using the given operation. It is guaranteed that the values of all the nodes can be decreased to exactly zero.
The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^4)$$$ — the number of test cases. The description of $$$t$$$ testcase follows.
The first line of each test case contains a single integer $$$n$$$ — the number of vertices in the tree $$$(2 \le n \le 10^5)$$$.
The second line contains $$$n$$$ space separated integers $$$a_1,a_2,...a_n$$$ $$$(1 \le a_i \le 10^9)$$$ denoting the values of the nodes of the tree.
The next $$$n-1$$$ lines describe the tree. Each contains two space separated integers $$$u$$$ and $$$v$$$ $$$(1 \le u, v \le n; $$$ $$$u \neq v \hspace{1 pt};)$$$ denoting an edge between vertices $$$u$$$ and $$$v$$$. It is guaranteed that these edges form a tree.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.
For each test case, print the minimum cost to decrease the values of all the nodes to $$$0$$$ using the given operation.
332 1 11 21 333 1 21 21 353 2 4 2 51 21 33 43 5
2 1 2
In sample test case 1, the optimal strategy is to choose the nodes $$$(1, 2)$$$ and $$$(1, 3)$$$, respectively, in the two operations.
In sample test case 2, the optimal strategy is to choose nodes $$$1$$$ and $$$2$$$ at cost $$$1$$$. The values become $$$[2, 0, 2]$$$. Now nodes $$$1$$$ and $$$1$$$, followed by $$$3$$$ and $$$3$$$, can he chosen, each with a cost of $$$0$$$. Thus the total cost is $$$1 + 0 + 0 = 1$$$.
