#2920
Maximum Points After Collecting Coins From All Nodes
master · 1815 · lc hard +32 · verified · 36.4% accepted · 238 likes · top 14%
Description
A rooted undirected tree has n nodes labeled 0 to n - 1 with root at node 0. The edges array gives the tree structure, and coins[i] is the number of coins at node i. You also have an integer k.
Coins must be collected top-down: a node's coins can only be gathered after all ancestor nodes have been processed.
For each node you choose one of two ways to collect:
- Gain coins[i] - k points (may be negative).
- Gain floor(coins[i] / 2) points, which also halves every descendant's coin count.
Return the maximum total points over all collection choices.
Example 1:
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:
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.
Code
1
2
3