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)