Algorithms
Hard
2973
3218
Find Number of Coins to Place in Tree Nodes
find-number-of-coins-to-place-in-tree-nodes
"""
You are given an undirected tree with n nodes labeled from 0 to n - 1, and rooted at node 0. 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 integer array cost of length n, where cost[i] is the cost assigned to the ith node.
You need to place some coins on every node of the tree. The number of coins to be placed at node i can be calculated as:

If size of the subtree of node i is less than 3, place 1 coin.
Otherwise, place an amount of coins equal to the maximum product of cost values assigned to 3 distinct nodes in the subtree of node i. If this product is negative, place 0 coins.

Return an array coin of size n such that coin[i] is the number of coins placed at node i.

Example 1:


Input: edges = [[0,1],[0,2],[0,3],[0,4],[0,5]], cost = [1,2,3,4,5,6]
Output: [120,1,1,1,1,1]
Explanation: For node 0 place 6 * 5 * 4 = 120 coins. All other nodes are leaves with subtree of size 1, place 1 coin on each of them.

Example 2:


Input: edges = [[0,1],[0,2],[1,3],[1,4],[1,5],[2,6],[2,7],[2,8]], cost = [1,4,2,3,5,7,8,-4,2]
Output: [280,140,32,1,1,1,1,1,1]
Explanation: The coins placed on each node are:
- Place 8 * 7 * 5 = 280 coins on node 0.
- Place 7 * 5 * 4 = 140 coins on node 1.
- Place 8 * 2 * 2 = 32 coins on node 2.
- All other nodes are leaves with subtree of size 1, place 1 coin on each of them.

Example 3:


Input: edges = [[0,1],[0,2]], cost = [1,2,-2]
Output: [0,1,1]
Explanation: Node 1 and 2 are leaves with subtree of size 1, place 1 coin on each of them. For node 0 the only possible product of cost is 2 * 1 * -2 = -4. Hence place 0 coins on node 0.


Constraints:

2 <= n <= 2 * 104
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
cost.length == n
1 <= |cost[i]| <= 104
The input is generated such that edges represents a valid tree.
"""
class Solution:
    def placedCoins(self, edges: List[List[int]], cost: List[int]) -> List[int]:
        
You are given an undirected tree with n nodes labeled from 0 to n - 1, and rooted at node 0. 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 integer array cost of length n, where cost[i] is the cost assigned to the ith node.
You need to place some coins on every node of the tree. The number of coins to be placed at node i can be calculated as:

If size of the subtree of node i is less than 3, place 1 coin.
Otherwise, place an amount of coins equal to the maximum product of cost values assigned to 3 distinct nodes in the subtree of node i. If this product is negative, place 0 coins.

Return an array coin of size n such that coin[i] is the number of coins placed at node i.

Example 1:


Input: edges = [[0,1],[0,2],[0,3],[0,4],[0,5]], cost = [1,2,3,4,5,6]
Output: [120,1,1,1,1,1]
Explanation: For node 0 place 6 * 5 * 4 = 120 coins. All other nodes are leaves with subtree of size 1, place 1 coin on each of them.

Example 2:


Input: edges = [[0,1],[0,2],[1,3],[1,4],[1,5],[2,6],[2,7],[2,8]], cost = [1,4,2,3,5,7,8,-4,2]
Output: [280,140,32,1,1,1,1,1,1]
Explanation: The coins placed on each node are:
- Place 8 * 7 * 5 = 280 coins on node 0.
- Place 7 * 5 * 4 = 140 coins on node 1.
- Place 8 * 2 * 2 = 32 coins on node 2.
- All other nodes are leaves with subtree of size 1, place 1 coin on each of them.

Example 3:


Input: edges = [[0,1],[0,2]], cost = [1,2,-2]
Output: [0,1,1]
Explanation: Node 1 and 2 are leaves with subtree of size 1, place 1 coin on each of them. For node 0 the only possible product of cost is 2 * 1 * -2 = -4. Hence place 0 coins on node 0.


Constraints:

2 <= n <= 2 * 104
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
cost.length == n
1 <= |cost[i]| <= 104
The input is generated such that edges represents a valid tree.


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

my_solution = Solution()

test_input = { "edges": [[0,1],[0,2],[0,3],[0,4],[0,5]], "cost": [1,2,3,4,5,6] }
assert my_solution.placedCoins(**test_input) == [120,1,1,1,1,1]

test_input = { "edges": [[0,1],[0,2],[1,3],[1,4],[1,5],[2,6],[2,7],[2,8]], "cost": [1,4,2,3,5,7,8,-4,2] }
assert my_solution.placedCoins(**test_input) == [280,140,32,1,1,1,1,1,1]

test_input = { "edges": [[0,1],[0,2]], "cost": [1,2,-2] }
assert my_solution.placedCoins(**test_input) == [0,1,1]

test_input = { "edges": [[0,1]], "cost": [1,2] }
assert my_solution.placedCoins(**test_input) == [1,1]

test_input = { "edges": [[0,1]], "cost": [2,1] }
assert my_solution.placedCoins(**test_input) == [1,1]

test_input = { "edges": [[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[0,10],[0,11],[0,12],[0,13],[0,14],[0,15],[0,16],[0,17],[0,18],[0,19],[0,20],[0,21],[0,22],[0,23],[0,24],[0,25],[0,26],[0,27],[0,28],[0,29],[0,30],[0,31],[0,32],[0,33],[0,34],[0,35],[0,36],[0,37],[0,38],[0,39],[0,40],[0,41],[0,42],[0,43],[0,44],[0,45],[0,46],[0,47],[0,48],[0,49],[0,50],[0,51],[0,52],[0,53],[0,54],[0,55],[0,56],[0,57],[0,58],[0,59],[0,60],[0,61],[0,62],[0,63],[0,64],[0,65],[0,66],[0,67],[0,68],[0,69],[0,70],[0,71],[0,72],[0,73],[0,74],[0,75],[0,76],[0,77],[0,78],[0,79],[0,80],[0,81],[0,82],[0,83],[0,84],[0,85],[0,86],[0,87],[0,88],[0,89],[0,90],[0,91],[0,92],[0,93],[0,94],[0,95],[0,96],[0,97],[0,98],[0,99]], "cost": [-5959,602,-6457,7055,-1462,6347,7226,-8422,-6088,2997,-7909,6433,5217,3294,-3792,7463,8538,-3811,5009,151,5659,4458,-1702,-1877,2799,9861,-9668,-1765,2181,-8128,7046,9529,6202,-8026,6464,1345,121,1922,7274,-1227,-9914,3025,1046,-9368,-7368,6205,-6342,8091,-6732,-7620,3276,5136,6871,4823,-1885,-4005,-3974,-2725,-3845,-8508,7201,-9566,-7236,-3386,4021,6793,-8759,5066,5879,-5171,1011,1242,8536,-8405,-9646,-214,2251,-9934,-8820,6206,1006,1318,-9712,7230,5608,-4601,9185,346,3056,8913,-2454,-3445,-4295,4802,-8852,-6121,-4538,-5580,-9246,-6462] }
assert my_solution.placedCoins(**test_input) == [971167251036,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]

test_input = { "edges": [[0,1],[0,2],[2,3]], "cost": [10000,-10000,10000,-10000] }
assert my_solution.placedCoins(**test_input) == [1000000000000,1,1,1]

test_input = { "edges": [[0,2],[0,6],[1,4],[3,5],[7,6],[3,6],[1,8],[3,1],[9,3]], "cost": [63,13,-6,20,56,-14,61,25,-99,54] }
assert my_solution.placedCoins(**test_input) == [215208,0,1,77616,1,1,184464,1,1,1]

test_input = { "edges": [[7,0],[4,3],[4,8],[1,5],[6,2],[2,7],[7,9],[1,8],[1,9]], "cost": [37,-48,30,-67,-84,36,-96,24,29,38] }
assert my_solution.placedCoins(**test_input) == [306432,202608,1,1,1,1,1,306432,163212,213864]

test_input = { "edges": [[0,2],[2,7],[3,4],[5,4],[5,8],[7,6],[7,1],[8,1],[1,9]], "cost": [-18,15,-82,-85,63,-89,60,63,20,18] }
assert my_solution.placedCoins(**test_input) == [476595,476595,476595,1,1,476595,1,476595,476595,1]

test_input = { "edges": [[2,0],[1,4],[3,8],[4,9],[6,8],[7,2],[2,8],[5,2],[5,9]], "cost": [-9,46,17,34,43,92,41,-50,4,76] }
assert my_solution.placedCoins(**test_input) == [321632,1,321632,1,1,321632,1,1,5576,150328]

test_input = { "edges": [[0,6],[3,2],[3,1],[6,1],[8,7],[7,1],[5,1],[5,4],[9,4]], "cost": [86,50,10,-54,-85,-65,54,-19,39,37] }
assert my_solution.placedCoins(**test_input) == [475150,276250,1,1,1,204425,298350,1,1,1]

test_input = { "edges": [[0,8],[8,1],[9,2],[4,6],[7,4],[3,7],[3,8],[5,8],[5,9]], "cost": [-4,83,-97,40,86,-85,-6,-84,-16,-53] }
assert my_solution.placedCoins(**test_input) == [709070,1,1,43344,1,0,1,43344,709070,1]

test_input = { "edges": [[4,2],[1,3],[4,5],[7,5],[5,0],[8,1],[0,1],[0,6],[9,6]], "cost": [-72,-18,-27,38,13,-53,43,-95,-100,-77] }
assert my_solution.placedCoins(**test_input) == [408500,68400,1,1,1,65455,1,1,1,1]

test_input = { "edges": [[0,2],[5,2],[1,5],[7,4],[4,8],[1,8],[1,6],[6,3],[9,3]], "cost": [6,93,59,-14,1,-71,-87,95,16,-12] }
assert my_solution.placedCoins(**test_input) == [586815,141360,586815,1,1,586815,0,1,1520,1]

test_input = { "edges": [[0,1],[5,4],[4,2],[7,2],[7,3],[8,6],[3,6],[3,1],[9,1]], "cost": [66,-54,74,18,-77,-57,49,-82,-71,80] }
assert my_solution.placedCoins(**test_input) == [505120,505120,324786,467236,1,1,1,467236,1,1]

test_input = { "edges": [[3,8],[2,4],[5,6],[6,7],[0,8],[2,0],[2,6],[1,6],[9,1]], "cost": [92,-71,-10,-70,-56,-47,69,51,100,65] }
assert my_solution.placedCoins(**test_input) == [634800,1,274344,1,1,1,230253,1,1,1]

test_input = { "edges": [[0,3],[2,8],[5,6],[9,5],[7,9],[8,1],[1,4],[4,3],[9,3]], "cost": [-71,66,86,99,50,-29,-30,27,16,-65] }
assert my_solution.placedCoins(**test_input) == [561924,90816,1,561924,283800,1,1,1,1,52650]

test_input = { "edges": [[1,0],[2,7],[6,3],[0,4],[6,5],[5,8],[0,7],[9,0],[9,8]], "cost": [40,8,43,31,-27,-21,-21,55,-36,75] }
assert my_solution.placedCoins(**test_input) == [177375,1,1,1,1,13671,1,1,23436,56700]

test_input = { "edges": [[9,0],[9,3],[4,5],[1,6],[1,5],[8,5],[9,7],[8,2],[2,9]], "cost": [64,35,-1,-28,-50,38,-77,-13,-72,35] }
assert my_solution.placedCoins(**test_input) == [354816,1,210672,1,1,146300,1,1,210672,210672]

test_input = { "edges": [[5,3],[4,2],[5,2],[6,5],[5,1],[0,1],[0,8],[9,7],[9,8]], "cost": [-100,44,-76,55,8,-8,38,26,-41,-83] }
assert my_solution.placedCoins(**test_input) == [456500,91960,1,1,1,33440,1,1,88478,1]

test_input = { "edges": [[0,8],[9,3],[4,5],[8,5],[2,6],[7,8],[2,8],[1,2],[9,1]], "cost": [36,33,52,-24,7,-82,63,85,21,-64] }
assert my_solution.placedCoins(**test_input) == [446080,50688,108108,1,1,1,1,1,446080,1]

test_input = { "edges": [[9,2],[1,3],[8,4],[1,5],[1,9],[8,6],[7,9],[8,0],[0,9]], "cost": [-67,-82,-2,32,-97,6,-85,14,8,1] }
assert my_solution.placedCoins(**test_input) == [263840,0,1,1,1,1,1,1,65960,5248]

test_input = { "edges": [[7,0],[3,1],[7,3],[4,8],[8,5],[7,6],[2,6],[2,9],[8,9]], "cost": [-48,-69,-25,-65,65,51,85,34,17,-28] }
assert my_solution.placedCoins(**test_input) == [381225,1,56355,1,1,1,281775,381225,56355,56355]

test_input = { "edges": [[4,2],[7,2],[3,5],[6,3],[3,0],[7,0],[1,8],[1,0],[9,0]], "cost": [-14,39,40,-76,-69,66,43,82,-66,-45] }
assert my_solution.placedCoins(**test_input) == [430008,1,1,0,1,1,1,0,1,1]

test_input = { "edges": [[1,9],[3,7],[0,6],[7,0],[8,5],[2,5],[4,2],[4,0],[0,9]], "cost": [34,-87,-34,87,58,76,5,43,14,-45] }
assert my_solution.placedCoins(**test_input) == [383496,1,0,1,61712,1,1,1,1,1]

test_input = { "edges": [[7,1],[2,7],[4,3],[9,5],[6,7],[3,6],[8,3],[0,3],[0,9]], "cost": [-9,67,10,-67,91,29,-4,-35,60,-84] }
assert my_solution.placedCoins(**test_input) == [512148,1,1,365820,1,1,9380,0,1,1]

test_input = { "edges": [[2,3],[3,6],[3,7],[8,5],[1,5],[4,1],[4,0],[0,3],[9,3]], "cost": [88,-73,8,-82,64,-14,56,-82,-2,-89] }
assert my_solution.placedCoins(**test_input) == [642224,0,1,408688,65408,1,1,1,1,1]

test_input = { "edges": [[8,4],[7,3],[3,0],[0,6],[6,8],[8,2],[5,2],[1,5],[1,9]], "cost": [-50,34,51,-69,-28,72,61,-76,-30,76] }
assert my_solution.placedCoins(**test_input) == [398544,1,279072,1,1,186048,333792,1,279072,1]

test_input = { "edges": [[5,0],[1,6],[7,2],[4,9],[3,5],[3,7],[8,7],[6,7],[6,9]], "cost": [-75,-39,-30,-69,84,-7,98,92,-42,-51] }
assert my_solution.placedCoins(**test_input) == [757344,1,1,757344,1,757344,194922,757344,1,1]

test_input = { "edges": [[0,8],[2,5],[3,5],[1,6],[4,1],[8,4],[7,8],[8,5],[9,5]], "cost": [81,-76,-61,1,39,-3,-21,-33,42,-78] }
assert my_solution.placedCoins(**test_input) == [480168,1,1,1,62244,4758,1,1,248976,1]

test_input = { "edges": [[7,1],[0,2],[0,3],[6,5],[6,0],[0,7],[7,4],[9,4],[8,9]], "cost": [-37,-11,71,-57,-2,-78,87,55,-21,-66] }
assert my_solution.placedCoins(**test_input) == [447876,1,1,1,0,1,1,76230,1,1]

test_input = { "edges": [[0,9],[8,2],[3,7],[6,4],[1,5],[8,1],[6,8],[6,7],[7,9]], "cost": [61,-53,-97,-86,-91,-32,-8,79,100,75] }
assert my_solution.placedCoins(**test_input) == [882700,1,1,1,1,1,882700,882700,514100,882700]

test_input = { "edges": [[8,3],[4,6],[2,5],[2,1],[6,8],[8,0],[0,7],[1,7],[1,9]], "cost": [-40,-4,60,-47,35,39,-8,-12,-29,-43] }
assert my_solution.placedCoins(**test_input) == [121260,10320,1,1,1,1,1,30960,47705,1]

test_input = { "edges": [[3,0],[1,7],[6,3],[7,5],[4,5],[4,6],[6,9],[2,8],[9,2]], "cost": [36,84,5,32,-36,86,-35,58,36,-100] }
assert my_solution.placedCoins(**test_input) == [418992,1,1,418992,418992,418992,418992,1,1,0]

test_input = { "edges": [[1,0],[3,0],[2,5],[3,5],[6,4],[4,9],[7,3],[8,3],[3,9]], "cost": [39,22,-9,-65,9,-53,83,-94,-34,12] }
assert my_solution.placedCoins(**test_input) == [507130,1,1,507130,1,1,1,1,1,8964]

test_input = { "edges": [[2,0],[7,0],[4,3],[5,8],[7,9],[8,1],[3,1],[3,6],[9,6]], "cost": [-68,1,-68,65,-45,-26,36,-3,-85,40] }
assert my_solution.placedCoins(**test_input) == [375700,2210,1,248625,1,1,248625,248625,1,248625]

test_input = { "edges": [[4,0],[7,2],[2,6],[8,6],[5,6],[4,5],[4,3],[1,3],[1,9]], "cost": [-45,26,-26,-34,-33,81,-33,55,-87,52] }
assert my_solution.placedCoins(**test_input) == [317115,1,1,0,239598,232551,157905,1,1,1]

test_input = { "edges": [[2,1],[0,1],[6,3],[5,4],[6,5],[0,6],[9,0],[8,7],[9,7]], "cost": [94,76,-92,61,27,78,-94,39,-12,77] }
assert my_solution.placedCoins(**test_input) == [812912,1,1,1,1,1,128466,1,1,0]

test_input = { "edges": [[8,0],[3,2],[6,2],[1,2],[1,5],[4,7],[9,4],[8,5],[9,5]], "cost": [-6,-89,62,-82,-78,97,-71,58,-43,12] }
assert my_solution.placedCoins(**test_input) == [707906,452476,360964,1,1,707906,1,1,707906,0]

test_input = { "edges": [[1,0],[2,0],[4,0],[4,3],[4,6],[6,5],[7,5],[7,8],[9,8]], "cost": [-35,4,-1,-44,-27,-93,10,55,-14,93] }
assert my_solution.placedCoins(**test_input) == [380556,1,1,1,380556,121086,121086,0,1,1]

test_input = { "edges": [[0,6],[1,5],[8,2],[8,3],[9,6],[4,7],[5,8],[5,4],[4,9]], "cost": [26,22,32,-27,54,44,-58,-88,79,-77] }
assert my_solution.placedCoins(**test_input) == [535304,1,1,1,187704,111232,535304,1,0,535304]

test_input = { "edges": [[7,2],[3,1],[5,1],[8,5],[6,9],[7,0],[0,4],[4,8],[9,4]], "cost": [-70,-80,17,23,19,-71,84,-52,-21,-44] }
assert my_solution.placedCoins(**test_input) == [477120,1,1,1,477120,130640,1,1,130640,1]

test_input = { "edges": [[2,1],[3,6],[0,6],[7,2],[5,2],[5,4],[4,0],[0,8],[9,0]], "cost": [-27,11,-5,22,-81,48,-28,-85,85,-44] }
assert my_solution.placedCoins(**test_input) == [585225,1,4675,1,330480,20400,1,1,1,1]

test_input = { "edges": [[8,1],[2,5],[4,3],[8,5],[5,6],[6,3],[0,3],[7,0],[9,7]], "cost": [79,-73,75,-96,61,87,-74,69,84,41] }
assert my_solution.placedCoins(**test_input) == [618048,1,1,618048,1,548100,548100,1,1,1]

test_input = { "edges": [[1,0],[2,0],[3,0],[4,0],[0,7],[8,0],[8,6],[5,6],[5,9]], "cost": [-97,-61,-67,60,-75,-85,-21,75,-89,59] }
assert my_solution.placedCoins(**test_input) == [647475,1,1,1,1,1,105315,1,446335,1]

test_input = { "edges": [[0,1],[0,4],[9,3],[9,4],[5,2],[2,7],[6,8],[8,7],[8,9]], "cost": [-88,-7,-16,-49,-53,46,-19,38,-2,-12] }
assert my_solution.placedCoins(**test_input) == [214544,1,1,1,119462,1,1,0,13984,42826]

test_input = { "edges": [[2,0],[4,6],[4,5],[1,5],[3,1],[3,2],[2,7],[8,7],[7,9]], "cost": [-71,-13,56,3,95,74,79,81,-50,-24] }
assert my_solution.placedCoins(**test_input) == [607905,555370,607905,555370,1,555370,1,97200,1,1]

test_input = { "edges": [[3,2],[7,3],[4,8],[1,5],[6,7],[0,7],[8,1],[0,1],[9,0]], "cost": [25,-2,22,-40,-53,-17,-97,-49,29,36] }
assert my_solution.placedCoins(**test_input) == [185076,26129,1,1,1,1,1,104566,1,1]

test_input = { "edges": [[1,8],[2,6],[7,2],[7,3],[8,3],[8,4],[5,4],[5,0],[9,0]], "cost": [-54,-16,51,-79,73,-83,-54,5,45,14] }
assert my_solution.placedCoins(**test_input) == [478661,1,1,217566,311418,478661,1,0,217566,1]

test_input = { "edges": [[3,1],[4,0],[1,5],[6,1],[6,0],[9,7],[0,8],[0,2],[2,9]], "cost": [23,-50,-5,-36,-49,49,39,-82,-8,81] }
assert my_solution.placedCoins(**test_input) == [332100,88200,33210,1,1,1,88200,1,1,1]

test_input = { "edges": [[0,7],[8,1],[5,7],[8,2],[2,3],[3,7],[4,7],[4,6],[6,9]], "cost": [-12,-83,-3,-43,12,48,-46,19,-92,69] }
assert my_solution.placedCoins(**test_input) == [526884,1,0,0,0,1,1,526884,1,1]

test_input = { "edges": [[0,1],[2,5],[7,2],[7,6],[1,8],[1,3],[3,7],[4,7],[9,4]], "cost": [56,61,-17,-3,-100,-28,81,42,1,-86] }
assert my_solution.placedCoins(**test_input) == [696600,696600,1,696600,1,1,1,696600,1,1]

test_input = { "edges": [[0,3],[8,1],[3,6],[5,3],[2,8],[4,2],[4,7],[7,5],[5,9]], "cost": [-42,72,54,-46,57,95,94,21,-19,-92] }
assert my_solution.placedCoins(**test_input) == [642960,1,0,642960,221616,389880,1,221616,1,1]

test_input = { "edges": [[2,0],[2,4],[6,5],[8,6],[3,7],[3,1],[1,8],[2,1],[2,9]], "cost": [-58,-82,-70,33,20,-40,21,-93,18,-6] }
assert my_solution.placedCoins(**test_input) == [251658,251658,251658,1,1,1,1,1,0,1]

test_input = { "edges": [[1,5],[3,0],[0,2],[2,4],[5,2],[7,2],[6,7],[8,7],[7,9]], "cost": [-96,-98,41,59,-69,-51,-78,43,-40,-8] }
assert my_solution.placedCoins(**test_input) == [555072,1,328692,1,1,1,1,134160,1,1]

test_input = { "edges": [[0,4],[1,4],[3,6],[5,7],[4,6],[7,2],[4,2],[4,9],[9,8]], "cost": [-98,-100,-37,62,38,-54,56,56,1,-72] }
assert my_solution.placedCoins(**test_input) == [607600,1,111888,1,446400,1,1,1,1,1]

test_input = { "edges": [[8,0],[4,3],[6,3],[5,7],[6,8],[8,2],[1,2],[7,1],[9,7]], "cost": [-70,-59,-87,-64,56,-15,-62,-48,-58,-85] }
assert my_solution.placedCoins(**test_input) == [414120,0,0,1,1,1,222208,0,414120,1]

test_input = { "edges": [[3,0],[1,8],[6,2],[5,3],[4,5],[8,4],[7,8],[8,6],[6,9]], "cost": [-56,-14,-44,-2,31,34,-61,53,-39,-21] }
assert my_solution.placedCoins(**test_input) == [181048,1,1,142252,142252,142252,0,1,142252,1]

test_input = { "edges": [[2,1],[1,3],[5,8],[9,6],[8,1],[1,4],[4,0],[7,0],[7,9]], "cost": [-18,-10,25,-60,-48,4,14,38,26,16] }
assert my_solution.placedCoins(**test_input) == [109440,15600,1,1,74880,1,1,8512,1,1]

test_input = { "edges": [[0,2],[2,5],[3,4],[5,3],[6,8],[7,1],[5,1],[5,9],[8,9]], "cost": [46,96,34,76,19,29,-36,48,-71,-45] }
assert my_solution.placedCoins(**test_input) == [350208,1,350208,1,1,350208,1,1,1,0]

test_input = { "edges": [[0,2],[7,2],[3,4],[4,7],[5,1],[6,1],[7,6],[9,6],[8,9]], "cost": [4,70,65,-34,-59,-70,-83,-21,66,-10] }
assert my_solution.placedCoins(**test_input) == [406700,1,406700,1,1,1,406700,406700,1,1]

test_input = { "edges": [[0,1],[2,3],[5,2],[9,2],[6,9],[9,7],[1,8],[4,1],[9,4]], "cost": [54,72,-52,45,-62,96,-54,28,-76,86] }
assert my_solution.placedCoins(**test_input) == [594432,594432,0,1,371520,1,1,1,1,371520]

test_input = { "edges": [[1,0],[0,4],[3,5],[6,7],[6,3],[3,8],[8,0],[0,2],[9,2]], "cost": [-98,-85,82,-30,64,-76,36,-54,84,85] }
assert my_solution.placedCoins(**test_input) == [708050,1,1,147744,1,1,1,1,344736,1]

test_input = { "edges": [[0,8],[2,6],[4,7],[5,1],[1,9],[3,7],[3,8],[6,8],[9,6]], "cost": [60,-76,-76,38,-5,-33,-80,-36,28,63] }
assert my_solution.placedCoins(**test_input) == [383040,1,1,6840,1,1,383040,1,383040,158004]

test_input = { "edges": [[5,3],[6,5],[7,6],[6,2],[2,1],[0,1],[0,9],[4,8],[4,9]], "cost": [-56,-92,-10,-70,52,22,43,37,88,48] }
assert my_solution.placedCoins(**test_input) == [566720,276920,35002,1,1,1,35002,1,1,219648]

test_input = { "edges": [[8,2],[9,4],[1,7],[3,1],[3,5],[5,8],[5,0],[0,6],[9,6]], "cost": [-70,17,-31,41,-93,17,-19,21,-66,-29] }
assert my_solution.placedCoins(**test_input) == [266910,1,1,14637,1,83886,0,1,1,1]

test_input = { "edges": [[8,1],[2,4],[7,3],[2,3],[2,6],[6,5],[0,5],[0,8],[9,8]], "cost": [88,86,55,-61,3,-70,12,44,-92,-72] }
assert my_solution.placedCoins(**test_input) == [582912,1,7260,1,1,234850,29040,1,569664,1]

test_input = { "edges": [[0,7],[1,3],[1,6],[4,2],[6,2],[5,6],[5,9],[7,8],[9,8]], "cost": [15,78,-48,58,-27,28,60,-9,-64,-71] }
assert my_solution.placedCoins(**test_input) == [354432,1,1,1,1,271440,271440,354432,354432,271440]

test_input = { "edges": [[4,0],[8,0],[5,6],[8,6],[6,1],[7,1],[3,7],[2,3],[9,2]], "cost": [14,10,10,-73,-43,19,92,62,16,-27] }
assert my_solution.placedCoins(**test_input) == [288788,122202,1,19710,1,1,181332,122202,181332,1]

test_input = { "edges": [[8,0],[3,1],[1,2],[8,5],[6,7],[4,7],[9,4],[2,8],[2,9]], "cost": [97,35,-74,5,65,5,86,61,-55,53] }
assert my_solution.placedCoins(**test_input) == [542230,1,340990,1,340990,1,1,1,350020,340990]

test_input = { "edges": [[0,1],[7,0],[8,2],[3,4],[4,7],[4,8],[4,6],[5,6],[9,5]], "cost": [-74,40,73,-97,-62,9,-96,-98,-38,63] }
assert my_solution.placedCoins(**test_input) == [693938,1,1,1,679776,1,0,693938,1,1]

test_input = { "edges": [[2,3],[0,3],[0,6],[6,5],[7,1],[1,5],[8,5],[4,5],[9,4]], "cost": [4,-30,59,61,78,-22,-24,85,-19,-89] }
assert my_solution.placedCoins(**test_input) == [404430,1,1,1,1,226950,226950,1,1,1]

test_input = { "edges": [[1,2],[5,4],[5,6],[7,1],[3,1],[3,5],[5,8],[0,5],[0,9]], "cost": [11,-80,95,64,-76,56,61,22,13,-58] }
assert my_solution.placedCoins(**test_input) == [577600,0,1,133760,1,577600,1,1,1,1]

test_input = { "edges": [[1,9],[2,7],[3,5],[4,3],[0,4],[0,6],[8,0],[7,0],[9,7]], "cost": [-69,18,-39,-59,-48,-65,97,1,74,-63] }
assert my_solution.placedCoins(**test_input) == [435045,1,1,1,0,1,1,44226,1,1]

test_input = { "edges": [[0,6],[1,4],[5,4],[6,8],[3,8],[5,3],[5,2],[7,2],[9,7]], "cost": [-84,27,16,75,49,4,72,46,-17,48] }
assert my_solution.placedCoins(**test_input) == [264600,1,35328,176400,1,108192,264600,1,176400,1]

test_input = { "edges": [[0,9],[1,7],[6,3],[8,7],[7,3],[5,3],[2,5],[2,4],[4,9]], "cost": [1,-53,88,-67,-55,-31,-89,-39,21,-96] }
assert my_solution.placedCoins(**test_input) == [751872,1,524744,125223,524744,125223,1,43407,1,751872]

test_input = { "edges": [[3,6],[0,6],[8,0],[7,4],[4,1],[2,1],[2,9],[8,5],[9,5]], "cost": [78,-10,-51,-50,-55,-72,-7,31,-94,4] }
assert my_solution.placedCoins(**test_input) == [527904,17050,86955,1,1,122760,1,1,209808,86955]

test_input = { "edges": [[2,5],[4,7],[4,5],[5,3],[3,6],[6,0],[1,0],[8,1],[9,8]], "cost": [-19,93,-23,-86,54,-70,-70,9,69,13] }
assert my_solution.placedCoins(**test_input) == [559860,83421,1,325080,1,86940,325080,1,1,1]

test_input = { "edges": [[2,7],[3,9],[7,5],[4,5],[4,1],[6,1],[6,0],[8,0],[0,9]], "cost": [45,-53,-16,-26,99,50,33,-57,-97,74] }
assert my_solution.placedCoins(**test_input) == [547371,299079,1,1,90288,45600,299079,1,1,1]

test_input = { "edges": [[5,0],[9,1],[3,6],[2,4],[2,6],[6,9],[8,7],[7,5],[5,9]], "cost": [-14,-4,-49,52,-45,77,-17,-79,21,-33] }
assert my_solution.placedCoins(**test_input) == [298067,1,1,1,1,298067,114660,1,1,114660]

test_input = { "edges": [[6,3],[7,0],[2,0],[2,4],[9,4],[1,8],[1,6],[5,6],[9,5]], "cost": [-58,-55,17,68,37,-32,91,-63,79,69] }
assert my_solution.placedCoins(**test_input) == [496041,1,496041,1,496041,488852,488852,1,1,496041]

test_input = { "edges": [[1,8],[0,3],[2,4],[0,2],[8,5],[0,5],[7,0],[7,6],[9,6]], "cost": [-8,-99,36,31,94,5,-35,54,33,19] }
assert my_solution.placedCoins(**test_input) == [325710,1,1,1,1,0,1,0,1,1]

test_input = { "edges": [[1,0],[1,7],[3,4],[4,5],[5,6],[7,5],[5,2],[8,2],[2,9]], "cost": [70,-75,-13,30,-87,20,-67,76,20,-30] }
assert my_solution.placedCoins(**test_input) == [495900,495900,7800,1,1,174870,1,443004,1,1]

test_input = { "edges": [[5,1],[2,1],[0,2],[6,0],[0,3],[3,7],[9,7],[4,8],[9,4]], "cost": [-10,-31,-7,-77,64,-80,-53,37,1,10] }
assert my_solution.placedCoins(**test_input) == [394240,1,0,23680,1,1,1,23680,1,640]

test_input = { "edges": [[2,0],[1,2],[2,8],[4,3],[4,7],[5,9],[6,9],[8,7],[7,9]], "cost": [-80,77,-18,-72,11,66,82,80,32,61] }
assert my_solution.placedCoins(**test_input) == [505120,1,505120,1,1,1,1,432960,432960,330132]

test_input = { "edges": [[0,3],[1,0],[1,8],[5,4],[9,6],[7,4],[9,4],[8,2],[9,2]], "cost": [70,-14,-91,98,-12,30,-24,79,-62,11] }
assert my_solution.placedCoins(**test_input) == [552916,445718,172536,1,0,1,1,1,445718,26070]

test_input = { "edges": [[5,8],[2,6],[2,0],[0,3],[7,8],[8,4],[3,4],[1,3],[1,9]], "cost": [55,69,29,87,27,-35,-83,71,-82,-8] }
assert my_solution.placedCoins(**test_input) == [592122,1,1,426213,203770,1,1,1,203770,1]

test_input = { "edges": [[1,9],[5,4],[5,3],[6,3],[6,2],[2,8],[0,7],[0,9],[8,9]], "cost": [-25,28,47,-75,-78,-39,23,93,-20,61] }
assert my_solution.placedCoins(**test_input) == [544050,1,274950,0,1,1,134550,1,274950,356850]

test_input = { "edges": [[5,0],[1,8],[6,4],[4,9],[7,3],[8,5],[3,5],[3,2],[9,2]], "cost": [-11,-91,-54,53,58,16,-60,85,20,51] }
assert my_solution.placedCoins(**test_input) == [464100,1,187920,275400,1,464100,1,1,1,0]

test_input = { "edges": [[1,3],[1,4],[2,4],[6,5],[7,5],[0,5],[9,0],[8,2],[9,2]], "cost": [-74,26,99,58,42,-55,-1,-56,29,-35] }
assert my_solution.placedCoins(**test_input) == [410256,1,241164,1,63336,0,1,1,1,241164]

test_input = { "edges": [[2,5],[5,3],[0,4],[5,9],[6,1],[7,1],[7,0],[0,9],[8,9]], "cost": [72,68,-18,95,87,-58,-55,20,40,2] }
assert my_solution.placedCoins(**test_input) == [595080,1,1,1,1,99180,1,0,1,99180]

test_input = { "edges": [[1,6],[3,2],[9,3],[6,5],[5,9],[7,0],[4,8],[0,4],[0,9]], "cost": [85,19,-56,-71,41,-72,59,30,55,67] }
assert my_solution.placedCoins(**test_input) == [434520,1,1,1,1,0,1,1,1,342504]

test_input = { "edges": [[2,1],[7,1],[0,3],[8,4],[0,5],[7,6],[0,6],[8,0],[9,8]], "cost": [13,4,84,36,29,-97,-59,-40,77,41] }
assert my_solution.placedCoins(**test_input) == [480732,1,1,1,1,1,198240,0,91553,1]

test_input = { "edges": [[2,1],[4,5],[6,3],[1,3],[1,0],[7,0],[8,7],[5,8],[9,5]], "cost": [85,64,-67,-60,5,-14,31,-84,47,-36] }
assert my_solution.placedCoins(**test_input) == [478380,257280,1,1,1,2520,1,142128,23688,1]

test_input = { "edges": [[6,1],[4,2],[7,4],[5,7],[0,8],[6,0],[3,6],[7,3],[7,9]], "cost": [-51,-55,82,25,-53,13,-15,98,39,29] }
assert my_solution.placedCoins(**test_input) == [313404,1,1,233044,1,1,285670,233044,1,1]

test_input = { "edges": [[0,2],[5,1],[6,2],[7,3],[5,4],[5,9],[6,9],[7,9],[8,9]], "cost": [-96,-75,-58,26,-73,-25,-9,87,57,3] }
assert my_solution.placedCoins(**test_input) == [626400,1,476325,1,1,0,476325,1,1,476325]

test_input = { "edges": [[0,4],[0,9],[5,1],[2,6],[3,7],[3,8],[1,8],[1,2],[2,9]], "cost": [-58,20,21,77,-96,53,-77,-66,-32,42] }
assert my_solution.placedCoins(**test_input) == [569184,162624,391314,1,1,1,1,1,162624,391314]

test_input = { "edges": [[2,4],[5,2],[6,3],[3,0],[7,5],[8,5],[1,8],[1,0],[0,9]], "cost": [-59,-25,-25,-78,22,29,9,-12,-11,-5] }
assert my_solution.placedCoins(**test_input) == [133458,18125,1,1,1,8700,1,1,8700,1]

test_input = { "edges": [[8,1],[3,2],[5,4],[6,3],[0,3],[8,5],[5,7],[7,0],[9,0]], "cost": [86,-87,-96,-74,51,75,-76,74,-2,-60] }
assert my_solution.placedCoins(**test_input) == [718272,1,1,0,1,13050,1,283050,1,1]