Consultas para calcular Bitwise OR de cada subárbol de un Node dado en un árbol N-ario

Dado un árbol N-ario que consta de N Nodes con valores de 1 a N , una array arr[] que consta de N enteros positivos, donde arr[i] es el valor asociado con el i -ésimo Node, y Q consultas, cada una de las cuales consta de un Node. La tarea de cada consulta es encontrar el OR bit a bit de los valores de Node presentes en el subárbol del Node dado.

Ejemplos:

Entrada: arr[] = {2, 3, 4, 8, 16} Consultas[]: {2, 3, 1} 

Salida: 3 28 31
Explicación:  
Consulta 1: OR bit a bit (subárbol (Node 2)) = OR bit a bit (Node 2) = OR bit a bit (3) = 3
Consulta 2: OR bit a bit (subárbol (Node 3)) = OR bit a bit ( Node 3, Node 4, Node 5) = OR bit a bit (4, 8, 16) = 28
Consulta 3: OR bit a bit (subárbol (Node 1)) = OR bit a bit (Node 1, Node 2, Node 3, Node 4, Node 5 ) = Bit a bit O (2, 3, 4, 8, 16) = 31

Entrada: arr[] = {2, 3, 4, 8, 16} Consultas[]: {4, 5} 

Salida: 8 16
Explicación:  
Consulta 1: OR bit a bit (subárbol (Node 4)) = OR bit a bit (Node 4) = 8
Consulta 2: OR bit a bit (subárbol (Node 5)) = OR bit a bit (Node 5) = 16

Enfoque ingenuo: el enfoque más simple para resolver este problema es atravesar el subárbol del Node dado y, para cada consulta, calcular el OR bit a bit de cada Node en el subárbol de ese Node e imprimir ese valor. 
Complejidad temporal: O(Q * N)
Espacio auxiliar: O(Q * N)

Enfoque eficiente: para optimizar el enfoque anterior, la idea es calcular previamente el OR bit a bit de todos los subárboles presentes en el árbol dado y, para cada consulta, encontrar el XOR bit a bit de los subárboles para cada Node dado. Siga los pasos a continuación para resolver el problema:

  • Inicialice un vector ans[] para almacenar el OR bit a bit de todos los subárboles presentes en el árbol dado.
  • Calcule previamente el OR bit a bit para cada subárbol utilizando la búsqueda en profundidad primero (DFS) .
  • Si el Node es un Node hoja , el OR bit a bit de este Node es el valor del Node en sí.
  • De lo contrario, el OR bit a bit para el subárbol es igual al OR bit a bit de todos los valores del subárbol de sus hijos.
  • Después de completar los pasos anteriores, imprima el valor almacenado en ans[Queries[i]] para cada i -ésima consulta.

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;
 
// Maximum Number of nodes
const int N = 1e5 + 5;
 
// Adjacency list
vector<int> adj[N];
 
// Stores Bitwise OR of each node
vector<int> answer(N);
 
// Function to add edges to the Tree
void addEdgesToGraph(int Edges[][2],
                     int N)
{
    // Traverse the edges
    for (int i = 0; i < N - 1; i++) {
        int u = Edges[i][0];
        int v = Edges[i][1];
 
        // Add edges
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
}
 
// Function to perform DFS
// Traversal on the given tree
void DFS(int node, int parent, int Val[])
{
    // Initialize answer with bitwise
    // OR of current node
    answer[node] = Val[node];
 
    // Iterate over each child
    // of the current node
    for (int child : adj[node]) {
 
        // Skip parent node
        if (child == parent)
            continue;
 
        // Call DFS for each child
        DFS(child, node, Val);
 
        // Taking bitwise OR of the
        // answer of the child to
        // find node's OR value
        answer[node] = (answer[node]
                        | answer[child]);
    }
}
 
// Function to call DFS from the'=
// root for precomputing answers
void preprocess(int Val[])
{
    DFS(1, -1, Val);
}
 
// Function to calculate and print
// the Bitwise OR for Q queries
void findSubtreeOR(int Queries[], int Q,
                   int Val[])
{
    // Perform preprocessing
    preprocess(Val);
 
    // Iterate over each given query
    for (int i = 0; i < Q; i++) {
 
        cout << answer[Queries[i]]
             << ' ';
    }
}
 
// Utility function to find and
// print bitwise OR for Q queries
void findSubtreeORUtil(
    int N, int Edges[][2], int Val[],
    int Queries[], int Q)
{
    // Function to add edges to graph
    addEdgesToGraph(Edges, N);
 
    // Function call
    findSubtreeOR(Queries, Q, Val);
}
 
// Driver Code
int main()
{
    // Number of nodes
    int N = 5;
    int Edges[][2]
        = { { 1, 2 }, { 1, 3 },
            { 3, 4 }, { 3, 5 } };
 
    int Val[] = { 0, 2, 3, 4, 8, 16 };
    int Queries[] = { 2, 3, 1 };
 
    int Q = sizeof(Queries)
            / sizeof(Queries[0]);
 
    // Function call
    findSubtreeORUtil(N, Edges, Val,
                      Queries, Q);
 
    return 0;
}

Java

// Java program for above approach
import java.util.*;
import java.lang.*;
import java.io.*;
 
class GFG
{
 
  // Maximum Number of nodes
  static int N = (int)1e5 + 5;
 
  // Adjacency list
  static ArrayList<ArrayList<Integer>> adj;
 
  // Stores Bitwise OR of each node
  static int[] answer;
 
  // Function to add edges to the Tree
  static void addEdgesToGraph(int Edges[][],
                              int N)
  {
    // Traverse the edges
    for (int i = 0; i < N - 1; i++)
    {
      int u = Edges[i][0];
      int v = Edges[i][1];
 
      // Add edges
      adj.get(u).add(v);
      adj.get(v).add(u);
    }
  }
 
  // Function to perform DFS
  // Traversal on the given tree
  static void DFS(int node, int parent, int Val[])
  {
 
    // Initialize answer with bitwise
    // OR of current node
    answer[node] = Val[node];
 
    // Iterate over each child
    // of the current node
    for (Integer child : adj.get(node))
    {
 
      // Skip parent node
      if (child == parent)
        continue;
 
      // Call DFS for each child
      DFS(child, node, Val);
 
      // Taking bitwise OR of the
      // answer of the child to
      // find node's OR value
      answer[node] = (answer[node]
                      | answer[child]);
    }
  }
 
  // Function to call DFS from the'=
  // root for precomputing answers
  static void preprocess(int Val[])
  {
    DFS(1, -1, Val);
  }
 
  // Function to calculate and print
  // the Bitwise OR for Q queries
  static void findSubtreeOR(int Queries[], int Q,
                            int Val[])
  {
     
    // Perform preprocessing
    preprocess(Val);
 
    // Iterate over each given query
    for (int i = 0; i < Q; i++)
    {
      System.out.println(answer[Queries[i]] + " ");
    }
  }
 
  // Utility function to find and
  // print bitwise OR for Q queries
  static void findSubtreeORUtil(int N, int Edges[][],
                                int Val[], int Queries[],
                                int Q)
  {
 
    // Function to add edges to graph
    addEdgesToGraph(Edges, N);
 
    // Function call
    findSubtreeOR(Queries, Q, Val);
  }
 
  // Driver function
  public static void main (String[] args)
  {
 
    adj = new ArrayList<>();
    for(int i = 0; i < N; i++)
      adj.add(new ArrayList<>());
    answer = new int[N];
    N = 5;
    int Edges[][] = { { 1, 2 }, { 1, 3 },
                     { 3, 4 }, { 3, 5 } };
 
    int Val[] = { 0, 2, 3, 4, 8, 16 };
    int Queries[] = { 2, 3, 1 };
    int Q = Queries.length;
 
    // Function call
    findSubtreeORUtil(N, Edges, Val,
                      Queries, Q);
  }
}
 
// This code is contributed by offbeat

Python3

# Python3 program for the above approach
  
# Maximum Number of nodes
N = 100005;
  
# Adjacency list
adj = [[] for i in range(N)];
  
# Stores Bitwise OR of each node
answer = [0 for i in range(N)]
  
# Function to add edges to the Tree
def addEdgesToGraph(Edges, N):
 
    # Traverse the edges
    for i in range(N - 1):
     
        u = Edges[i][0];
        v = Edges[i][1];
  
        # Add edges
        adj[u].append(v);
        adj[v].append(u);
     
# Function to perform DFS
# Traversal on the given tree
def DFS(node, parent, Val):
 
    # Initialize answer with bitwise
    # OR of current node
    answer[node] = Val[node];
  
    # Iterate over each child
    # of the current node
    for child in adj[node]:
     
        # Skip parent node
        if (child == parent):
            continue;
  
        # Call DFS for each child
        DFS(child, node, Val);
  
        # Taking bitwise OR of the
        # answer of the child to
        # find node's OR value
        answer[node] = (answer[node]
                        | answer[child]);
     
# Function to call DFS from the'=
# root for precomputing answers
def preprocess( Val):
 
    DFS(1, -1, Val);
 
# Function to calculate and print
# the Bitwise OR for Q queries
def findSubtreeOR(Queries, Q, Val):
 
    # Perform preprocessing
    preprocess(Val);
  
    # Iterate over each given query
    for i in range(Q):
         
        print(answer[Queries[i]], end=' ')
   
# Utility function to find and
# print bitwise OR for Q queries
def findSubtreeORUtil( N, Edges, Val, Queries, Q):
 
    # Function to add edges to graph
    addEdgesToGraph(Edges, N);
  
    # Function call
    findSubtreeOR(Queries, Q, Val);
  
# Driver Code
if __name__=='__main__':
     
    # Number of nodes
    N = 5;
    Edges = [ [ 1, 2 ], [ 1, 3 ], [ 3, 4 ], [ 3, 5 ] ];
  
    Val = [ 0, 2, 3, 4, 8, 16 ];
    Queries = [ 2, 3, 1 ];
  
    Q = len(Queries)
  
    # Function call
    findSubtreeORUtil(N, Edges, Val,Queries, Q);
 
    # This code is contributed by rutvik_56

C#

// C# program to generate
// n-bit Gray codes
using System;
using System.Collections.Generic;
class GFG
{
 
  // Maximum Number of nodes
  static int N = (int)1e5 + 5;
 
  // Adjacency list
  static List<List<int> > adj;
 
  // Stores Bitwise OR of each node
  static int[] answer;
 
  // Function to Add edges to the Tree
  static void AddEdgesToGraph(int[, ] Edges, int N)
  {
 
    // Traverse the edges
    for (int i = 0; i < N - 1; i++) {
      int u = Edges[i, 0];
      int v = Edges[i, 1];
 
      // Add edges
      adj[u].Add(v);
      adj[v].Add(u);
    }
  }
 
  // Function to perform DFS
  // Traversal on the given tree
  static void DFS(int node, int parent, int[] Val)
  {
 
    // Initialize answer with bitwise
    // OR of current node
    answer[node] = Val[node];
 
    // Iterate over each child
    // of the current node
    foreach(int child in adj[node])
    {
 
      // Skip parent node
      if (child == parent)
        continue;
 
      // Call DFS for each child
      DFS(child, node, Val);
 
      // Taking bitwise OR of the
      // answer of the child to
      // find node's OR value
      answer[node] = (answer[node] | answer[child]);
    }
  }
 
  // Function to call DFS from the'=
  // root for precomputing answers
  static void preprocess(int[] Val) { DFS(1, -1, Val); }
 
  // Function to calculate and print
  // the Bitwise OR for Q queries
  static void findSubtreeOR(int[] Queries, int Q,
                            int[] Val)
  {
 
    // Perform preprocessing
    preprocess(Val);
 
    // Iterate over each given query
    for (int i = 0; i < Q; i++) {
      Console.Write(answer[Queries[i]] + " ");
    }
  }
 
  // Utility function to find and
  // print bitwise OR for Q queries
  static void findSubtreeORUtil(int N, int[, ] Edges,
                                int[] Val, int[] Queries,
                                int Q)
  {
 
    // Function to Add edges to graph
    AddEdgesToGraph(Edges, N);
 
    // Function call
    findSubtreeOR(Queries, Q, Val);
  }
 
  // Driver function
  public static void Main(String[] args)
  {
 
    adj = new List<List<int> >();
    for (int i = 0; i < N; i++)
      adj.Add(new List<int>());
    answer = new int[N];
    N = 5;
    int[, ] Edges
      = { { 1, 2 }, { 1, 3 }, { 3, 4 }, { 3, 5 } };
 
    int[] Val = { 0, 2, 3, 4, 8, 16 };
    int[] Queries = { 2, 3, 1 };
    int Q = Queries.Length;
 
    // Function call
    findSubtreeORUtil(N, Edges, Val, Queries, Q);
  }
}
 
// This code is contributed by grand_master.

Javascript

<script>
// Javascript program for the above approach
 
// Maximum Number of nodes
const N = 1e5 + 5;
 
// Adjacency list
let adj = [];
 
for (let i = 0; i < N; i++) {
    adj.push([])
}
 
// Stores Bitwise OR of each node
let answer = new Array(N);
 
// Function to add edges to the Tree
function addEdgesToGraph(Edges, N) {
    // Traverse the edges
    for (let i = 0; i < N - 1; i++) {
        let u = Edges[i][0];
        let v = Edges[i][1];
 
        // Add edges
        adj[u].push(v);
        adj[v].push(u);
    }
}
 
// Function to perform DFS
// Traversal on the given tree
function DFS(node, parent, Val) {
    // Initialize answer with bitwise
    // OR of current node
    answer[node] = Val[node];
 
    // Iterate over each child
    // of the current node
    for (let child of adj[node]) {
 
        // Skip parent node
        if (child == parent)
            continue;
 
        // Call DFS for each child
        DFS(child, node, Val);
 
        // Taking bitwise OR of the
        // answer of the child to
        // find node's OR value
        answer[node] = (answer[node] | answer[child]);
    }
}
 
// Function to call DFS from the'=
// root for precomputing answers
function preprocess(Val) {
    DFS(1, -1, Val);
}
 
// Function to calculate and print
// the Bitwise OR for Q queries
function findSubtreeOR(Queries, Q, Val) {
    // Perform preprocessing
    preprocess(Val);
 
    // Iterate over each given query
    for (let i = 0; i < Q; i++) {
 
        document.write(answer[Queries[i]] + ' ');
    }
}
 
// Utility function to find and
// print bitwise OR for Q queries
function findSubtreeORUtil(N, Edges, Val, Queries, Q) {
    // Function to add edges to graph
    addEdgesToGraph(Edges, N);
 
    // Function call
    findSubtreeOR(Queries, Q, Val);
}
 
// Driver Code
 
// Number of nodes
let n = 5;
let Edges
    = [[1, 2], [1, 3],
       [3, 4], [3, 5]];
 
let Val = [0, 2, 3, 4, 8, 16];
let Queries = [2, 3, 1];
 
let Q = Queries.length;
 
// Function call
findSubtreeORUtil(n, Edges, Val, Queries, Q);
 
 
 
// This code is contributed by _saurabh_jaiswal
</script>
Producción: 

3 28 31

 

Complejidad temporal: O(N + Q)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por math_lover 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 *