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) = 31Entrada: 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