Dado un árbol N-ario que consta de N Nodes numerados del 1 al N con raíz en el Node 1 , la tarea es asignar valores a cada Node del árbol de modo que la suma de los valores desde cualquier raíz hasta la ruta de la hoja que contiene al menos dos Nodes no es divisible por el número de Nodes a lo largo de ese camino.
Ejemplos:
Entrada: N = 11, bordes[][] = {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 6}, {2, 10}, { 10, 11}, {3, 7}, {4, 8}, {5, 9}}
Salida: 1 2 1 2 2 1 1
Explicación:De acuerdo con la asignación de valores anterior, a continuación se muestran todos los caminos posibles desde la raíz hasta la hoja:
- Ruta 1 → 2 → 6, suma = 1 + 2 + 1 = 4, longitud = 3.
- Ruta 1 → 2 → 10 → 11, suma = 1 + 2 + 1 + 2 = 6, longitud = 4
- Ruta 1 → 3 → 7, suma = 1 + 2 + 1 = 4, longitud = 3.
- Ruta 1 → 4 → 8, suma = 1 + 2 + 1 = 4, longitud = 3.
- Ruta 1 → 5 → 9, suma = 1 + 2 + 1 = 4, longitud = 3.
De todos los caminos anteriores, ninguno de los caminos existe teniendo la suma de valores divisible por su longitud.
Entrada: N = 3, aristas = {{1, 2}, {2, 3}}
Salida: 1 2 1
Enfoque: El problema dado se puede resolver con base en la observación de que para cualquier camino de raíz a hoja con un número de Nodes de al menos 2 , digamos K si la suma de los valores a lo largo de este camino se encuentra entre K y 2*K exclusivo, entonces esa suma nunca puede ser divisible por K ya que cualquier número sobre el rango (K, 2*K) nunca es divisible por K. Por lo tanto, para K = 1 , asigne valores de Node de Nodes de nivel impar como 1 y el resto como 2 . Siga los pasos a continuación para resolver el problema:
- Inicialice una array , diga answer[] de tamaño N + 1 para almacenar los valores asignados a los Nodes.
- Inicialice una variable, diga K como 1 para asignar valores a cada Node.
- Inicialice una cola que se usa para realizar BFS Traversal en el árbol dado y empuje el Node con el valor 1 en la cola e inicialice el valor en los Nodes como 1 .
- Iterar hasta que la cola no esté vacía y realizar los siguientes pasos:
- Extraiga el Node frontal de la cola y, si el valor asignado al Node emergente es 1 , actualice el valor de K a 2 . De lo contrario, actualice K como 1 .
- Atraviese todos los Nodes secundarios del Node emergente actual y empuje el Node secundario en la cola y asigne el valor K al Node secundario.
- Después de completar los pasos anteriores, imprima los valores almacenados en la array answer[] como resultado.
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; // Function to assign values to nodes // of the tree s.t. sum of values of // nodes of path between any 2 nodes // is not divisible by length of path void assignValues(int Edges[][2], int n) { // Stores the adjacency list vector <int> tree[n + 1]; // Create a adjacency list for(int i = 0; i < n - 1; i++) { int u = Edges[i][0]; int v = Edges[i][1]; tree[u].push_back(v); tree[v].push_back(u); } // Stores whether node is // visited or not vector <bool> visited(n + 1, false); // Stores the node values vector <int> answer(n + 1); // Variable used to assign values to // the nodes alternatively to the // parent child int K = 1; // Declare a queue queue <int> q; // Push the 1st node q.push(1); // Assign K value to this node answer[1] = K; while (!q.empty()) { // Dequeue the node int node = q.front(); q.pop(); // Mark it as visited visited[node] = true; // Upgrade the value of K K = ((answer[node] == 1) ? 2 : 1); // Assign K to the child nodes for (auto child : tree[node]) { // If the child is unvisited if (!visited[child]) { // Enqueue the child q.push(child); // Assign K to the child answer[child] = K; } } } // Print the value assigned to // the nodes for (int i = 1; i <= n; i++) { cout << answer[i] << " "; } } // Driver Code int main() { int N = 11; int Edges[][2] = {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 6}, {2, 10}, {10, 11}, {3, 7}, {4, 8}, {5, 9}}; // Function Call assignValues(Edges, N); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to assign values to nodes // of the tree s.t. sum of values of // nodes of path between any 2 nodes // is not divisible by length of path static void assignValues(int Edges[][], int n) { // Stores the adjacency list ArrayList<ArrayList<Integer>> tree = new ArrayList<>(); for(int i = 0; i < n + 1; i++) tree.add(new ArrayList<>()); // Create a adjacency list for(int i = 0; i < n - 1; i++) { int u = Edges[i][0]; int v = Edges[i][1]; tree.get(u).add(v); tree.get(v).add(u); } // Stores whether node is // visited or not boolean[] visited = new boolean[n + 1]; // Stores the node values int[] answer = new int[n + 1]; // Variable used to assign values to // the nodes alternatively to the // parent child int K = 1; // Declare a queue Queue<Integer> q = new LinkedList<>(); // Push the 1st node q.add(1); // Assign K value to this node answer[1] = K; while (!q.isEmpty()) { // Dequeue the node int node = q.peek(); q.poll(); // Mark it as visited visited[node] = true; // Upgrade the value of K K = ((answer[node] == 1) ? 2 : 1); // Assign K to the child nodes for(Integer child : tree.get(node)) { // If the child is unvisited if (!visited[child]) { // Enqueue the child q.add(child); // Assign K to the child answer[child] = K; } } } // Print the value assigned to // the nodes for(int i = 1; i <= n; i++) { System.out.print(answer[i] + " "); } } // Driver code public static void main(String[] args) { int N = 11; int Edges[][] = { { 1, 2 }, { 1, 3 }, { 1, 4 }, { 1, 5 }, { 2, 6 }, { 2, 10 }, { 10, 11 }, { 3, 7 }, { 4, 8 }, { 5, 9 } }; // Function Call assignValues(Edges, N); } } // This code is contributed by offbeat
Python3
# Python3 program for the above approach from collections import deque # Function to assign values to nodes # of the tree s.t. sum of values of # nodes of path between any 2 nodes # is not divisible by length of path def assignValues(Edges, n): # Stores the adjacency list tree = [[] for i in range(n + 1)] # Create a adjacency list for i in range(n - 1): u = Edges[i][0] v = Edges[i][1] tree[u].append(v) tree[v].append(u) # Stores whether any node is # visited or not visited = [False]*(n+1) # Stores the node values answer = [0]*(n + 1) # Variable used to assign values to # the nodes alternatively to the # parent child K = 1 # Declare a queue q = deque() # Push the 1st node q.append(1) # Assign K value to this node answer[1] = K while (len(q) > 0): # Dequeue the node node = q.popleft() # q.pop() # Mark it as visited visited[node] = True # Upgrade the value of K K = 2 if (answer[node] == 1) else 1 # Assign K to the child nodes for child in tree[node]: # If the child is unvisited if (not visited[child]): # Enqueue the child q.append(child) # Assign K to the child answer[child] = K # Print the value assigned to # the nodes for i in range(1, n + 1): print(answer[i],end=" ") # Driver Code if __name__ == '__main__': N = 7 Edges = [ [ 1, 2 ], [ 4, 6 ], [ 3, 5 ], [ 1, 4 ], [ 7, 5 ], [ 5, 1 ] ] # Function Call assignValues(Edges, N) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach using System; using System.Collections; using System.Collections.Generic; public class GFG{ // Function to assign values to nodes // of the tree s.t. sum of values of // nodes of path between any 2 nodes // is not divisible by length of path static void assignValues(int[, ] Edges, int n) { // Stores the adjacency list LinkedList<int>[] tree = new LinkedList<int>[n+1]; for(int i = 0; i < n + 1; i++) tree[i] = new LinkedList<int>(); // Create a adjacency list for(int i = 0; i < n - 1; i++) { int u = Edges[i, 0]; int v = Edges[i, 1]; tree[u].AddLast(v); tree[v].AddLast(u); } // Stores whether node is // visited or not bool[] visited = new bool[n + 1]; // Stores the node values int[] answer = new int[n + 1]; // Variable used to assign values to // the nodes alternatively to the // parent child int K = 1; // Declare a queue Queue q = new Queue(); // Push the 1st node q.Enqueue(1); // Assign K value to this node answer[1] = K; while (q.Count > 0) { // Dequeue the node int node = (int)q.Peek(); q.Dequeue(); // Mark it as visited visited[node] = true; // Upgrade the value of K K = ((answer[node] == 1) ? 2 : 1); // Assign K to the child nodes foreach (var child in tree[node]) { // If the child is unvisited if (!visited[child]) { // Enqueue the child q.Enqueue(child); // Assign K to the child answer[child] = K; } } } // Print the value assigned to // the nodes for(int i = 1; i <= n; i++) { Console.Write(answer[i] + " "); } } // Driver code static public void Main (){ int N = 11; int[, ] Edges = { { 1, 2 }, { 1, 3 }, { 1, 4 }, { 1, 5 }, { 2, 6 }, { 2, 10 }, { 10, 11 }, { 3, 7 }, { 4, 8 }, { 5, 9 } }; // Function Call assignValues(Edges, N); } } // This code is contributed by Dharanendra L V.
Javascript
<script> // Javascript program for the above approach // Function to assign values to nodes // of the tree s.t. sum of values of // nodes of path between any 2 nodes // is not divisible by length of path function assignValues(Edges, n) { // Stores the adjacency list var tree = Array.from(Array(n+1), ()=> Array()); // Create a adjacency list for(var i = 0; i < n - 1; i++) { var u = Edges[i][0]; var v = Edges[i][1]; tree[u].push(v); tree[v].push(u); } // Stores whether node is // visited or not var visited = Array(n + 1).fill(false); // Stores the node values var answer = Array(n + 1); // Variable used to assign values to // the nodes alternatively to the // parent child var K = 1; // Declare a queue var q = []; // Push the 1st node q.push(1); // Assign K value to this node answer[1] = K; while (q.length!=0) { // Dequeue the node var node = q[0]; q.shift(); // Mark it as visited visited[node] = true; // Upgrade the value of K K = ((answer[node] == 1) ? 2 : 1); // Assign K to the child nodes tree[node].forEach(child => { // If the child is unvisited if (!visited[child]) { // Enqueue the child q.push(child); // Assign K to the child answer[child] = K; } }); } // Print the value assigned to // the nodes for (var i = 1; i <= n; i++) { document.write( answer[i] + " "); } } // Driver Code var N = 11; var Edges = [[1, 2], [1, 3], [1, 4], [1, 5], [2, 6], [2, 10], [10, 11], [3, 7], [4, 8], [5, 9]]; // Function Call assignValues(Edges, N); </script>
1 2 2 2 2 1 1 1 1 1 2
Complejidad temporal: O(N), donde N es el número total de Nodes del árbol.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ramandeep8421 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA