Algorithms
Hard
2920
3179
Maximum Points After Collecting Coins From All Nodes
maximum-points-after-collecting-coins-from-all-nodes
"""
There exists an undirected tree rooted at node 0 with n nodes labeled from 0 to n - 1. You are given a 2D integer array edges of length n - 1, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree. You are also given a 0-indexed array coins of size n where coins[i] indicates the number of coins in the vertex i, and an integer k.

Starting from the root, you have to collect all the coins such that the coins at a node can only be collected if the coins of its ancestors have been already collected.

Coins at nodei can be collected in one of the following ways:

 * Collect all the coins, but you will get coins[i] - k points. If coins[i] - k is negative then you will lose abs(coins[i] - k) points.
 * Collect all the coins, but you will get floor(coins[i] / 2) points. If this way is used, then for all the nodej present in the subtree of nodei, coins[j] will get reduced to floor(coins[j] / 2).

Return the maximum points you can get after collecting the coins from all the tree nodes.

Example 1:

[https://assets.leetcode.com/uploads/2023/09/18/ex1-copy.png]

Input: edges = [[0,1],[1,2],[2,3]], coins = [10,10,3,3], k = 5
Output: 11
Explanation:
Collect all the coins from node 0 using the first way. Total points = 10 - 5 = 5.
Collect all the coins from node 1 using the first way. Total points = 5 + (10 - 5) = 10.
Collect all the coins from node 2 using the second way so coins left at node 3 will be floor(3 / 2) = 1. Total points = 10 + floor(3 / 2) = 11.
Collect all the coins from node 3 using the second way. Total points = 11 + floor(1 / 2) = 11.
It can be shown that the maximum points we can get after collecting coins from all the nodes is 11.

Example 2:

[https://assets.leetcode.com/uploads/2023/09/18/ex2.png]

Input: edges = [[0,1],[0,2]], coins = [8,4,4], k = 0
Output: 16
Explanation:
Coins will be collected from all the nodes using the first way. Therefore, total points = (8 - 0) + (4 - 0) + (4 - 0) = 16.


Constraints:

 * n == coins.length
 * 2 <= n <= 105
 * 0 <= coins[i] <= 104
 * edges.length == n - 1
 * 0 <= edges[i][0], edges[i][1] < n
 * 0 <= k <= 104
"""
class Solution:
    def maximumPoints(self, edges: List[List[int]], coins: List[int], k: int) -> int:
        
There exists an undirected tree rooted at node 0 with n nodes labeled from 0 to n - 1. You are given a 2D integer array edges of length n - 1, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree. You are also given a 0-indexed array coins of size n where coins[i] indicates the number of coins in the vertex i, and an integer k.

Starting from the root, you have to collect all the coins such that the coins at a node can only be collected if the coins of its ancestors have been already collected.

Coins at nodei can be collected in one of the following ways:

 * Collect all the coins, but you will get coins[i] - k points. If coins[i] - k is negative then you will lose abs(coins[i] - k) points.
 * Collect all the coins, but you will get floor(coins[i] / 2) points. If this way is used, then for all the nodej present in the subtree of nodei, coins[j] will get reduced to floor(coins[j] / 2).

Return the maximum points you can get after collecting the coins from all the tree nodes.

Example 1:

[https://assets.leetcode.com/uploads/2023/09/18/ex1-copy.png]

Input: edges = [[0,1],[1,2],[2,3]], coins = [10,10,3,3], k = 5
Output: 11
Explanation:
Collect all the coins from node 0 using the first way. Total points = 10 - 5 = 5.
Collect all the coins from node 1 using the first way. Total points = 5 + (10 - 5) = 10.
Collect all the coins from node 2 using the second way so coins left at node 3 will be floor(3 / 2) = 1. Total points = 10 + floor(3 / 2) = 11.
Collect all the coins from node 3 using the second way. Total points = 11 + floor(1 / 2) = 11.
It can be shown that the maximum points we can get after collecting coins from all the nodes is 11.

Example 2:

[https://assets.leetcode.com/uploads/2023/09/18/ex2.png]

Input: edges = [[0,1],[0,2]], coins = [8,4,4], k = 0
Output: 16
Explanation:
Coins will be collected from all the nodes using the first way. Therefore, total points = (8 - 0) + (4 - 0) + (4 - 0) = 16.


Constraints:

 * n == coins.length
 * 2 <= n <= 105
 * 0 <= coins[i] <= 104
 * edges.length == n - 1
 * 0 <= edges[i][0], edges[i][1] < n
 * 0 <= k <= 104


Please complete the code below to solve above prblem:
```python
class Solution:
    def maximumPoints(self, edges: List[List[int]], coins: List[int], k: int) -> int:
        
```

my_solution = Solution()

test_input = { "edges": [[0,1],[1,2],[2,3]], "coins": [10,10,3,3], "k": 5 }
assert my_solution.maximumPoints(**test_input) == 11

test_input = { "edges": [[0,1],[0,2]], "coins": [8,4,4], "k": 0 }
assert my_solution.maximumPoints(**test_input) == 16

test_input = { "edges": [[0,1],[2,0],[0,3],[4,2]], "coins": [7,5,0,9,3], "k": 4 }
assert my_solution.maximumPoints(**test_input) == 10

test_input = { "edges": [[1,0],[0,2],[1,3]], "coins": [9,3,8,9], "k": 0 }
assert my_solution.maximumPoints(**test_input) == 29

test_input = { "edges": [[0,1],[0,2],[3,2],[0,4]], "coins": [5,6,8,7,4], "k": 7 }
assert my_solution.maximumPoints(**test_input) == 8

test_input = { "edges": [[1,0],[2,1],[3,1]], "coins": [8,2,7,1], "k": 2 }
assert my_solution.maximumPoints(**test_input) == 11

test_input = { "edges": [[0,1],[1,2],[0,3]], "coins": [6,1,2,3], "k": 2 }
assert my_solution.maximumPoints(**test_input) == 5

test_input = { "edges": [[0,1],[0,2],[0,3],[2,4],[5,4],[6,0],[4,7],[8,5]], "coins": [2,3,10,0,0,2,7,3,9], "k": 2 }
assert my_solution.maximumPoints(**test_input) == 20

test_input = { "edges": [[0,1],[0,2],[1,3],[3,4],[0,5],[6,3],[5,7],[3,8],[9,7]], "coins": [0,5,10,5,6,5,0,2,0,0], "k": 7 }
assert my_solution.maximumPoints(**test_input) == 4

test_input = { "edges": [[0,1],[2,1],[3,0],[3,4],[5,0],[6,4],[7,1],[6,8],[9,5]], "coins": [9,0,9,6,7,6,5,7,1,10], "k": 7 }
assert my_solution.maximumPoints(**test_input) == 14

test_input = { "edges": [[0,1],[2,1],[3,2],[4,0],[5,2],[3,6],[7,2],[8,4],[9,2]], "coins": [9,4,0,8,0,7,8,1,10,9], "k": 1 }
assert my_solution.maximumPoints(**test_input) == 46

test_input = { "edges": [[1,0],[2,1],[3,1],[2,4],[5,4],[6,3],[6,7]], "coins": [9,9,5,5,7,9,6,9], "k": 8 }
assert my_solution.maximumPoints(**test_input) == 10

test_input = { "edges": [[0,1],[2,1],[2,3],[4,0],[5,2],[6,1]], "coins": [1,1,8,6,9,4,1], "k": 10 }
assert my_solution.maximumPoints(**test_input) == 3

test_input = { "edges": [[1,0],[1,2],[0,3]], "coins": [10,2,9,3], "k": 6 }
assert my_solution.maximumPoints(**test_input) == 8

test_input = { "edges": [[1,0],[1,2],[1,3],[3,4],[5,3],[4,6],[7,0],[1,8],[9,1]], "coins": [2,10,4,0,1,3,6,10,3,6], "k": 8 }
assert my_solution.maximumPoints(**test_input) == 7

test_input = { "edges": [[1,0],[0,2],[3,2],[4,3],[2,5],[1,6],[7,2]], "coins": [2,8,3,1,9,4,8,6], "k": 6 }
assert my_solution.maximumPoints(**test_input) == 6

test_input = { "edges": [[1,0],[2,0],[3,0]], "coins": [0,0,0,6], "k": 0 }
assert my_solution.maximumPoints(**test_input) == 6

test_input = { "edges": [[1,0],[1,2]], "coins": [7,6,0], "k": 6 }
assert my_solution.maximumPoints(**test_input) == 4

test_input = { "edges": [[0,1],[0,2],[1,3],[2,4],[5,4]], "coins": [4,2,7,7,4,9], "k": 6 }
assert my_solution.maximumPoints(**test_input) == 5

test_input = { "edges": [[0,1]], "coins": [10,9], "k": 6 }
assert my_solution.maximumPoints(**test_input) == 8

test_input = { "edges": [[0,1],[2,1],[3,1],[2,4],[5,0],[6,1]], "coins": [6,1,8,10,0,4,10], "k": 5 }
assert my_solution.maximumPoints(**test_input) == 13

test_input = { "edges": [[1,0],[2,0],[0,3],[0,4],[5,1],[6,4],[3,7],[5,8]], "coins": [9,0,4,2,0,0,3,1,8], "k": 5 }
assert my_solution.maximumPoints(**test_input) == 8

test_input = { "edges": [[0,1],[1,2],[3,2],[4,0]], "coins": [7,5,6,3,6], "k": 8 }
assert my_solution.maximumPoints(**test_input) == 5

test_input = { "edges": [[0,1],[1,2],[3,2],[4,2],[5,3],[6,1],[4,7],[7,8],[2,9]], "coins": [4,2,0,8,3,2,7,2,1,6], "k": 2 }
assert my_solution.maximumPoints(**test_input) == 18

test_input = { "edges": [[0,1],[1,2],[1,3],[4,0],[3,5],[6,3],[7,6],[8,0]], "coins": [3,3,4,3,1,3,1,6,3], "k": 1 }
assert my_solution.maximumPoints(**test_input) == 18

test_input = { "edges": [[1,0],[2,1],[2,3],[4,1],[4,5],[2,6]], "coins": [3,10,1,5,10,1,4], "k": 2 }
assert my_solution.maximumPoints(**test_input) == 21

test_input = { "edges": [[0,1],[2,0]], "coins": [7,10,8], "k": 10 }
assert my_solution.maximumPoints(**test_input) == 7

test_input = { "edges": [[1,0],[2,1],[3,1],[4,2],[5,3],[6,0],[7,4]], "coins": [1,1,7,10,5,1,7,8], "k": 7 }
assert my_solution.maximumPoints(**test_input) == 2

test_input = { "edges": [[1,0],[0,2],[3,2]], "coins": [5,2,10,5], "k": 3 }
assert my_solution.maximumPoints(**test_input) == 12

test_input = { "edges": [[1,0],[2,0],[3,2],[2,4],[4,5],[6,2],[5,7],[8,2]], "coins": [4,2,1,4,7,7,2,7,4], "k": 2 }
assert my_solution.maximumPoints(**test_input) == 22

test_input = { "edges": [[1,0]], "coins": [8,1], "k": 7 }
assert my_solution.maximumPoints(**test_input) == 4

test_input = { "edges": [[1,0],[0,2],[3,0],[3,4],[3,5],[6,0],[7,5]], "coins": [3,9,9,9,5,3,2,0], "k": 9 }
assert my_solution.maximumPoints(**test_input) == 8

test_input = { "edges": [[0,1],[2,1],[3,2],[4,1],[2,5]], "coins": [2,10,4,6,7,9], "k": 5 }
assert my_solution.maximumPoints(**test_input) == 11

test_input = { "edges": [[1,0],[2,1],[3,2],[3,4],[5,4],[2,6],[7,3]], "coins": [3,3,6,1,10,1,2,5], "k": 3 }
assert my_solution.maximumPoints(**test_input) == 11

test_input = { "edges": [[1,0],[2,0],[0,3],[1,4],[3,5],[0,6],[7,4],[1,8]], "coins": [9,7,9,0,3,6,9,4,0], "k": 8 }
assert my_solution.maximumPoints(**test_input) == 13

test_input = { "edges": [[0,1],[2,1],[3,0],[2,4],[1,5],[6,1],[7,3],[5,8]], "coins": [4,9,7,6,6,9,0,2,6], "k": 2 }
assert my_solution.maximumPoints(**test_input) == 34

test_input = { "edges": [[1,0],[1,2]], "coins": [4,4,6], "k": 3 }
assert my_solution.maximumPoints(**test_input) == 5

test_input = { "edges": [[0,1],[0,2],[3,1],[2,4],[4,5],[6,2],[4,7],[4,8],[9,1]], "coins": [8,6,10,9,3,10,3,7,9,1], "k": 6 }
assert my_solution.maximumPoints(**test_input) == 21

test_input = { "edges": [[1,0],[2,1],[0,3],[0,4],[5,3],[6,1],[7,5],[8,2],[9,3]], "coins": [1,3,10,0,7,2,8,10,0,5], "k": 0 }
assert my_solution.maximumPoints(**test_input) == 46

test_input = { "edges": [[0,1],[2,0]], "coins": [9,4,2], "k": 0 }
assert my_solution.maximumPoints(**test_input) == 15

test_input = { "edges": [[0,1],[2,1]], "coins": [0,9,3], "k": 3 }
assert my_solution.maximumPoints(**test_input) == 4

test_input = { "edges": [[1,0],[2,1],[3,2],[4,1],[3,5]], "coins": [10,10,8,6,0,0], "k": 1 }
assert my_solution.maximumPoints(**test_input) == 30

test_input = { "edges": [[0,1],[2,0],[3,0],[3,4],[5,1],[6,1],[7,2],[8,3],[0,9]], "coins": [6,4,5,2,1,10,10,9,8,10], "k": 1 }
assert my_solution.maximumPoints(**test_input) == 55

test_input = { "edges": [[0,1],[2,1],[3,2],[0,4],[1,5],[6,5],[7,1],[5,8],[1,9]], "coins": [8,0,9,5,9,6,2,8,1,8], "k": 9 }
assert my_solution.maximumPoints(**test_input) == 10

test_input = { "edges": [[0,1],[2,1],[2,3],[1,4],[3,5],[6,4],[7,6]], "coins": [8,2,3,10,4,5,8,8], "k": 1 }
assert my_solution.maximumPoints(**test_input) == 40

test_input = { "edges": [[0,1],[2,0],[0,3],[4,1],[5,2],[6,1],[7,1]], "coins": [3,9,4,4,3,4,10,4], "k": 2 }
assert my_solution.maximumPoints(**test_input) == 25

test_input = { "edges": [[1,0],[1,2],[3,0],[4,1],[5,1],[1,6],[1,7]], "coins": [7,4,7,2,5,8,0,7], "k": 8 }
assert my_solution.maximumPoints(**test_input) == 8

test_input = { "edges": [[0,1],[2,1],[3,1],[4,2],[5,4],[6,5],[7,5]], "coins": [4,5,7,5,0,4,6,7], "k": 4 }
assert my_solution.maximumPoints(**test_input) == 8

test_input = { "edges": [[1,0],[1,2],[1,3]], "coins": [8,4,10,7], "k": 1 }
assert my_solution.maximumPoints(**test_input) == 25

test_input = { "edges": [[0,1],[2,1],[2,3],[3,4],[4,5],[6,3],[3,7],[7,8],[9,8]], "coins": [0,2,1,5,8,2,5,3,7,6], "k": 10 }
assert my_solution.maximumPoints(**test_input) == 0

test_input = { "edges": [[1,0],[1,2],[3,0],[4,3],[1,5],[6,2],[7,3],[4,8],[4,9]], "coins": [6,5,1,8,8,10,5,7,7,1], "k": 5 }
assert my_solution.maximumPoints(**test_input) == 19

test_input = { "edges": [[0,1],[2,0],[2,3],[4,2],[5,0],[3,6],[7,5],[3,8],[9,8]], "coins": [9,6,4,10,4,1,6,1,5,9], "k": 6 }
assert my_solution.maximumPoints(**test_input) == 17

test_input = { "edges": [[0,1],[2,1],[3,1],[0,4],[3,5]], "coins": [1,9,3,4,9,3], "k": 6 }
assert my_solution.maximumPoints(**test_input) == 5

test_input = { "edges": [[0,1],[0,2]], "coins": [9,3,9], "k": 3 }
assert my_solution.maximumPoints(**test_input) == 13

test_input = { "edges": [[0,1],[2,0],[3,1],[2,4],[5,2],[6,5],[7,3],[8,5],[9,5]], "coins": [4,1,3,1,6,1,0,0,0,6], "k": 1 }
assert my_solution.maximumPoints(**test_input) == 15

test_input = { "edges": [[0,1]], "coins": [1,7], "k": 10 }
assert my_solution.maximumPoints(**test_input) == 1

test_input = { "edges": [[0,1]], "coins": [10,6], "k": 10 }
assert my_solution.maximumPoints(**test_input) == 6

test_input = { "edges": [[1,0],[1,2],[2,3],[0,4]], "coins": [6,7,8,1,9], "k": 9 }
assert my_solution.maximumPoints(**test_input) == 7

test_input = { "edges": [[0,1]], "coins": [6,6], "k": 0 }
assert my_solution.maximumPoints(**test_input) == 12

test_input = { "edges": [[0,1],[0,2],[0,3],[1,4],[5,4],[2,6]], "coins": [9,3,7,2,3,1,2], "k": 8 }
assert my_solution.maximumPoints(**test_input) == 6

test_input = { "edges": [[1,0],[0,2],[3,1],[3,4],[2,5]], "coins": [4,0,3,10,5,8], "k": 3 }
assert my_solution.maximumPoints(**test_input) == 12

test_input = { "edges": [[0,1],[2,1],[3,2],[4,1],[4,5],[5,6]], "coins": [3,9,2,6,1,9,1], "k": 10 }
assert my_solution.maximumPoints(**test_input) == 3

test_input = { "edges": [[1,0]], "coins": [8,8], "k": 8 }
assert my_solution.maximumPoints(**test_input) == 6

test_input = { "edges": [[0,1],[1,2],[1,3],[0,4],[5,2]], "coins": [2,3,7,9,7,7], "k": 2 }
assert my_solution.maximumPoints(**test_input) == 23

test_input = { "edges": [[0,1],[2,0],[3,1],[4,0],[3,5],[2,6]], "coins": [6,9,7,7,7,9,7], "k": 8 }
assert my_solution.maximumPoints(**test_input) == 11

test_input = { "edges": [[1,0],[2,1],[3,0],[0,4],[5,2],[0,6]], "coins": [9,4,7,9,6,2,9], "k": 10 }
assert my_solution.maximumPoints(**test_input) == 13

test_input = { "edges": [[0,1],[1,2],[3,2],[4,2],[0,5],[6,4],[7,3]], "coins": [5,5,6,3,0,8,5,7], "k": 7 }
assert my_solution.maximumPoints(**test_input) == 5

test_input = { "edges": [[1,0],[2,0],[2,3],[4,0],[5,2],[2,6],[7,3]], "coins": [8,3,4,5,6,1,6,9], "k": 6 }
assert my_solution.maximumPoints(**test_input) == 11

test_input = { "edges": [[0,1],[2,0],[0,3],[4,0],[5,0],[6,1],[7,3],[8,1]], "coins": [1,6,3,10,1,9,7,8,7], "k": 5 }
assert my_solution.maximumPoints(**test_input) == 17

test_input = { "edges": [[0,1],[2,0],[3,1],[3,4],[2,5],[6,4],[5,7],[5,8],[6,9]], "coins": [3,6,5,6,6,9,5,5,3,10], "k": 10 }
assert my_solution.maximumPoints(**test_input) == 4

test_input = { "edges": [[0,1],[2,0],[3,2],[4,1],[4,5],[6,3],[7,2],[8,2],[3,9]], "coins": [2,2,0,0,4,8,8,5,0,10], "k": 8 }
assert my_solution.maximumPoints(**test_input) == 1

test_input = { "edges": [[1,0],[0,2],[3,0],[4,3],[4,5],[6,5],[7,5]], "coins": [8,5,7,3,2,3,5,3], "k": 6 }
assert my_solution.maximumPoints(**test_input) == 8

test_input = { "edges": [[0,1],[2,0]], "coins": [4,3,8], "k": 3 }
assert my_solution.maximumPoints(**test_input) == 7

test_input = { "edges": [[1,0],[2,1],[3,1],[4,2],[5,0],[4,6],[7,3],[8,2]], "coins": [8,9,0,3,9,7,4,8,7], "k": 7 }
assert my_solution.maximumPoints(**test_input) == 12

test_input = { "edges": [[0,1],[2,1]], "coins": [1,6,4], "k": 4 }
assert my_solution.maximumPoints(**test_input) == 1

test_input = { "edges": [[0,1],[2,1],[3,1]], "coins": [8,9,1,0], "k": 3 }
assert my_solution.maximumPoints(**test_input) == 11

test_input = { "edges": [[1,0],[2,1],[0,3],[4,3],[5,4],[4,6]], "coins": [4,1,4,4,0,5,5], "k": 8 }
assert my_solution.maximumPoints(**test_input) == 3

test_input = { "edges": [[1,0],[2,1],[3,2],[3,4],[4,5],[6,5],[7,3]], "coins": [10,9,6,8,9,9,0,7], "k": 0 }
assert my_solution.maximumPoints(**test_input) == 58

test_input = { "edges": [[0,1],[1,2],[3,1],[2,4],[3,5],[4,6],[5,7],[1,8],[2,9]], "coins": [9,5,7,6,2,5,0,7,5,7], "k": 8 }
assert my_solution.maximumPoints(**test_input) == 8

test_input = { "edges": [[0,1],[1,2],[3,1]], "coins": [4,10,2,2], "k": 10 }
assert my_solution.maximumPoints(**test_input) == 4

test_input = { "edges": [[1,0],[1,2],[1,3],[2,4],[3,5],[1,6],[7,4],[8,1],[0,9]], "coins": [6,7,1,2,3,7,3,4,8,4], "k": 1 }
assert my_solution.maximumPoints(**test_input) == 35

test_input = { "edges": [[0,1],[2,1]], "coins": [4,8,10], "k": 6 }
assert my_solution.maximumPoints(**test_input) == 5

test_input = { "edges": [[0,1],[0,2],[2,3],[2,4],[5,3],[3,6],[7,2],[8,5]], "coins": [7,8,4,3,4,8,10,8,1], "k": 7 }
assert my_solution.maximumPoints(**test_input) == 12

test_input = { "edges": [[1,0],[2,1],[3,0],[4,2],[0,5]], "coins": [9,9,3,3,4,4], "k": 4 }
assert my_solution.maximumPoints(**test_input) == 15

test_input = { "edges": [[0,1],[0,2],[1,3],[2,4],[5,0]], "coins": [7,5,0,10,0,0], "k": 8 }
assert my_solution.maximumPoints(**test_input) == 5

test_input = { "edges": [[1,0],[2,1],[2,3],[4,2],[0,5],[6,2],[4,7],[8,5],[0,9]], "coins": [5,2,8,8,6,0,3,2,2,5], "k": 3 }
assert my_solution.maximumPoints(**test_input) == 18

test_input = { "edges": [[1,0],[1,2],[3,0],[4,3],[1,5],[6,1],[7,4],[2,8]], "coins": [5,5,2,1,3,8,6,4,3], "k": 1 }
assert my_solution.maximumPoints(**test_input) == 28

test_input = { "edges": [[1,0],[0,2]], "coins": [8,2,5], "k": 0 }
assert my_solution.maximumPoints(**test_input) == 15

test_input = { "edges": [[1,0],[1,2],[3,2]], "coins": [10,9,2,0], "k": 7 }
assert my_solution.maximumPoints(**test_input) == 7

test_input = { "edges": [[0,1],[2,0],[2,3],[0,4],[2,5],[6,4],[7,1],[8,3]], "coins": [10,4,4,8,9,5,5,8,1], "k": 0 }
assert my_solution.maximumPoints(**test_input) == 54

test_input = { "edges": [[0,1],[1,2],[1,3],[2,4],[1,5],[6,2],[3,7],[8,4],[9,3]], "coins": [5,1,1,3,5,0,0,1,1,9], "k": 5 }
assert my_solution.maximumPoints(**test_input) == 2

test_input = { "edges": [[0,1],[1,2],[3,1],[1,4],[5,3]], "coins": [1,7,1,3,3,7], "k": 7 }
assert my_solution.maximumPoints(**test_input) == 1

test_input = { "edges": [[0,1],[1,2],[3,2],[4,3],[5,2],[0,6],[3,7],[5,8]], "coins": [9,1,3,2,1,3,4,2,6], "k": 1 }
assert my_solution.maximumPoints(**test_input) == 22

test_input = { "edges": [[0,1],[0,2]], "coins": [5,1,5], "k": 10 }
assert my_solution.maximumPoints(**test_input) == 3

test_input = { "edges": [[0,1],[0,2],[3,1],[1,4],[4,5]], "coins": [5,7,8,9,3,10], "k": 7 }
assert my_solution.maximumPoints(**test_input) == 9

test_input = { "edges": [[0,1],[0,2],[0,3],[0,4],[0,5],[5,6],[6,7],[8,5]], "coins": [8,3,0,3,4,1,4,0,7], "k": 2 }
assert my_solution.maximumPoints(**test_input) == 16

test_input = { "edges": [[1,0],[0,2],[3,0],[4,3],[2,5],[3,6]], "coins": [3,6,7,1,2,8,0], "k": 9 }
assert my_solution.maximumPoints(**test_input) == 4

test_input = { "edges": [[1,0]], "coins": [4,0], "k": 9 }
assert my_solution.maximumPoints(**test_input) == 2

test_input = { "edges": [[1,0],[2,0],[3,1],[4,1],[5,2],[6,1],[4,7],[5,8]], "coins": [9,7,8,9,6,8,9,1,6], "k": 1 }
assert my_solution.maximumPoints(**test_input) == 54

test_input = { "edges": [[1,0],[0,2],[1,3],[0,4],[5,4],[6,0],[3,7]], "coins": [7,10,8,4,6,0,6,2], "k": 4 }
assert my_solution.maximumPoints(**test_input) == 21