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:
coins[i] - k points. If coins[i] - k is negative then you will lose abs(coins[i] - k) points.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:
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.length2 <= n <= 1050 <= coins[i] <= 104edges.length == n - 10 <= edges[i][0], edges[i][1] < n0 <= k <= 104This approach leverages Depth-First Search (DFS) to traverse the tree and calculate the maximum possible points from collecting coins. We perform a DFS starting from the root node (0) and for each node, decide whether to collect its coins using the first or second method. The first method subtracts k from the node's coin value, whereas the second reduces all subtree nodes' coins by half. The key is to recursively calculate and choose the best option for every node.
The C solution involves organizing the graph structure using adjacency lists. The DFS function explores each node, calculating potential points for both ways of collecting coins (subtracting k or halving the subtree's coins). By comparing results, it ensures the maximum points are achieved.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) since we visit each node once.
Space Complexity: O(n) to store adjacency list and recursion stack.
This approach uses dynamic programming to solve the problem on trees, known as DP on trees. We maintain a dp array to store the maximum points that can be collected from each subtree starting from a node. The transition relations help in deciding whether a node should be included without penalties or adjusted by halving the subtree values.
The C code outlines the skeleton where DP on trees is applied to compute potential points efficiently. By transforming each edge into transitions in the dp table, it evaluates maximal paths recursively and optimizes score calculation.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), typical for tree dynamic programming where each node contributes.
Space Complexity: O(n) for storing intermediate dp results.
| Approach | Complexity |
|---|---|
| DFS with Subtree Points Calculation | Time Complexity: O(n) since we visit each node once. |
| Dynamic Programming on Trees | Time Complexity: O(n), typical for tree dynamic programming where each node contributes. |
I solved too many Leetcode problems • NeetCodeIO • 101,495 views views
Watch 9 more video solutions →Practice Maximum Points After Collecting Coins From All Nodes with our built-in code editor and test cases.
Practice on FleetCode