2920. Maximum Points After Collecting Coins From All Nodes
Description
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. Ifcoins[i] - k
is negative then you will loseabs(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 thenodej
present in the subtree ofnodei
,coins[j]
will get reduced tofloor(coins[j] / 2)
.
Return the maximum points you can get after collecting the coins from all the tree nodes.
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.
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
Solutions
Solution 1: Memoization Search
First, we construct a graph $g$ based on the edges given in the problem, where $g[i]$ represents all adjacent nodes of node $i$. Then we can use the method of memoization search to solve this problem.
We design a function $dfs(i, fa, j)$, which represents that the current node is $i$, the parent node is $fa$, the number of gold coins of the current node needs to be shifted to the right by $j$ bits, and the maximum score that can be obtained.
The execution process of the function $dfs(i, fa, j)$ is as follows:
If we use the first method to collect the gold coins of the current node, then the score of the current node is $(coins[i] >> j) - k$. Then we traverse all the adjacent nodes $c$ of the current node. If $c$ is not equal to $fa$, then we add the result of $dfs(c, i, j)$ to the score of the current node.
If we use the second method to collect the gold coins of the current node, then the score of the current node is $coins[i] >> (j + 1)$. Then we traverse all the adjacent nodes $c$ of the current node. If $c$ is not equal to $fa$, then we add the result of $dfs(c, i, j + 1)$ to the score of the current node. Note that since the maximum value of $coins[i]$ given in the problem is $10^4$, we can only shift to the right by at most $14$ bits, so that the value of $coins[i] >> (j + 1)$ is $0$.
Finally, we return the maximum score that can be obtained by using the two methods at the current node.
In order to avoid repeated calculations, we use the method of memoization search and store the result of $dfs(i, fa, j)$ in $f[i][j]$, where $f[i][j]$ represents that the current node is $i$, the parent node is $fa$, the number of gold coins of the current node needs to be shifted to the right by $j$ bits, and the maximum score that can be obtained.
The time complexity is $O(n \times \log M)$, and the space complexity is $O(n \times \log M)$. Where $M$ represents the maximum value of $coins[i]$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
|