Dado un árbol y los pesos de todos los Nodes, la tarea es encontrar la raíz del subárbol cuya suma ponderada es mínima.
Ejemplos:
Aporte:
Salida: 5
Peso del subárbol para el padre 1 = ((-1) + (5) + (-2) + (-1) + (3)) = 4
Peso del subárbol para el padre 2 = ((5) ) + (-1) + (3)) = 7
Peso del subárbol para el padre 3 = -1
Peso del subárbol para el padre 4 = 3
Peso del subárbol para el padre 5 = -2
El Node 5 da el mínimo suma ponderada del subárbol.
Enfoque: Realice dfs en el árbol y, para cada Node, calcule la suma ponderada del subárbol con raíz en el Node actual y luego encuentre el valor de suma mínimo para un Node.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; int ans = 0, mini = INT_MAX; vector<int> graph[100]; vector<int> weight(100); // Function to perform dfs and update the tree // such that every node's weight is the sum of // the weights of all the nodes in the sub-tree // of the current node including itself void dfs(int node, int parent) { for (int to : graph[node]) { if (to == parent) continue; dfs(to, node); // Calculating the weighted // sum of the subtree weight[node] += weight[to]; } } // Function to find the node // having minimum sub-tree sum void findMin(int n) { // For every node for (int i = 1; i <= n; i++) { // If current node's weight // is minimum so far if (mini > weight[i]) { mini = weight[i]; ans = i; } } } // Driver code int main() { int n = 5; // Weights of the node weight[1] = -1; weight[2] = 5; weight[3] = -1; weight[4] = 3; weight[5] = -2; // Edges of the tree graph[1].push_back(2); graph[2].push_back(3); graph[2].push_back(4); graph[1].push_back(5); dfs(1, 1); findMin(n); cout << ans; return 0; }
Java
// Java implementation of the approach import java.util.*; class GFG { static int ans = 0, mini = Integer.MAX_VALUE; @SuppressWarnings("unchecked") static Vector<Integer>[] graph = new Vector[100]; static Integer[] weight = new Integer[100]; // Function to perform dfs and update the tree // such that every node's weight is the sum of // the weights of all the nodes in the sub-tree // of the current node including itself static void dfs(int node, int parent) { for (int to : graph[node]) { if (to == parent) continue; dfs(to, node); // Calculating the weighted // sum of the subtree weight[node] += weight[to]; } } // Function to find the node // having minimum sub-tree sum x static void findMin(int n) { // For every node for (int i = 1; i <= n; i++) { // If current node's weight x // is minimum so far if (mini > weight[i]) { mini = weight[i]; ans = i; } } } // Driver code public static void main(String[] args) { int n = 5; for (int i = 0; i < 100; i++) graph[i] = new Vector<Integer>(); // Weights of the node weight[1] = -1; weight[2] = 5; weight[3] = -1; weight[4] = 3; weight[5] = -2; // Edges of the tree graph[1].add(2); graph[2].add(3); graph[2].add(4); graph[1].add(5); dfs(1, 1); findMin(n); System.out.print(ans); } } // This code is contributed by shubhamsingh10
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { static int ans = 0, mini = int.MaxValue; static List<int>[] graph = new List<int>[100]; static int[] weight = new int[100]; // Function to perform dfs and update the tree // such that every node's weight is the sum of // the weights of all the nodes in the sub-tree // of the current node including itself static void dfs(int node, int parent) { foreach (int to in graph[node]) { if (to == parent) continue; dfs(to, node); // Calculating the weighted // sum of the subtree weight[node] += weight[to]; } } // Function to find the node // having minimum sub-tree sum x static void findMin(int n) { // For every node for (int i = 1; i <= n; i++) { // If current node's weight x // is minimum so far if (mini > weight[i]) { mini = weight[i]; ans = i; } } } // Driver code public static void Main(String[] args) { int n = 5; for (int i = 0; i < 100; i++) graph[i] = new List<int>(); // Weights of the node weight[1] = -1; weight[2] = 5; weight[3] = -1; weight[4] = 3; weight[5] = -2; // Edges of the tree graph[1].Add(2); graph[2].Add(3); graph[2].Add(4); graph[1].Add(5); dfs(1, 1); findMin(n); Console.Write(ans); } } // This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach ans = 0 mini = 2**32 graph = [[] for i in range(100)] weight = [0]*100 # Function to perform dfs and update the tree # such that every node's weight is the sum of # the weights of all the nodes in the sub-tree # of the current node including itself def dfs(node, parent): global mini, graph, weight, ans for to in graph[node]: if (to == parent): continue dfs(to, node) # Calculating the weighted # sum of the subtree weight[node] += weight[to] # Function to find the node # having minimum sub-tree sum def findMin(n): global mini, graph, weight, ans # For every node for i in range(1, n + 1): # If current node's weight # is minimum so far if (mini > weight[i]): mini = weight[i] ans = i # Driver code n = 5 # Weights of the node weight[1] = -1 weight[2] = 5 weight[3] = -1 weight[4] = 3 weight[5] = -2 # Edges of the tree graph[1].append(2) graph[2].append(3) graph[2].append(4) graph[1].append(5) dfs(1, 1) findMin(n) print(ans) # This code is contributed by SHUBHAMSINGH10
Javascript
<script> // Javascript implementation of the approach let ans = 0; let mini = Number.MAX_VALUE; let graph = new Array(100); let weight = new Array(100); for(let i = 0; i < 100; i++) { graph[i] = []; weight[i] = 0; } // Function to perform dfs and update the tree // such that every node's weight is the sum of // the weights of all the nodes in the sub-tree // of the current node including itself function dfs(node, parent) { for(let to = 0; to < graph[node].length; to++) { if (graph[node][to] == parent) continue dfs(graph[node][to], node); // Calculating the weighted // sum of the subtree weight[node] += weight[graph[node][to]]; } } // Function to find the node // having minimum sub-tree sum function findMin(n) { // For every node for(let i = 1; i <= n; i++) { // If current node's weight // is minimum so far if (mini > weight[i]) { mini = weight[i]; ans = i; } } } // Driver code let n = 5; // Weights of the node weight[1] = -1; weight[2] = 5; weight[3] = -1; weight[4] = 3; weight[5] = -2; // Edges of the tree graph[1].push(2); graph[2].push(3); graph[2].push(4); graph[1].push(5); dfs(1, 1); findMin(n); document.write(ans); // This code is contributed by Dharanendra L V. </script>
5
Análisis de Complejidad:
- Complejidad temporal: O(N).
En dfs, cada Node del árbol se procesa una vez y, por lo tanto, la complejidad debida a dfs es O(N) si hay un total de N Nodes en el árbol. Por lo tanto, la complejidad del tiempo es O(N). - Espacio Auxiliar : O(n).
Pila recursiva.
Publicación traducida automáticamente
Artículo escrito por mohit kumar 29 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA