Dado un árbol N-ario que contiene N Nodes, valores asociados con cada Node y Q consultas, donde cada consulta contiene un solo Node. La tarea es encontrar el GCD de los valores de todos los Nodes presentes en el subárbol (incluido él mismo).
Ejemplo:
Árbol:
1(2) / \ / \ 2(3) 3(4) / \ / \ 4(8) 5(16)query[]: {2, 3, 1}
Output: {3, 4, 1}
Explanation:
For query 1: GCD(subtree(node2)) = GCD(node2) = GCD(3) = 3
For query 2: GCD(subtree(node3)) = GCD(node3, node4, node5) = GCD(4, 8, 16) = 4
Enfoque ingenuo:
- Para cada consulta, recorra todo el subárbol del Node dado .
- Calcule el GCD de cada Node en el subárbol y devuélvalo.
Complejidad de tiempo : O(Q*N)
Complejidad de espacio : O(Q*N)
Enfoque eficiente:
- Inicialmente, calcule previamente el GCD para cada subárbol utilizando la búsqueda en profundidad primero (DFS) .
- Si el Node es un Node hoja, el GCD de este Node es el número mismo.
- Para el Node que no es hoja, el GCD del subárbol es el GCD de todos los valores del subárbol de sus hijos.
- Ahora, es fácil encontrar una respuesta en tiempo constante ya que la respuesta ya está almacenada
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find GCD // of each subtree for // a given node by Q queries #include <bits/stdc++.h> using namespace std; // Maximum Number of nodes const int N = 1e5 + 5; // Tree represented // as adjacency list vector<vector<int> > v(N); // for storing value // associates with node vector<int> val(N); // for storing GCD // of every subarray vector<int> answer(N); // number of nodes int n; // Function to find GCD of two numbers // using Euclidean algo int gcd(int a, int b) { // if b == 0 // then simply return a if (b == 0) return a; return gcd(b, a % b); } // DFS function to traverse the tree void DFS(int node, int parent) { // initializing answer // with GCD of this node. answer[node] = val[node]; // iterate over each // child of current node for (int child : v[node]) { // skipping the parent if (child == parent) continue; // call DFS for each child DFS(child, node); // taking GCD of the answer // of the child to // find node's GCD answer[node] = gcd(answer[node], answer[child]); } } // Calling DFS from the root (1) // for precomputing answers void preprocess() { DFS(1, -1); } // Function to find and // print GCD for Q queries void findGCD(int queries[], int q) { // doing preprocessing preprocess(); // iterate over each given query for (int i = 0; i < q; i++) { int GCD = answer[queries[i]]; cout << "For subtree of " << queries[i] << ", GCD = " << GCD << endl; } } // Driver code int main() { /* Tree: 1 (2) / \ 2 (3) 3 (4) / \ 4 (8) 5 (16) */ n = 5; // making a undirected tree v[1].push_back(2); v[2].push_back(1); v[1].push_back(3); v[3].push_back(1); v[3].push_back(4); v[4].push_back(3); v[3].push_back(5); v[5].push_back(3); // values associated with nodes val[1] = 2; val[2] = 3; val[3] = 4; val[4] = 8; val[5] = 16; int queries[] = { 2, 3, 1 }; int q = sizeof(queries) / sizeof(queries[0]); // Function call findGCD(queries, q); return 0; }
Java
// Java program to find GCD // of each subtree for // a given node by Q queries import java.util.*; class GFG { // Maximum Number of nodes static int N = (int)(1e5 + 5); // Tree represented // as adjacency list static Vector<Integer>[] v = new Vector[N]; // For storing value // associates with node static int[] val = new int[N]; // For storing GCD // of every subarray static int[] answer = new int[N]; // Number of nodes static int n; // Function to find GCD of // two numbers using // Euclidean algo static int gcd(int a, int b) { // If b == 0 // then simply return a if (b == 0) return a; return gcd(b, a % b); } // DFS function to traverse // the tree static void DFS(int node, int parent) { // Initializing answer // with GCD of this node. answer[node] = val[node]; // Iterate over each // child of current node for (int child : v[node]) { // Skipping the parent if (child == parent) continue; // Call DFS for each child DFS(child, node); // Taking GCD of the answer // of the child to // find node's GCD answer[node] = gcd(answer[node], answer[child]); } } // Calling DFS from the root (1) // for precomputing answers static void preprocess() { DFS(1, -1); } // Function to find and // print GCD for Q queries static void findGCD(int queries[], int q) { // Doing preprocessing preprocess(); // iterate over each given query for (int i = 0; i < q; i++) { int GCD = answer[queries[i]]; System.out.print("For subtree of " + queries[i] + ", GCD = " + GCD + "\n"); } } // Driver code public static void main(String[] args) { /* Tree: 1 (2) / \ 2 (3) 3 (4) / \ 4 (8) 5 (16) */ n = 5; for (int i = 0; i < v.length; i++) v[i] = new Vector<Integer>(); // Making a undirected tree v[1].add(2); v[2].add(1); v[1].add(3); v[3].add(1); v[3].add(4); v[4].add(3); v[3].add(5); v[5].add(3); // Values associated with nodes val[1] = 2; val[2] = 3; val[3] = 4; val[4] = 8; val[5] = 16; int queries[] = { 2, 3, 1 }; int q = queries.length; // Function call findGCD(queries, q); } } // This code is contributed by shikhasingrajput
Python3
# Python3 program to find GCD # of each subtree for a # given node by Q queries # Maximum number of nodes N = 10**5 + 5 # Tree represented # as adjacency list v = [[] for i in range(N)] # For storing value # associates with node val = [0] * (N) # For storing GCD # of every subarray answer = [0] * (N) # Number of nodes n = 0 # Function to find GCD of two # numbers. Using Euclidean algo def gcd(a, b): # If b == 0 then # simply return a if (b == 0): return a return gcd(b, a % b) # DFS function to traverse the tree def DFS(node, parent): # Initializing answer # with GCD of this node. answer[node] = val[node] # Iterate over each # child of current node for child in v[node]: # Skipping the parent if (child == parent): continue # Call DFS for each child DFS(child, node) # Taking GCD of the answer # of the child to # find node's GCD answer[node] = gcd(answer[node], answer[child]) # Calling DFS from the root (1) # for precomputing answers def preprocess(): DFS(1, -1) # Function to find and # prGCD for Q queries def findGCD(queries, q): # Doing preprocessing preprocess() # Iterate over each given query for i in range(q): GCD = answer[queries[i]] print("For subtree of ", queries[i], ", GCD = ", GCD) # Driver code if __name__ == '__main__': """ Tree: 1 (2) / \ 2 (3) 3 (4) / \ 4 (8) 5 (16) """ n = 5 # Making a undirected tree v[1].append(2) v[2].append(1) v[1].append(3) v[3].append(1) v[3].append(4) v[4].append(3) v[3].append(5) v[5].append(3) # Values associated with nodes val[1] = 2 val[2] = 3 val[3] = 4 val[4] = 8 val[5] = 16 queries = [2, 3, 1] q = len(queries) # Function call findGCD(queries, q) # This code is contributed by mohit kumar 29
C#
// C# program to find GCD // of each subtree for // a given node by Q queries using System; using System.Collections.Generic; public class GFG { // Maximum Number of nodes static int N = (int)(1e5 + 5); // Tree represented // as adjacency list static List<int>[] v = new List<int>[ N ]; // For storing value // associates with node static int[] val = new int[N]; // For storing GCD // of every subarray static int[] answer = new int[N]; // Number of nodes static int n; // Function to find GCD of // two numbers using // Euclidean algo static int gcd(int a, int b) { // If b == 0 // then simply return a if (b == 0) return a; return gcd(b, a % b); } // DFS function to traverse // the tree static void DFS(int node, int parent) { // Initializing answer // with GCD of this node. answer[node] = val[node]; // Iterate over each // child of current node foreach(int child in v[node]) { // Skipping the parent if (child == parent) continue; // Call DFS for each child DFS(child, node); // Taking GCD of the answer // of the child to // find node's GCD answer[node] = gcd(answer[node], answer[child]); } } // Calling DFS from the root (1) // for precomputing answers static void preprocess() { DFS(1, -1); } // Function to find and // print GCD for Q queries static void findGCD(int[] queries, int q) { // Doing preprocessing preprocess(); // iterate over each given query for (int i = 0; i < q; i++) { int GCD = answer[queries[i]]; Console.Write("For subtree of " + queries[i] + ", GCD = " + GCD + "\n"); } } // Driver code public static void Main(String[] args) { /* Tree: 1 (2) / \ 2 (3) 3 (4) / \ 4 (8) 5 (16) */ n = 5; for (int i = 0; i < v.Length; i++) v[i] = new List<int>(); // Making a undirected tree v[1].Add(2); v[2].Add(1); v[1].Add(3); v[3].Add(1); v[3].Add(4); v[4].Add(3); v[3].Add(5); v[5].Add(3); // Values associated with nodes val[1] = 2; val[2] = 3; val[3] = 4; val[4] = 8; val[5] = 16; int[] queries = { 2, 3, 1 }; int q = queries.Length; findGCD(queries, q); } } // This code is contributed by Amit Katiyar
Javascript
<script> // Javascript program to find GCD // of each subtree for // a given node by Q queries // Maximum Number of nodes var N = 100005; // Tree represented // as adjacency list var v = Array.from(Array(N), ()=>Array()); // for storing value // associates with node var val = Array(N); // for storing GCD // of every subarray var answer = Array(N); // number of nodes var n; // Function to find GCD of two numbers // using Euclidean algo function gcd(a, b) { // If b == 0 // then simply return a if (b == 0) return a; return gcd(b, a % b); } // DFS function to traverse the tree function DFS(node, parent) { // Initializing answer // with GCD of this node. answer[node] = val[node]; // Iterate over each // child of current node v[node].forEach(child => { // Skipping the parent if (child != parent) { // Call DFS for each child DFS(child, node); // Taking GCD of the answer // of the child to // find node's GCD answer[node] = gcd(answer[node], answer[child]); } }); } // Calling DFS from the root (1) // for precomputing answers function preprocess() { DFS(1, -1); } // Function to find and // print GCD for Q queries function findGCD(queries, q) { // Doing preprocessing preprocess(); // Iterate over each given query for(var i = 0; i < q; i++) { var GCD = answer[queries[i]]; document.write("For subtree of " + queries[i] + ", GCD = " + GCD + "<br>"); } } // Driver code /* Tree: 1 (2) / \ 2 (3) 3 (4) / \ 4 (8) 5 (16) */ n = 5; // Making a undirected tree v[1].push(2); v[2].push(1); v[1].push(3); v[3].push(1); v[3].push(4); v[4].push(3); v[3].push(5); v[5].push(3); // Values associated with nodes val[1] = 2; val[2] = 3; val[3] = 4; val[4] = 8; val[5] = 16; var queries = [ 2, 3, 1 ]; var q = queries.length; // Function call findGCD(queries, q); // This code is contributed by itsok </script>
For subtree of 2, GCD = 3 For subtree of 3, GCD = 4 For subtree of 1, GCD = 1
Complejidad temporal: O(N + Q)
Complejidad espacial: O(N)
Publicación traducida automáticamente
Artículo escrito por insiderpants y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA