Collect Maximum Points from all Nodes using Dynamic Programming
Approach: The problem can be solved using the following approach:
It can be observed that operation of type 2 can be applied at most 30 times because each type 2 operation reduces the value points at a node i to points[i]/2 and if 30 operations of type 2 are applied then node with any value up to 10^9 will get reduced to 0 as 230>109 so type 2 operation will be applied at most 30 times. Now we can apply Dynamic Programming to solve this problem. The state will be: dp[curr][i] = maximum points that can be collected at the subtree rooted at node curr such that type 2 operation are already applied i times on the ancestors till now. The answer will be max(dp[1][0], dp[1][1], dp[1][2], …… , dp[1][30]).
Follow the steps to solve the problem:
- Create a 2D dp[][] array of size N X 30 , where dp[curr][i] represents maximum points that can be collected at the subtree rooted at node curr with type 2 operation already applied i times on the ancestors till now.
- Iterate through the nodes using DFS. At any node curr, dp[curr][i] will be calculated by:
- Applying Type 1 Operation: Let sum1 denote the maximum points that can be collected from the subtree rooted at node curr if type 1 operation is performed on node curr. So sum1 will be:
, where x is child of node curr and pt is the points at node curr when operation 2 have applied i times before visiting node curr. - Applying Type 2 Operation: Let sum2 denote the maximum points that can be collected from the subtree rooted at node curr if type 2 operation is performed on node curr. So sum2 will be:
, where x is child of node curr and pt is the points at node curr when operation 2 have applied i times before visiting node curr. - dp[curr][i] will be max(sum1, sum2).
- Applying Type 1 Operation: Let sum1 denote the maximum points that can be collected from the subtree rooted at node curr if type 1 operation is performed on node curr. So sum1 will be:
- The final answer will be max(dp[1][0], dp[1][1], ……, dp[1][29], dp[1][30]).
Below is the implementation of above approach:
C++
#include <bits/stdc++.h> using namespace std; // Depth-First Search (DFS) function to process the tree void dfs(vector<vector< int > >& adj, vector< int >& points, vector<vector< int > >& dp, int k, int curr, int par) { // Traverse the children nodes of the current node for ( auto x : adj[curr]) { if (par != x) { dfs(adj, points, dp, k, x, curr); } } int pt = points[curr - 1]; // Loop for 30 iterations, corresponding to applying // type 2 operation at most 30 times for ( int i = 0; i < 30; i++) { int sum2 = pt / 2, sum1 = pt - k; // Iterate through the child nodes for ( auto x : adj[curr]) { if (x != par) { sum2 = sum2 + dp[x][i + 1]; sum1 = sum1 + dp[x][i]; } } pt = pt / 2; // Update the DP values for the current node and // iteration dp[curr][i] = max(sum1, sum2); } } // Function to calculate the maximum points int maximumPoints(vector<vector< int > >& edges, vector< int >& points, int k) { int n = points.size(); vector<vector< int > > adj(n + 1); // Create an adjacency list based on the input edges for ( int i = 0; i < edges.size(); i++) { adj[edges[i][0]].push_back(edges[i][1]); adj[edges[i][1]].push_back(edges[i][0]); } // Initialize a 2D DP array with zeros vector<vector< int > > dp(n + 1, vector< int >(31, 0)); // Perform DFS to calculate DP values dfs(adj, points, dp, k, 1, -1); int ans = 0; // Find the maximum points for all iterations for ( int i = 0; i < 31; i++) { ans = max(ans, dp[1][i]); } return ans; } // Driver Code int main() { int N = 5; int k = 4; vector<vector< int > > edges = { { 1, 2 }, { 1, 3 }, { 1, 4 }, { 2, 5 } }; vector< int > points = { 7, 0, 9, 5, 3 }; cout << maximumPoints(edges, points, k); } |
Java
import java.util.*; // Nikunj Sonigara class Main { // Depth-First Search (DFS) function to process the tree static void dfs(List<List<Integer>> adj, List<Integer> points, List<List<Integer>> dp, int k, int curr, int par) { // Traverse the children nodes of the current node for ( int x : adj.get(curr)) { if (par != x) { dfs(adj, points, dp, k, x, curr); } } int pt = points.get(curr - 1 ); // Loop for 30 iterations, corresponding to applying // type 2 operation at most 30 times for ( int i = 0 ; i < 30 ; i++) { int sum2 = pt / 2 , sum1 = pt - k; // Iterate through the child nodes for ( int x : adj.get(curr)) { if (x != par) { sum2 = sum2 + dp.get(x).get(i + 1 ); sum1 = sum1 + dp.get(x).get(i); } } pt = pt / 2 ; // Update the DP values for the current node and // iteration dp.get(curr).set(i, Math.max(sum1, sum2)); } } // Function to calculate the maximum points static int maximumPoints(List<List<Integer>> edges, List<Integer> points, int k) { int n = points.size(); List<List<Integer>> adj = new ArrayList<>(n + 1 ); // Initialize adjacency list for ( int i = 0 ; i <= n; i++) { adj.add( new ArrayList<>()); } // Create an adjacency list based on the input edges for (List<Integer> edge : edges) { adj.get(edge.get( 0 )).add(edge.get( 1 )); adj.get(edge.get( 1 )).add(edge.get( 0 )); } // Initialize a 2D DP array with zeros List<List<Integer>> dp = new ArrayList<>(n + 1 ); for ( int i = 0 ; i <= n; i++) { dp.add( new ArrayList<>( 31 )); for ( int j = 0 ; j < 31 ; j++) { dp.get(i).add( 0 ); } } // Perform DFS to calculate DP values dfs(adj, points, dp, k, 1 , - 1 ); int ans = 0 ; // Find the maximum points for all iterations for ( int i = 0 ; i < 31 ; i++) { ans = Math.max(ans, dp.get( 1 ).get(i)); } return ans; } // Driver Code public static void main(String[] args) { int N = 5 ; int k = 4 ; List<List<Integer>> edges = List.of( List.of( 1 , 2 ), List.of( 1 , 3 ), List.of( 1 , 4 ), List.of( 2 , 5 ) ); List<Integer> points = List.of( 7 , 0 , 9 , 5 , 3 ); System.out.println(maximumPoints(edges, points, k)); } } |
Python3
# Depth-First Search (DFS) function to process the tree def dfs(adj, points, dp, k, curr, par): # Traverse the children nodes of the current node for x in adj[curr]: if par ! = x: dfs(adj, points, dp, k, x, curr) pt = points[curr - 1 ] # Loop for 30 iterations, corresponding to applying # type 2 operation at most 30 times for i in range ( 30 ): sum2, sum1 = pt / / 2 , pt - k # Iterate through the child nodes for x in adj[curr]: if x ! = par: sum2 + = dp[x][i + 1 ] sum1 + = dp[x][i] pt / / = 2 # Update the DP values for the current node and iteration dp[curr][i] = max (sum1, sum2) # Function to calculate the maximum points def maximumPoints(edges, points, k): n = len (points) adj = [[] for _ in range (n + 1 )] # Create an adjacency list based on the input edges for edge in edges: adj[edge[ 0 ]].append(edge[ 1 ]) adj[edge[ 1 ]].append(edge[ 0 ]) # Initialize a 2D DP array with zeros dp = [[ 0 ] * 31 for _ in range (n + 1 )] # Perform DFS to calculate DP values dfs(adj, points, dp, k, 1 , - 1 ) ans = 0 # Find the maximum points for all iterations for i in range ( 31 ): ans = max (ans, dp[ 1 ][i]) return ans # Driver Code def main(): N = 5 k = 4 edges = [[ 1 , 2 ], [ 1 , 3 ], [ 1 , 4 ], [ 2 , 5 ]] points = [ 7 , 0 , 9 , 5 , 3 ] print (maximumPoints(edges, points, k)) if __name__ = = "__main__" : main() |
C#
using System; using System.Collections.Generic; class MaximumPointsCalculator { // Depth-First Search (DFS) function to process the tree static void Dfs(List<List< int >> adj, List< int > points, List<List< int >> dp, int k, int curr, int par) { // Traverse the children nodes of the current node foreach ( int x in adj[curr]) { if (par != x) { Dfs(adj, points, dp, k, x, curr); } } int pt = points[curr - 1]; // Loop for 30 iterations, corresponding to applying // type 2 operation at most 30 times for ( int i = 0; i < 30; i++) { int sum2 = pt / 2, sum1 = pt - k; // Iterate through the child nodes foreach ( int x in adj[curr]) { if (x != par) { sum2 = sum2 + dp[x][i + 1]; sum1 = sum1 + dp[x][i]; } } pt = pt / 2; // Update the DP values for the current node and // iteration dp[curr][i] = Math.Max(sum1, sum2); } } // Function to calculate the maximum points static int MaximumPoints(List<List< int >> edges, List< int > points, int k) { int n = points.Count; List<List< int >> adj = new List<List< int >>(); // Initialize adjacency list for ( int i = 0; i <= n; i++) { adj.Add( new List< int >()); } // Create an adjacency list based on the input edges foreach (List< int > edge in edges) { adj[edge[0]].Add(edge[1]); adj[edge[1]].Add(edge[0]); } // Initialize a 2D DP array with zeros List<List< int >> dp = new List<List< int >>(); for ( int i = 0; i <= n; i++) { dp.Add( new List< int >( new int [31])); } // Perform DFS to calculate DP values Dfs(adj, points, dp, k, 1, -1); int ans = 0; // Find the maximum points for all iterations for ( int i = 0; i < 31; i++) { ans = Math.Max(ans, dp[1][i]); } return ans; } // Driver Code static void Main( string [] args) { int k = 4; List<List< int >> edges = new List<List< int >> { new List< int > { 1, 2 }, new List< int > { 1, 3 }, new List< int > { 1, 4 }, new List< int > { 2, 5 } }; List< int > points = new List< int > { 7, 0, 9, 5, 3 }; Console.WriteLine(MaximumPoints(edges, points, k)); } } |
Javascript
function dfs(adj, points, dp, k, curr, par) { // Traverse the children nodes of current node for (let x of adj[curr]) { if (par !== x) { dfs(adj, points, dp, k, x, curr); } } let pt = points[curr - 1]; // Loop for 30 iterations, corresponding to applying for (let i = 0; i < 30; i++) { let sum2 = Math.floor(pt / 2); let sum1 = pt - k; // Iterate through the child nodes for (let x of adj[curr]) { if (x !== par) { sum2 += dp[x][i + 1]; sum1 += dp[x][i]; } } pt = Math.floor(pt / 2); // Update the DP values for the current node and iteration dp[curr][i] = Math.max(sum1, sum2); } } // Function to calculate the maximum points function GFG(edges, points, k) { const n = points.length; const adj = Array.from({ length: n + 1 }, () => []); // Create an adjacency list based on input edges for (let i = 0; i < edges.length; i++) { adj[edges[i][0]].push(edges[i][1]); adj[edges[i][1]].push(edges[i][0]); } // Initialize a 2D DP array with the zeros const dp = Array.from({ length: n + 1 }, () => Array(31).fill(0)); dfs(adj, points, dp, k, 1, -1); let ans = 0; // Find the maximum points for the all iterations for (let i = 0; i < 31; i++) { ans = Math.max(ans, dp[1][i]); } return ans; } // Driver Code const N = 5; const k = 4; const edges = [[1, 2], [1, 3], [1, 4], [2, 5]]; const points = [7, 0, 9, 5, 3]; console.log(GFG(edges, points, k)); |
Output
10
Time Complexity: O(N), where N is number of nodes in the tree
Auxiliary Space: O(N)
Collect Maximum Points from all Nodes
Given a tree of N nodes and N-1 edges rooted at Node 1, an array points[] of size N, where points[i] denote the number of points at the vertex i and an integer k. A Node can be visited only if its ancestors have already been visited. When any Node i is visited 2 types of operations can be applied:
- Type 1: Add (
points[i] - k)
points to total points. - Type 2: Add
floor(points[i] / 2)
points to total points and all the nodes j in the subtree of node i becomesfloor(coins[j] / 2)
.
The task is to determine the maximum points that can be collected from all nodes.
Constraints:
2 <= N <= 10^5
0 <= points [i] <= 10^9
0 <= x <= 10^9
Examples:
Input: N=5, K=4
Output: 10
Explanation:
- Type 1 operation is performed on Node 1, so points obtained = (7 – 4) = 3
- Type 1 operation is performed on Node 3, so points obtained = (9 – 4) = 5
- Type 2 operation is performed on Node 4, so points obtained = floor(5/2) = 2 and since Node 4 has no nodes in the subtree, therefore no other node’s value gets reduced.
- Type 2 operation is performed on Node 2, so points obtained = floor(0/2) = 0 and since Node 5 lies in the subtree of node 2, value of node 5 gets reduced to floor(3/2) = 1.
- Type 2 operation is performed on Node 5, so points obtained = floor(1/2) = 0 and since Node 5 has no nodes in the subtree, therefore no other node’s value gets reduced.
Total points obtained = 3 + 5 + 2 + 0 + 0 = 10
Input: N=3, K=0
Output: 7
Explanation:
- Type 1 operation is performed in Node 1, so points obtained = (2 – 0) = 2
- Type 1 operation is performed in Node 2, so points obtained = (2 – 0) = 2
- Type 1 operation is performed in Node 3, so points obtained = (3 – 0) = 3
Total points obtained = 2 + 2 + 3 = 7