Given an N-Ary tree containing N nodes and an array weight [ ] that denotes the weight of the nodes which can be positive or negative, the task for every node is to print the maximum sum possible by a sequence of nodes including the current node.
Examples:
Input: N = 7 weight[] = [-8, 9, 7, -4, 5, -10, -6] N-Ary tree: -8 / \ 9 7 / \ / -4 5 -10 / -6 Output: 13 14 13 10 14 3 4 Explanations: Node -8: [-8 + 9 + 7 + 5] = 13 Node 9: [9 + 5] = 14 Node 3: [7 + (-8) + 9 + 5] = 13 Node 4: [-4 + 9 + 5] = 10 Node: [5 + 9] = 14 Node 6: [-10 + 7 + (-8) + 9 + 5] = 3 Node 7: [-6 + (-4) + 9 + 5] = 4 Input: N = 6 weight[] = [2, -7, -5, 8, 4, -10] N-Ary tree: 2 / \ -7 -5 / \ \ 8 4 -10 Output: 7 7 2 8 7 -8
Approach: This problem can be solved using Dp on Trees technique by applying two DFS.
- Apply the first DFS to store the maximum sum possible for every node by including them in a sequence with their respective successors. Store the maximum possible sum in dp1[]. array.
- Maximum possible value for each node in the first DFS can be obtained by:
dp1[node] += maximum(0, dp1[child1], dp1[child2], …)
Â
- Perform the second Dfs to update the maximum sum for each node in dp1[] by including them in a sequence with their ancestors also. The maximum values stored in dp2[] for every node are the required answers.
- Maximum possible value for each node in the second DFS can be obtained by:
dp2[node] = dp1[node] + maximum(0, maxSumAncestors)
Best answer can be obtained by including or excluding the maximum sum possible for its ancestors
where maxSumAncestors = dp2[parent] – maximum(0, dp1[node]), i.e. including or excluding contribution of the maximum sum of the current node stored in dp1[]
Â
Refer to the pictorial explanation for better understanding:
Below is the implementation of the above approach:
C++
// C++ program to calculate the maximum // sum possible for every node by including // it in a segment of the N-Ary Tree #include <bits/stdc++.h> using namespace std; Â
// Stores the maximum // sum possible for every node // by including them in a segment // with their successors int dp1[100005]; Â
// Stores the maximum // sum possible for every node // by including them in a segment // with their ancestors int dp2[100005]; Â
// Store the maximum sum // for every node by // including it in a // segment with its successors void dfs1( int u, int par, Â Â Â Â Â Â Â Â Â Â vector< int > g[], Â Â Â Â Â Â Â Â Â Â int weight[]) { Â
    dp1[u] = weight[u];     for ( auto c: g[u]) {         if (c != par) {             dfs1(c, u, g, weight);             dp1[u] += max(0, dp1);         }     } } Â
// Update the maximum sums // for each node by including // them in a sequence with // their ancestors void dfs2( int u, int par,           vector< int > g[],           int weight[]) {     // Condition to check,     // if current node is not root     if (par != 0) {         int maxSumAncestors = dp2[par]                               - max(0, dp1[u]);         dp2[u] = dp1[u] + max(0,                               maxSumAncestors);     }     for ( auto c: g[u]) {         if (c != par) {             dfs2(c, u, g, weight);         }     } } Â
// Add edges void addEdge( int u, int v, vector< int > g[]) { Â Â Â Â g[u].push_back(v); Â Â Â Â g[v].push_back(u); } Â
// Function to find the maximum // answer for each node void maxSumSegments(vector< int > g[], Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â int weight[], Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â int n) { Â
    // Compute the maximum sums     // with successors     dfs1(1, 0, g, weight); Â
    // Store the computed maximums     for ( int i = 1; i <= n; i++) {         dp2[i] = dp1[i];     } Â
    // Update the maximum sums     // by including their     // ancestors     dfs2(1, 0, g, weight); } Â
// Print the desired result void printAns( int n) { Â Â Â Â for ( int i = 1; i <= n; i++) { Â Â Â Â Â Â Â Â cout << dp2[i] << " " ; Â Â Â Â } } Â
// Driver Program int main() { Â
    // Number of nodes     int n = 6;     int u, v; Â
    // graph     vector< int > g[100005]; Â
    // Add edges     addEdge(1, 2, g);     addEdge(1, 3, g);     addEdge(2, 4, g);     addEdge(2, 5, g);     addEdge(3, 6, g);     addEdge(4, 7, g); Â
    // Weight of each node     int weight[n + 1];     weight[1] = -8;     weight[2] = 9;     weight[3] = 7;     weight[4] = -4;     weight[5] = 5;     weight[6] = -10;     weight[7] = -6; Â
    // Compute the max sum     // of segments for each     // node     maxSumSegments(g, weight, n); Â
    // Print the answer     // for every node     printAns(n); Â
    return 0; } |
Java
// Java program to calculate the maximum // sum possible for every node by including // it in a segment of the N-Ary Tree import java.util.*; public class Main {     // Stores the maximum     // sum possible for every node     // by including them in a segment     // with their successors     static int [] dp1 = new int [ 100005 ];            // Stores the maximum     // sum possible for every node     // by including them in a segment     // with their ancestors     static int [] dp2 = new int [ 100005 ];           // Store the maximum sum for every     // node by including it in a     // segment with its successors     static void dfs1( int u, int par,                      Vector<Vector<Integer>> g,                      int [] weight)     {         dp1[u] = weight[u];            for ( int c = 0 ; c < g.get(u).size(); c++)         {             if (g.get(u).get(c) != par)             {                 dfs1(g.get(u).get(c), u, g, weight);                 dp1[u] += Math.max( 0 , dp1[g.get(u).get(c)]);             }         }     }        // Update the maximum sums     // for each node by including     // them in a sequence with     // their ancestors     static void dfs2( int u, int par,                      Vector<Vector<Integer>> g,                      int [] weight)     {                // Condition to check,         // if current node is not root         if (par != 0 )         {             int maxSumAncestors = dp2[par] - Math.max( 0 , dp1[u]);             dp2[u] = dp1[u] + Math.max( 0 , maxSumAncestors);         }            for ( int c = 0 ; c < g.get(u).size(); c++)         {             if (g.get(u).get(c) != par)             {                 dfs2(g.get(u).get(c), u, g, weight);             }         }     }        // Add edges     static void addEdge( int u, int v, Vector<Vector<Integer>> g)     {         g.get(u).add(v);         g.get(v).add(u);     }        // Function to find the maximum     // answer for each node     static void maxSumSegments(Vector<Vector<Integer>> g, int [] weight, int n)     {                 // Compute the maximum sums         // with successors         dfs1( 1 , 0 , g, weight);            // Store the computed maximums         for ( int i = 1 ; i < n + 1 ; i++)             dp2[i] = dp1[i];            // Update the maximum sums         // by including their         // ancestors         dfs2( 1 , 0 , g, weight);     }        // Print the desired result     static void printAns( int n)     {         for ( int i = 1 ; i < n; i++)             System.out.print(dp2[i] + " " );     }          public static void main(String[] args)     {                // Number of nodes         int n = 7 ;                  // Graph         Vector<Vector<Integer>> g = new Vector<Vector<Integer>>();         for ( int i = 0 ; i < 100005 ; i++)         {             g.add( new Vector<Integer>());         }                  // Add edges         addEdge( 1 , 2 , g);         addEdge( 1 , 3 , g);         addEdge( 2 , 4 , g);         addEdge( 2 , 5 , g);         addEdge( 3 , 6 , g);         addEdge( 4 , 7 , g);                  // Weight of each node         int [] weight = new int [n + 1 ];         weight[ 1 ] = - 8 ;         weight[ 2 ] = 9 ;         weight[ 3 ] = 7 ;         weight[ 4 ] = - 4 ;         weight[ 5 ] = 5 ;         weight[ 6 ] = - 10 ;         weight[ 7 ] = - 6 ;                  // Compute the max sum         // of segments for each         // node         maxSumSegments(g, weight, n);                  // Print the answer         // for every node         printAns(n);     } } Â
// This code is contributed by divyeshrabadiya07. |
Python3
# Python3 program to calculate the maximum # sum possible for every node by including # it in a segment of the N-Ary Tree   # Stores the maximum # sum possible for every node # by including them in a segment # with their successors dp1 = [ 0 for i in range ( 100005 )]   # Stores the maximum sum possible # for every node by including them # in a segment with their ancestors dp2 = [ 0 for i in range ( 100005 )]   # Store the maximum sum for every # node by including it in a # segment with its successors def dfs1(u, par, g, weight):       dp1[u] = weight[u]          for c in g[u]:         if (c ! = par):             dfs1(c, u, g, weight)             dp1[u] + = max ( 0 , dp1)          # Update the maximum sums # for each node by including # them in a sequence with # their ancestors def dfs2(u, par, g, weight): Â
    # Condition to check,     # if current node is not root     if (par ! = 0 ):         maxSumAncestors = dp2[par] - max ( 0 , dp1[u])         dp2[u] = dp1[u] + max ( 0 , maxSumAncestors)          for c in g[u]:         if (c ! = par):             dfs2(c, u, g, weight)              # Add edges def addEdge(u, v, g): Â
    g[u].append(v)     g[v].append(u) Â
# Function to find the maximum # answer for each node def maxSumSegments(g, weight, n):       # Compute the maximum sums     # with successors     dfs1( 1 , 0 , g, weight)       # Store the computed maximums     for i in range ( 1 , n + 1 ):         dp2[i] = dp1[i]          # Update the maximum sums     # by including their     # ancestors     dfs2( 1 , 0 , g, weight) Â
# Print the desired result def printAns(n): Â
    for i in range ( 1 , n):         print (dp2[i], end = ' ' )          # Driver code if __name__ = = '__main__' :          # Number of nodes     n = 7     u = 0     v = 0       # Graph     g = [[] for i in range ( 100005 )]       # Add edges     addEdge( 1 , 2 , g)     addEdge( 1 , 3 , g)     addEdge( 2 , 4 , g)     addEdge( 2 , 5 , g)     addEdge( 3 , 6 , g)     addEdge( 4 , 7 , g)       # Weight of each node     weight = [ 0 for i in range (n + 1 )]     weight[ 1 ] = - 8     weight[ 2 ] = 9     weight[ 3 ] = 7     weight[ 4 ] = - 4     weight[ 5 ] = 5     weight[ 6 ] = - 10     weight[ 7 ] = - 6       # Compute the max sum     # of segments for each     # node     maxSumSegments(g, weight, n)       # Print the answer     # for every node     printAns(n) Â
# This code is contributed by pratham76 |
C#
// C# program to calculate the maximum // sum possible for every node by including // it in a segment of the N-Ary Tree using System; using System.Collections.Generic; class GFG {          // Stores the maximum     // sum possible for every node     // by including them in a segment     // with their successors     static int [] dp1 = new int [100005];           // Stores the maximum     // sum possible for every node     // by including them in a segment     // with their ancestors     static int [] dp2 = new int [100005];          // Store the maximum sum for every     // node by including it in a     // segment with its successors     static void dfs1( int u, int par, List<List< int >> g, int [] weight)     {         dp1[u] = weight[u];           for ( int c = 0; c < g[u].Count; c++)         {             if (g[u] != par)             {                 dfs1(g[u], u, g, weight);                 dp1[u] += Math.Max(0, dp1[g[u]]);             }         }     }       // Update the maximum sums     // for each node by including     // them in a sequence with     // their ancestors     static void dfs2( int u, int par, List<List< int >> g, int [] weight)     {         // Condition to check,         // if current node is not root         if (par != 0)         {             int maxSumAncestors = dp2[par] - Math.Max(0, dp1[u]);             dp2[u] = dp1[u] + Math.Max(0, maxSumAncestors);         }           for ( int c = 0; c < g[u].Count; c++)         {             if (g[u] != par)             {                 dfs2(g[u], u, g, weight);             }         }     }       // Add edges     static void addEdge( int u, int v, List<List< int >> g)     {         g[u].Add(v);         g[v].Add(u);     }       // Function to find the maximum     // answer for each node     static void maxSumSegments(List<List< int >> g, int [] weight, int n)     {                // Compute the maximum sums         // with successors         dfs1(1, 0, g, weight);           // Store the computed maximums         for ( int i = 1; i < n + 1; i++)             dp2[i] = dp1[i];           // Update the maximum sums         // by including their         // ancestors         dfs2(1, 0, g, weight);     }       // Print the desired result     static void printAns( int n)     {         for ( int i = 1; i < n; i++)             Console.Write(dp2[i] + " " );     } Â
  static void Main() {     // Number of nodes     int n = 7;         // Graph     List<List< int >> g = new List<List< int >>();     for ( int i = 0; i < 100005; i++)     {         g.Add( new List< int >());     }         // Add edges     addEdge(1, 2, g);     addEdge(1, 3, g);     addEdge(2, 4, g);     addEdge(2, 5, g);     addEdge(3, 6, g);     addEdge(4, 7, g);         // Weight of each node     int [] weight = new int [n + 1];     weight[1] = -8;     weight[2] = 9;     weight[3] = 7;     weight[4] = -4;     weight[5] = 5;     weight[6] = -10;     weight[7] = -6;         // Compute the max sum     // of segments for each     // node     maxSumSegments(g, weight, n);         // Print the answer     // for every node     printAns(n);   } } Â
// This code is contributed by divyesh072019. |
Javascript
<script>     // Javascript program to calculate the maximum     // sum possible for every node by including     // it in a segment of the N-Ary Tree          // Stores the maximum     // sum possible for every node     // by including them in a segment     // with their successors     let dp1 = []; Â
    // Stores the maximum     // sum possible for every node     // by including them in a segment     // with their ancestors     let dp2 = [];          for (let i = 0; i < 100005; i++)     {         dp1.push(0);         dp2.push(0);     }          // Store the maximum sum for every     // node by including it in a     // segment with its successors     function dfs1(u, par, g, weight)     {         dp1[u] = weight[u]; Â
        for (let c = 0; c < g[u].length; c++)         {             if (g[u] != par)             {                 dfs1(g[u], u, g, weight);                 dp1[u] += Math.max(0, dp1[g[u]]);             }         }     } Â
    // Update the maximum sums     // for each node by including     // them in a sequence with     // their ancestors     function dfs2(u, par, g, weight)     {         // Condition to check,         // if current node is not root         if (par != 0)         {             maxSumAncestors = dp2[par] - Math.max(0, dp1[u]);             dp2[u] = dp1[u] + Math.max(0, maxSumAncestors);         } Â
        for (let c = 0; c < g[u].length; c++)         {             if (g[u] != par)             {                 dfs2(g[u], u, g, weight);             }         }     } Â
    // Add edges     function addEdge(u, v, g)     {         g[u].push(v);         g[v].push(u);     } Â
    // Function to find the maximum     // answer for each node     function maxSumSegments(g, weight, n)     {         // Compute the maximum sums         // with successors         dfs1(1, 0, g, weight); Â
        // Store the computed maximums         for (let i = 1; i < n + 1; i++)             dp2[i] = dp1[i]; Â
        // Update the maximum sums         // by including their         // ancestors         dfs2(1, 0, g, weight);     } Â
    // Print the desired result     function printAns(n)     {         for (let i = 1; i < n; i++)             document.write(dp2[i] + " " );     }          // Number of nodes     let n = 7, u = 0, v = 0;        // Graph     let g = [];     for (let i = 0; i < 100005; i++)     {         g.push([]);     }        // Add edges     addEdge(1, 2, g);     addEdge(1, 3, g);     addEdge(2, 4, g);     addEdge(2, 5, g);     addEdge(3, 6, g);     addEdge(4, 7, g);        // Weight of each node     let weight = new Array(n + 1);     weight.fill(0);     weight[1] = -8;     weight[2] = 9;     weight[3] = 7;     weight[4] = -4;     weight[5] = 5;     weight[6] = -10;     weight[7] = -6;        // Compute the max sum     // of segments for each     // node     maxSumSegments(g, weight, n);        // Print the answer     // for every node     printAns(n); Â
// This code is contributed by suresh07. </script> |
13 14 13 10 14 3
Â
Time complexity: O(n)Â
Auxiliary Space: O(n)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!