Maximum sum possible for every node by including it in a segment of N-Ary Tree
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 successorsint dp1[100005];// Stores the maximum// sum possible for every node// by including them in a segment// with their ancestorsint dp2[100005];// Store the maximum sum// for every node by// including it in a// segment with its successorsvoid 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 ancestorsvoid 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 edgesvoid 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 nodevoid 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 resultvoid printAns(int n){ for (int i = 1; i <= n; i++) { cout << dp2[i] << " "; }}// Driver Programint 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 Treeimport 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 successorsdp1 = [0 for i in range(100005)] # Stores the maximum sum possible# for every node by including them# in a segment with their ancestorsdp2 = [0 for i in range(100005)] # Store the maximum sum for every # node by including it in a# segment with its successorsdef 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 ancestorsdef 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 edgesdef addEdge(u, v, g): g[u].append(v) g[v].append(u)# Function to find the maximum# answer for each nodedef 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 resultdef printAns(n): for i in range(1, n): print(dp2[i], end = ' ') # Driver codeif __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 Treeusing 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> |
Output:
13 14 13 10 14 3
Time complexity: O(n)
Auxiliary Space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
