Maximum coins such that root to leaf path sum is positive
source link: https://www.geeksforgeeks.org/maximum-coins-such-that-root-to-leaf-path-sum-is-positive/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Maximum coins such that root to leaf path sum is positive
Given tree with N vertices rooted at node 0, edges given by array edges[][] and array arr[] of size N representing coins[] on each node. In one operation pick any node and collect all its coins. Task for this problem is to find maximum number of coins collected such that path sum from root node to any leaf node remains positive (path sum from root node to leaf node is total coins present on nodes of simple path between root to leaf).
Examples:
Input: N = 6, A[] = {5, 2, 5, 2, 1, 1 }, edges[][2] = {{0, 1}, {0, 2}, {0, 3}, {2, 4}, {4, 5}}
Output: 11
Explanation: We can collect coins from node 1, 2, 3, 4 and 5. Total coins = 2 + 5 + 2 + 1 + 1 = 11.
Since root node 0 is non zero any path starting from root node to any leaf will be non zero.Input: N = 7, A[] = { 20, 10, 9, 7, 4, 3, 5 }, edges[][2] = { {0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6} }
Output: 40
Explanation: We can collect coins from nodes 0, 2, 3 and 4. Total coins = 20 + 9 + 7 + 4 = 40
- path sum from 0 to 4 is equal to 10.
- path sum from 0 to 3 is equal to 10.
- path sum from 0 to 5 is equal to 3.
- path sum from 0 to 6 is equal to 5.
So, path sum from root node 0 to any leaf is non-zero.
Approach: To solve the problem, follow the below idea:
Observation: We have two choices to make for every subtree root. Either we pick the coins present on root of subtree or all coins on present on its descendants. Problem is turned into other way around lets find minimum coins required to keep path sum from root node to any leaf node non-zero.
Tree Dynamic Programming can be used to solve this problem. The main concept of DP in the problem will be:
DP[v] will store minimum coins required so path sum from node v to any leaf node is non-zero.
Transition: dp[v] = min(A[v], ∑dp[ui])
Step-by-step algorithm:
- Declaring Adjacency list adj[N] and fill the adjacency list by iterating on N – 1 edges.
- Declaring DP[] array of length N.
- Declare dfs function which takes two parameters as input v node and p its parent.
- Iterate over all child’s u and find out dp[v] = ∑dp[ui]
- base case if v is not zero and there is only one element present in adjacent of v then update dp[v] as A[v]
- otherwise update dp[v] = min(dp[v], A[v])
- Call dfs(0, -1) function which is called for node 0 and its parent being -1
- Declare variable totalCoins which has sum of all coins present on every node of v
- Return totalCoins – dp[0]
Below is the implementation of the approach:
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to Find maximum coins collected// from tree such that path sum from root node// to any leaf node is non zeroint maxCoinsCollect(int N, int edges[][2], int A[]){// Declaring Adjacency List for treevector<vector<int> > adj(N);// Filling Adjacency Listfor (int i = 0; i < N - 1; i++) {adj[edges[i][0]].push_back(edges[i][1]);adj[edges[i][1]].push_back(edges[i][0]);}// DP array initalized with zerovector<int> dp(N, 0);// dfs functionauto dfs = [&](int v, int p, auto&& dfs) -> void {// iterating over child nodesfor (auto& u : adj[v]) {// if child of v is not equal to its parentif (u != p) {// call dfs function for child udfs(u, v, dfs);// adding maximum coins chosen for child// nodesdp[v] += dp[u];}}// base caseif (v != 0 and adj[v].size() == 1)dp[v] = A[v];else// Either chose maximum coins by child nodes or// coins present on root of the treedp[v] = min(dp[v], A[v]);};// calling dfs functiondfs(0, N, dfs);// variable to store total coinsint totalCoins = accumulate(A, A + N, 0);// returning final answer totalCoins - minimum// coins required so that path sum from root to// any leaf node is non zeroreturn totalCoins - dp[0];}// Driver Codeint main(){// Inputint N = 6;int A[] = { 5, 2, 5, 2, 1, 1 };int edges[][2] = {{ 0, 1 }, { 0, 2 }, { 0, 3 }, { 2, 4 }, { 4, 5 }};// Function Callcout << maxCoinsCollect(N, edges, A) << endl;return 0;} |
Output
Time Complexity: O(N), where N is the number of nodes in the tree.
Auxiliary Space: O(N)
Whether you're preparing for your first job interview or aiming to upskill in this ever-evolving tech landscape, GeeksforGeeks Courses are your key to success. We provide top-quality content at affordable prices, all geared towards accelerating your growth in a time-bound manner. Join the millions we've already empowered, and we're here to do the same for you. Don't miss out - check it out now!
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK