Construya un árbol cuya suma de Nodes de todo el camino de la raíz a la hoja no sea divisible por el conteo de Nodes en ese camino

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>
Producción: 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *