Dado un árbol de N-arrays de N Nodes, con raíz en 1 , con bordes en la forma {u, v} , y una array de valores[] que consta de N enteros. Cada vértice i tiene un valor entero indicado por valores[i] . La tarea es encontrar la suma de subárbol más grande posible para cada vértice i agregando su valor a un subconjunto no vacío de sus vértices secundarios.
Ejemplos:
Entrada: Bordes[][] = {{1, 2}, {1, 3}, {3, 4}}, valores[] = {1, -1, 0, 1}
Salida: 2 -1 1 1
Explicación :
A continuación se muestra el árbol dado:1
/ \
2 3
\
4
Se pueden elegir los siguientes subconjuntos para cada vértice:
Vértice 1: Se puede elegir el subconjunto de vértices {1, 3, 4} con valores {1, 0, 1}. Por lo tanto, suma = 1 + 0 + 1 = 2.
Vértice 2: Se puede elegir el subconjunto de vértices {2} con valores {-1}. Por lo tanto, suma = -1.
Vértice 3: el subconjunto de vértices {3, 4} se puede elegir con valores {0, 1}. Por lo tanto, suma = 0 + 1 = 1.
Vértice 4: Se puede elegir el subconjunto de vértices {4} con valores {1}. Por lo tanto, suma = 1.Entrada: Bordes[][] = {{1, 2}, {1, 3}, {2, 4}, {2, 5}}, valores[] = {1, -1, -2, 1, 3 }
Salida: 5 4 -2 1 3
Explicación:
A continuación se muestra el árbol dado:1
/ \
2 3
/ \
4 5
Se pueden elegir los siguientes subconjuntos para cada vértice:
Vértice 1: Se puede elegir el subconjunto de vértices {1, 4, 5} con valores {1, 1, 3}. Por lo tanto, suma = 1 + 1 + 3 = 5.
Vértice 2: Se puede elegir el subconjunto de vértices {4, 5} con valores {1, 3}. Por lo tanto, suma = 1 + 3 = 4.
Vértice 3: Se puede elegir el subconjunto de vértices {3} con valores {-2}. Por lo tanto, suma = -2.
Vértice 4: el subconjunto de vértices {4} se puede elegir con valores {1}. Por lo tanto, suma = 1.
Vértice 5: El subconjunto de vértices {5} se puede elegir con valores {3}. Por lo tanto, suma = 3.
Enfoque ingenuo: el enfoque más simple es atravesar el subárbol de cada vértice i de 1 a N y realizar DFS Traversal en él. Para cada vértice i , elija el subconjunto de sus vértices secundarios que tengan valores no negativos. Si el subconjunto de vértices elegidos está vacío, busque e imprima el Node que tenga el valor mínimo de modo que sea el Node secundario del vértice i . De lo contrario, imprima la suma de los valores de los Nodes presentes en el subconjunto.
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: la idea es utilizar el enfoque de programación dinámica y transversal DFS . Siga los pasos a continuación para resolver el problema:
- Inicialice una array ans[] de tamaño N para almacenar la suma máxima del subárbol para cada vértice.
- Realice DFS Traversal para cada vértice y para cada vértice inicialice v , ans[v] con un valor negativo grande.
- Si el vértice v es un vértice de hoja, entonces la respuesta para ese vértice sería valores[v] . Por lo tanto, asigne ans[v] = valores[v] .
- De lo contrario, recorre los vértices adyacentes al vértice v y para cada vértice adyacente u , actualiza ans[v] como ans[v] = max(ans[u] + valores[v], valores[v], ans[u]) .
- Después de los pasos anteriores, imprima los valores almacenados en la array ans[] como la respuesta para cada vértice.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
#define V 3
#define M 2
// Function to perform the DFS
// Traversal on the given Tree
void dfs(int v, int p,
vector<int> adj[],
int ans[], int vals[])
{
// To check if v is leaf vertex
bool isLeaf = 1;
// Initialize answer for vertex v
ans[v] = INT_MIN;
// Traverse adjacency list of v
for(int u : adj[v])
{
if (u == p)
continue;
isLeaf = 0;
dfs(u, v, adj, ans, vals);
// Update maximum subtree sum
ans[v] = max(ans[u] + vals[v],
max(ans[u], vals[u]));
}
// If v is leaf
if (isLeaf)
{
ans[v] = vals[v];
}
}
// Function to calculate maximum
// subtree sum for each vertex
void printAnswer(int n,
int edges[V][M],
int values[])
{
// Stores the adjacency list
vector<int> adj[n];
// Add Edges to the list
for(int i = 0; i < n - 1; i++)
{
int u = edges[i][0] - 1;
int v = edges[i][1] - 1;
adj[u].push_back(v);
adj[v].push_back(u);
}
// Stores largest subtree
// sum for each vertex
int ans[n] ;
// Calculate answer
dfs(0, -1, adj, ans, values);
// Print the result
for(auto x : ans)
{
cout << x << " ";
}
}
// Driver Code
int main()
{
// Given nodes
int N = 4;
// Give N edges
int edges[V][M] = { { 1, 2 },
{ 1, 3 },
{ 3, 4 } };
// Given values
int values[] = { 1, -1, 0, 1 };
// Function Call
printAnswer(N, edges, values);
}
// This code is contributed by Princi Singh
Java
// Java program for the above approach
import java.io.*;
import java.util.ArrayList;
@SuppressWarnings("unchecked")
class GFG {
// Function to perform the DFS
// Traversal on the given Tree
static void dfs(int v, int p,
ArrayList<Integer> adj[],
int ans[], int vals[])
{
// To check if v is leaf vertex
boolean isLeaf = true;
// Initialize answer for vertex v
ans[v] = Integer.MIN_VALUE;
// Traverse adjacency list of v
for (int u : adj[v]) {
if (u == p)
continue;
isLeaf = false;
dfs(u, v, adj, ans, vals);
// Update maximum subtree sum
ans[v] = Math.max(
ans[u] + vals[v],
Math.max(ans[u],
vals[u]));
}
// If v is leaf
if (isLeaf) {
ans[v] = vals[v];
}
}
// Function to calculate maximum
// subtree sum for each vertex
static void printAnswer(
int n, int edges[][], int values[])
{
// Stores the adjacency list
ArrayList<Integer> adj[]
= new ArrayList[n];
for (int i = 0; i < n; i++)
adj[i] = new ArrayList<>();
// Add Edges to the list
for (int i = 0; i < n - 1; i++) {
int u = edges[i][0] - 1;
int v = edges[i][1] - 1;
adj[u].add(v);
adj[v].add(u);
}
// Stores largest subtree
// sum for each vertex
int ans[] = new int[n];
// Calculate answer
dfs(0, -1, adj, ans, values);
// Print the result
for (int x : ans) {
System.out.print(x + " ");
}
}
// Driver Code
public static void main(String[] args)
{
// Given nodes
int N = 4;
// Give N edges
int edges[][]
= new int[][] { { 1, 2 },
{ 1, 3 },
{ 3, 4 } };
// Given values
int values[] = { 1, -1, 0, 1 };
// Function Call
printAnswer(N, edges, values);
}
}
Python3
# Python3 program for the above approach V = 3 M = 2 # Function to perform the DFS # Traversal on the given Tree def dfs(v, p): # To check if v is leaf vertex isLeaf = 1 # Initialize answer for vertex v ans[v] = -10**9 # Traverse adjacency list of v for u in adj[v]: if (u == p): continue isLeaf = 0 dfs(u, v) # Update maximum subtree sum ans[v] = max(ans[u] + vals[v],max(ans[u], vals[u])) # If v is leaf if (isLeaf): ans[v] = vals[v] # Function to calculate maximum # subtree sum for each vertex def printAnswer(n, edges, vals): # Stores the adjacency list # vector<int> adj[n]; # Add Edges to the list for i in range(n - 1): u = edges[i][0] - 1 v = edges[i][1] - 1 adj[u].append(v) adj[v].append(u) # Calculate answer dfs(0, -1) # Print the result for x in ans: print(x, end=" ") # Driver Code if __name__ == '__main__': # Given nodes N = 4 # Give N edges edges=[ [ 1, 2], [ 1, 3], [ 3, 4] ] adj=[[] for i in range(N)] ans=[0 for i in range(N)] # Given values vals=[1, -1, 0, 1] # Function Call printAnswer(N, edges, vals) # This code is contributed by mohit kumar 29
C#
// C# program for the
// above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to perform the DFS
// Traversal on the given Tree
static void dfs(int v, int p,
List<int> []adj,
int []ans, int []vals)
{
// To check if v is leaf
// vertex
bool isLeaf = true;
// Initialize answer for
// vertex v
ans[v] = int.MinValue;
// Traverse adjacency list
// of v
foreach (int u in adj[v])
{
if (u == p)
continue;
isLeaf = false;
dfs(u, v, adj, ans, vals);
// Update maximum subtree
// sum
ans[v] = Math.Max(ans[u] +
vals[v],
Math.Max(ans[u],
vals[u]));
}
// If v is leaf
if (isLeaf)
{
ans[v] = vals[v];
}
}
// Function to calculate maximum
// subtree sum for each vertex
static void printAnswer(int n,
int [,]edges,
int []values)
{
// Stores the adjacency list
List<int> []adj =
new List<int>[n];
for (int i = 0; i < n; i++)
adj[i] = new List<int>();
// Add Edges to the list
for (int i = 0;
i < n - 1; i++)
{
int u = edges[i, 0] - 1;
int v = edges[i, 1] - 1;
adj[u].Add(v);
adj[v].Add(u);
}
// Stores largest subtree
// sum for each vertex
int []ans = new int[n];
// Calculate answer
dfs(0, -1, adj,
ans, values);
// Print the result
foreach (int x in ans)
{
Console.Write(x + " ");
}
}
// Driver Code
public static void Main(String[] args)
{
// Given nodes
int N = 4;
// Give N edges
int [,]edges = new int[,] {{1, 2},
{1, 3},
{3, 4}};
// Given values
int []values = {1, -1, 0, 1};
// Function Call
printAnswer(N, edges, values);
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// JavaScript program for the above approach
// Function to perform the DFS
// Traversal on the given Tree
function dfs(v, p, adj, ans, vals)
{
// To check if v is leaf
// vertex
let isLeaf = true;
// Initialize answer for
// vertex v
ans[v] = Number.MIN_VALUE;
// Traverse adjacency list
// of v
for(let u = 0; u < adj[v].length; u++)
{
if (adj[v][u] == p)
continue;
isLeaf = false;
dfs(adj[v][u], v, adj, ans, vals);
// Update maximum subtree
// sum
ans[v] = Math.max(ans[adj[v][u]] +
vals[v],
Math.max(ans[adj[v][u]],
vals[adj[v][u]]));
}
// If v is leaf
if (isLeaf)
{
ans[v] = vals[v];
}
}
// Function to calculate maximum
// subtree sum for each vertex
function printAnswer(n, edges, values)
{
// Stores the adjacency list
let adj = new Array(n);
for (let i = 0; i < n; i++)
adj[i] = [];
// Add Edges to the list
for (let i = 0; i < n - 1; i++)
{
let u = edges[i][0] - 1;
let v = edges[i][1] - 1;
adj[u].push(v);
adj[v].push(u);
}
// Stores largest subtree
// sum for each vertex
let ans = new Array(n);
// Calculate answer
dfs(0, -1, adj, ans, values);
// Print the result
for(let x = 0; x < ans.length; x++)
{
document.write(ans[x] + " ");
}
}
// Given nodes
let N = 4;
// Give N edges
let edges = [[1, 2], [1, 3], [3, 4]];
// Given values
let values = [1, -1, 0, 1];
// Function Call
printAnswer(N, edges, values);
</script>
2 -1 1 1
Complejidad temporal: O(N)
Espacio auxiliar: O(N)