Dado un árbol n-ario y Q consultas donde cada consulta consta de un número entero u que denota un Node. La tarea es imprimir el xor de todos los valores de los Nodes en el subárbol del Node dado.
Ejemplos:
Aporte:
q[] = {0, 1, 4, 5}
Salida:
0
3
5
6
Consulta 1: (1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7) = 0
Consulta 2: (2 ^ 4 ^ 5) = 3
Consulta 3: (5) = 5
Consulta 4: (6) = 6
Enfoque ingenuo: para cada Node, tenemos que atravesar el árbol para que cada consulta encuentre el xor de todos los Nodes del subárbol. Entonces la complejidad del código será O(N * Q) .
Enfoque eficiente: si calculamos previamente el xor de todos los Nodes del subárbol recorriendo el árbol total una vez y primero calculando el xor de todos los Nodes del subárbol del Node secundario primero y luego usando el valor de el Node hijo para calcular el xor de todos los Nodes del subárbol del Node padre. De esta forma podemos calcular el xor en tiempo O(N) y almacenarlos para consultas. Cuando se realiza una consulta, imprimiremos el valor precalculado en tiempo O(1) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Adjacency list of the graph vector<vector<int> > graph; // Value of the node vector<int> values, xor_values; // Function to pre-compute the xor values int pre_compute_xor(int i, int prev) { // xor of the sub-tree int x = values[i]; for (int j = 0; j < graph[i].size(); j++) if (graph[i][j] != prev) { // xor x with xor of the sub-tree // of it child nodes x ^= pre_compute_xor(graph[i][j], i); } xor_values[i] = x; // Return the xor return x; } // Function to return the xor of // the nodes of the sub-tree // rooted at node u int query(int u) { return xor_values[u]; } // Driver code int main() { int n = 7; graph.resize(n); xor_values.resize(n); // Create the graph graph[0].push_back(1); graph[0].push_back(2); graph[1].push_back(3); graph[1].push_back(4); graph[2].push_back(5); graph[2].push_back(6); // Set the values of the nodes values.push_back(1); values.push_back(2); values.push_back(3); values.push_back(4); values.push_back(5); values.push_back(6); values.push_back(7); // Pre-computation pre_compute_xor(0, -1); // Perform queries int queries[] = { 0, 1, 4, 5 }; int q = sizeof(queries) / sizeof(queries[0]); for (int i = 0; i < q; i++) cout << query(queries[i]) << endl; return 0; }
Java
// Java implementation of the approach import java.util.*; class GFG { static int n = 7; // Adjacency list of the graph static Vector<Integer> []graph = new Vector[n]; // Value of the node static Vector<Integer> values = new Vector<Integer>(), xor_values = new Vector<Integer>(n); // Function to pre-compute the xor values static int pre_compute_xor(int i, int prev) { // xor of the sub-tree int x = values.get(i); for (int j = 0; j < graph[i].size(); j++) if (graph[i].get(j)!= prev) { // xor x with xor of the sub-tree // of it child nodes x ^= pre_compute_xor(graph[i].get(j), i); } xor_values.remove(i); xor_values.add(i, x); // Return the xor return x; } // Function to return the xor of // the nodes of the sub-tree // rooted at node u static int query(int u) { return xor_values.get(u); } // Driver code public static void main(String[] args) { for(int i = 0; i < n; i++) { graph[i] = new Vector<Integer>(); xor_values.add(0); } // Create the graph graph[0].add(1); graph[0].add(2); graph[1].add(3); graph[1].add(4); graph[2].add(5); graph[2].add(6); // Set the values of the nodes values.add(1); values.add(2); values.add(3); values.add(4); values.add(5); values.add(6); values.add(7); // Pre-computation pre_compute_xor(0, -1); // Perform queries int queries[] = { 0, 1, 4, 5 }; int q = queries.length; for (int i = 0; i < q; i++) System.out.print(query(queries[i]) +"\n"); } } // This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach # Adjacency list of the graph graph = [] # Value of the node values = [] xor_values = [] # Function to pre-compute the xor values def pre_compute_xor(i, prev): # xor of the sub-tree x = values[i] for j in range(len(graph[i])): if graph[i][j] != prev: # xor x with xor of the sub-tree # of it child nodes x ^= pre_compute_xor(graph[i][j], i) xor_values[i] = x # Return the xor return x # Function to return the xor of # the nodes of the sub-tree # rooted at node u def query(u): return xor_values[u] # Driver code n = 7 for i in range(n): graph.append([]) xor_values.append(0) # Create the graph graph[0].append(1) graph[0].append(2) graph[1].append(3) graph[1].append(4) graph[2].append(5) graph[2].append(6) # Set the values of the nodes values.append(1) values.append(2) values.append(3) values.append(4) values.append(5) values.append(6) values.append(7) # Pre-computation pre_compute_xor(0, -1) # Perform queries queries = [ 0, 1, 4, 5 ] q = len(queries) for i in range(q): print(query(queries[i])) # This code is contributed by divyamohan123
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { static int n = 7; // Adjacency list of the graph static List<int> []graph = new List<int>[n]; // Value of the node static List<int> values = new List<int>(), xor_values = new List<int>(n); // Function to pre-compute the xor values static int pre_compute_xor(int i, int prev) { // xor of the sub-tree int x = values[i]; for (int j = 0; j < graph[i].Count; j++) if (graph[i][j] != prev) { // xor x with xor of the sub-tree // of it child nodes x ^= pre_compute_xor(graph[i][j], i); } xor_values.RemoveAt(i); xor_values.Insert(i, x); // Return the xor return x; } // Function to return the xor of // the nodes of the sub-tree // rooted at node u static int query(int u) { return xor_values[u]; } // Driver code public static void Main(String[] args) { for(int i = 0; i < n; i++) { graph[i] = new List<int>(); xor_values.Add(0); } // Create the graph graph[0].Add(1); graph[0].Add(2); graph[1].Add(3); graph[1].Add(4); graph[2].Add(5); graph[2].Add(6); // Set the values of the nodes values.Add(1); values.Add(2); values.Add(3); values.Add(4); values.Add(5); values.Add(6); values.Add(7); // Pre-computation pre_compute_xor(0, -1); // Perform queries int []queries = { 0, 1, 4, 5 }; int q = queries.Length; for (int i = 0; i < q; i++) Console.Write(query(queries[i]) +"\n"); } } // This code is contributed by PrinciRaj1992
Javascript
<script> // Javascript implementation of the approach let n = 7; // Adjacency list of the graph let graph = new Array(n); // Value of the node let values = new Array(); let xor_values = new Array(n); // Function to pre-compute the xor values function pre_compute_xor(i, prev) { // xor of the sub-tree let x = values[i]; for (let j = 0; j < graph[i].length; j++) if (graph[i][j] != prev) { // xor x with xor of the sub-tree // of it child nodes x ^= pre_compute_xor(graph[i][j], i); } xor_values.splice(i, 1); xor_values.splice(i, 0, x); // Return the xor return x; } // Function to return the xor of // the nodes of the sub-tree // rooted at node u function query(u) { return xor_values[u]; } // Driver code for (let i = 0; i < n; i++) { graph[i] = new Array(); xor_values.push(0); } // Create the graph graph[0].push(1); graph[0].push(2); graph[1].push(3); graph[1].push(4); graph[2].push(5); graph[2].push(6); // Set the values of the nodes values.push(1); values.push(2); values.push(3); values.push(4); values.push(5); values.push(6); values.push(7); // Pre-computation pre_compute_xor(0, -1); // Perform queries let queries = [0, 1, 4, 5]; let q = queries.length; for (let i = 0; i < q; i++) document.write(query(queries[i]) + "<br>"); // This code is contributed by gfgking </script>
0 3 5 6
Publicación traducida automáticamente
Artículo escrito por andrew1234 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA