Minimize Increments for Equal Path Sum from Root to Any Leaf
Given arrays arr[] and edges[] where edges[i] denotes an undirected edge from edges[i][0] to edges[i][1] and arr[i] represents the value of the ith node. The task is to find the minimum number of increments by 1 required for any node, such that the sum of values along any path from the root to a leaf is equal.
Examples:
Input: N = 7, edges[] = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6}}, A[] = {1, 5, 2, 2, 3, 3, 1}
Output: 6
Explanation:
- 1st Operation: Increment A[3] by one, so A[3] becomes 3.
- 2nd Operation: Increment A[6] by one, so A[6] becomes 3.
- 3rd Operation: Increment A[6] by one, so A[6] becomes 4.
- 4th Operation: Increment A[2] by one, so A[2] becomes 3.
- 5th Operation: Increment A[2] by one, so A[2] becomes 4.
- 6th Operation: Increment A[2] by one, so A[2] becomes 5.
In total of 6 operations all paths’ sums from root node to leaf node becomes 9.
Input: N = 3, edges[] = {{0, 1}, {0, 2}}, A[] = {5, 3, 3}
Output: 0
Explanation: Sum of all paths from root to leaf are already equal. Therefore, no operations are required.
Approach: Implement the idea below to solve the problem:
The problem can be solved using DP on Trees. DP[i] will store the minimum cost for balancing subtree of ith node (balancing subtree means path sum from node V to all leaf nodes is same)
Let’s say a node v has arr[v] = 5 and v has three child nodes u1, u2 and u3 with arr[u1] = 2, arr[u2] = 3 and arr[u3] = 5
- path sum from root v to u1 is arr[v] + arr[u1] = 5 + 2 = 7
- path sum from root v to u2 is arr[v] + arr[u2] = 5 + 3 = 8
- path sum from root v to u3 is arr[v] + arr[u3] = 5 + 5 = 10
The intuition to solve this problem is to find the leaf node which is at maximum distance in this case it is u3 as distance arr[u3] = 5 and make all the other nodes equal to this node.
Increment node u1 and u2 to make it equal to 5. Currently arr[u1] = 2 and arr[u2] = 3, so perform increment operations 3 times on u1 to make arr[u1] = 5 and 2 times to make arr[u2] = 5. Now path sums are equal from v to u1, v to u2 and v to u3.
We will solve this problem for every subtree starting from leaf using Dynamic Programming and merging the answers of children with their parent.
Step-by-step algorithm:
- Initialize DP[N] array with all values initially zero.
- Create dfs() function that takes current node V and its parent P as input.
- In dfs() function initialize maxi variable with value INT_MIN.
- Iterate over all the child nodes of V and find maximum value arr[child] by updating maxi variable.
- Iterate over all the child nodes again, this time perform operations to make all child’s have equal path sum. It is done by DP transition: DP[V] = (DP[V] + DP[child] + maxi – arr[child])
- Finally, as we move up in bottom-up manner from leaf to upper nodes distances increases which will be tracked by adding maxi value of child to arr[V].
- Return DP[0] as the final answer.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // dfs function void dfs( int arr[], vector< int >& dp, int v, int parent, vector<vector< int > >& adj) { // variable to find child with maximum value int maxi = INT_MIN; // iterating over adjacent elements to find maximum // node sum for ( auto & u : adj[v]) { // if u is not parent call dfs for u if (u != parent) { // call dfs function dfs(arr, dp, u, v, adj); // updated maximum maxi = max(maxi, arr[u]); } } // iterating for performing operations to // make child nodes equal for ( auto & u : adj[v]) { // if u is not parent call dfs for u if (u != parent) { // transition for dp dp[v] += dp[u] + maxi - arr[u]; } } // going from child u to parent v path will increase in // bottom up arr[v] = arr[v] + maxi; } // Function to Minimize Number of operations // to make path sum from root to any leaf equal int minimumCost( int N, int edges[][2], int arr[]) { // DP array initalized with 0 vector< int > dp(N, 0); // Declaring adjacency List vector<vector< int > > adj(N + 1); // fill adjacency list for ( 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]); } // making dfs call from root 0 dfs(arr, dp, 0, -1, adj); // Returing answer return dp[0]; } // Driver Code int32_t main() { // Input int N = 7; int edges[][2] = { { 0, 1 }, { 0, 2 }, { 1, 3 }, { 1, 4 }, { 2, 5 }, { 2, 6 } }; int arr[] = { 1, 5, 2, 2, 3, 3, 1 }; // Function Call cout << minimumCost(N, edges, arr) << endl; return 0; } |
Java
import java.util.*; class Main { // dfs function static void dfs( int [] arr, List<Integer> dp, int v, int parent, List<List<Integer> > adj) { // variable to find child with maximum value int maxi = Integer.MIN_VALUE; // iterating over adjacent elements to find maximum // node sum for ( int u : adj.get(v)) { // if u is not parent call dfs for u if (u != parent) { // call dfs function dfs(arr, dp, u, v, adj); // updated maximum maxi = Math.max(maxi, arr[u]); } } // iterating for performing operations to // make child nodes equal for ( int u : adj.get(v)) { // if u is not parent call dfs for u if (u != parent) { // transition for dp dp.set(v, dp.get(v) + dp.get(u) + maxi - arr[u]); } } // going from child u to parent v path will increase // in bottom up arr[v] = arr[v] + maxi; } // Function to Minimize Number of operations // to make path sum from root to any leaf equal static int minimumCost( int N, int [][] edges, int [] arr) { // DP array initialized with 0 List<Integer> dp = new ArrayList<>(Collections.nCopies(N, 0 )); // Declaring adjacency List List<List<Integer> > adj = new ArrayList<>(N + 1 ); // initialize adjacency list for ( int i = 0 ; i <= N; i++) { adj.add( new ArrayList<>()); } // fill adjacency list for ( int i = 0 ; i < N - 1 ; i++) { adj.get(edges[i][ 0 ]).add(edges[i][ 1 ]); adj.get(edges[i][ 1 ]).add(edges[i][ 0 ]); } // making dfs call from root 0 dfs(arr, dp, 0 , - 1 , adj); // Returning answer return dp.get( 0 ); } // Driver Code public static void main(String[] args) { // Input int N = 7 ; int [][] edges = { { 0 , 1 }, { 0 , 2 }, { 1 , 3 }, { 1 , 4 }, { 2 , 5 }, { 2 , 6 } }; int [] arr = { 1 , 5 , 2 , 2 , 3 , 3 , 1 }; // Function Call System.out.println(minimumCost(N, edges, arr)); } } |
Python3
def dfs(arr, dp, v, parent, adj): maxi = float ( '-inf' ) for u in adj[v]: if u ! = parent: dfs(arr, dp, u, v, adj) maxi = max (maxi, arr[u]) for u in adj[v]: if u ! = parent: dp[v] + = dp[u] + maxi - arr[u] # Check if any child node exists if maxi ! = float ( '-inf' ): arr[v] = arr[v] + maxi def minimum_cost(N, edges, arr): dp = [ 0 ] * N adj = [[] for _ in range (N + 1 )] for edge in edges: adj[edge[ 0 ]].append(edge[ 1 ]) adj[edge[ 1 ]].append(edge[ 0 ]) dfs(arr, dp, 0 , - 1 , adj) return dp[ 0 ] # Driver Code if __name__ = = "__main__" : N = 7 edges = [[ 0 , 1 ], [ 0 , 2 ], [ 1 , 3 ], [ 1 , 4 ], [ 2 , 5 ], [ 2 , 6 ]] arr = [ 1 , 5 , 2 , 2 , 3 , 3 , 1 ] print (minimum_cost(N, edges, arr)) # This code is contributed by akshitaguprzj3 |
C#
using System; using System.Collections.Generic; class Program { // dfs function static void DFS( int [] arr, List< int > dp, int v, int parent, List<List< int >> adj) { // variable to find child with maximum value int maxi = int .MinValue; // iterating over adjacent elements to find maximum // node sum foreach ( var u in adj[v]) { // if u is not parent call DFS for u if (u != parent) { // call DFS function DFS(arr, dp, u, v, adj); // updated maximum maxi = Math.Max(maxi, arr[u]); } } // iterating for performing operations to // make child nodes equal foreach ( var u in adj[v]) { // if u is not parent call DFS for u if (u != parent) { // transition for dp dp[v] += dp[u] + maxi - arr[u]; } } // going from child u to parent v path will increase in // bottom up arr[v] = arr[v] + maxi; } // Function to Minimize Number of operations // to make path sum from root to any leaf equal static int MinimumCost( int N, int [,] edges, int [] arr) { // DP array initialized with 0 List< int > dp = new List< int >( new int [N]); // Declaring adjacency List List<List< int >> adj = new List<List< int >>(N + 1); // fill adjacency list for ( int i = 0; i <= N; i++) { adj.Add( new List< int >()); } for ( int i = 0; i < N - 1; i++) { adj[edges[i, 0]].Add(edges[i, 1]); adj[edges[i, 1]].Add(edges[i, 0]); } // making DFS call from root 0 DFS(arr, dp, 0, -1, adj); // Returning answer return dp[0]; } // Driver Code static void Main() { // Input int N = 7; int [,] edges = { { 0, 1 }, { 0, 2 }, { 1, 3 }, { 1, 4 }, { 2, 5 }, { 2, 6 } }; int [] arr = { 1, 5, 2, 2, 3, 3, 1 }; // Function Call Console.WriteLine(MinimumCost(N, edges, arr)); } } |
Javascript
// JavaScript code to implement the approach // dfs function function dfs(arr, dp, v, parent, adj) { // variable to find child with maximum value let maxi = -1e9; // iterating over adjacent elements to find maximum // node sum for (let u of adj[v]) { // if u is not parent call dfs for u if (u !== parent) { // call dfs function dfs(arr, dp, u, v, adj); // updated maximum maxi = Math.max(maxi, arr[u]); } } // iterating for performing operations to // make child nodes equal for (let u of adj[v]) { // if u is not parent call dfs for u if (u !== parent) { // transition for dp dp[v] += dp[u] + maxi - arr[u]; } } // going from child u to parent v path will increase in // bottom up arr[v] = arr[v] + maxi; } // Function to Minimize Number of operations // to make path sum from root to any leaf equal function minimumCost(N, edges, arr) { // DP array initialized with 0 let dp = new Array(N).fill(0); // Declaring adjacency List let adj = new Array(N + 1).fill(0).map(() => []); // fill adjacency list for (let i = 0; i < N - 1; i++) { adj[edges[i][0]].push(edges[i][1]); adj[edges[i][1]].push(edges[i][0]); } // making dfs call from root 0 dfs(arr, dp, 0, -1, adj); // Returning answer return dp[0]; } // Driver Code function main() { // Input let N = 7; let edges = [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]; let arr = [1, 5, 2, 2, 3, 3, 1]; // Function Call console.log(minimumCost(N, edges, arr)); } // Run the driver code main(); |
6
Time Complexity: O(N), where N is the number of nodes in the tree.
Auxiliary Space: O(N)