Dado un árbol N-Ario que contiene N Nodes y un peso de array [] que denota el peso de los Nodes que pueden ser positivos o negativos , la tarea para cada Node es imprimir la suma máxima posible por una secuencia de Nodes que incluye el Node actual .
Ejemplos:
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
Enfoque: este problema se puede resolver utilizando la técnica Dp on Trees aplicando dos DFS .
- Aplique el primer DFS para almacenar la máxima suma posible para cada Node incluyéndolos en una secuencia con sus respectivos sucesores . Almacene la suma máxima posible en dp1[]. formación.
- El valor máximo posible para cada Node en el primer DFS se puede obtener mediante:
dp1[Node] += máximo(0, dp1[hijo1], dp1[hijo2], …)
- Realice el segundo Dfs para actualizar la suma máxima de cada Node en dp1[] incluyéndolos en una secuencia con sus ancestros también. Los valores máximos almacenados en dp2[] para cada Node son las respuestas requeridas.
- El valor máximo posible para cada Node en el segundo DFS se puede obtener mediante:
dp2[Node] = dp1[Node] + maximo(0, maxSumAncestors) La
mejor respuesta se puede obtener incluyendo o excluyendo la suma máxima posible para sus ancestros
donde maxSumAncestors = dp2[padre] – maximo(0, dp1[Node]) , es decir, incluyendo o excluyendo la contribución de la suma máxima del Node actual almacenado en dp1[]
Consulte la explicación pictórica para una mejor comprensión:
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
13 14 13 10 14 3
Publicación traducida automáticamente
Artículo escrito por VikasVishwakarma1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA