Dado un árbol y los pesos de todos los Nodes, la tarea es encontrar la raíz del subárbol cuya suma ponderada XOR con el entero X dado es mínima.
Ejemplos:
Aporte:
X = 15
Salida: 5
Peso del subárbol para padre 1 = ((-1) + (5) + (-2) + (-1) + (3)) XOR 15 = 4 XOR 15 = 11
Peso del sub -árbol para padre 2 = ((5) + (-1) + (3)) XOR 15 = 7 XOR 15 = 8
Peso del subárbol para padre 3 = -1 XOR 15 = -16
Peso del subárbol para padre 4 = 3 XOR 15 = 12
Peso del subárbol para el padre 5 = -2 XOR 15 = -15
El Node 3 proporciona la suma ponderada mínima del subárbol XOR X.
Enfoque: Realice dfs en el árbol y, para cada Node, calcule la suma ponderada del subárbol enraizada en el Node actual, luego encuentre el valor mínimo (suma XOR X) 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 XOR x void findMinX(int n, int x) { // For every node for (int i = 1; i <= n; i++) { // If current node's weight XOR x // is minimum so far if (mini > (weight[i] ^ x)) { mini = (weight[i] ^ x); ans = i; } } } // Driver code int main() { int x = 15; 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); findMinX(n, x); cout << ans; return 0; }
Java
// Java implementation of the approach import java.util.*; class GFG { static int ans = 0, mini = Integer.MAX_VALUE; 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 XOR x static void findMinX(int n, int x) { // For every node for (int i = 1; i <= n; i++) { // If current node's weight XOR x // is minimum so far if (mini > (weight[i] ^ x)) { mini = (weight[i] ^ x); ans = i; } } } // Driver code public static void main(String[] args) { int x = 15; 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); findMinX(n, x); System.out.print(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 ans, mini, graph, weight, x 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 XOR x def findMinX(n, x): global ans, mini,graph,weight # For every node for i in range(1, n + 1): # If current node's weight XOR x # is minimum so far if (mini > (weight[i] ^ x)): mini = (weight[i] ^ x) ans = i # Driver code x = 15 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) findMinX(n, x) 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 XOR x static void findMinX(int n, int x) { // For every node for (int i = 1; i <= n; i++) { // If current node's weight XOR x // is minimum so far if (mini > (weight[i] ^ x)) { mini = (weight[i] ^ x); ans = i; } } } // Driver code public static void Main(String[] args) { int x = 15; 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); findMinX(n, x); Console.Write(ans); } } // This code is contributed by PrinciRaj1992
Javascript
<script> // Javascript implementation of the approach let ans = 0, 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[to]; } } // Function to find the node // having minimum sub-tree sum XOR x function findMinX(n,X) { // For every node for (let i = 1; i <= n; i++) { // If current node's weight XOR x // is minimum so far if (mini > (weight[i] ^ x)) { mini = (weight[i] ^ x); ans = i; } } } // Driver code let x = 15; 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); findMinX(n, x); document.write(ans); // This code is contributed by unknown2108 </script>
3
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).
El espacio de la pila de recursividad puede ser de hasta O(n).
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