Dado un árbol genérico que consta de N Nodes numerados de 0 a N – 1 que tiene su raíz en el Node 0 y una array val[] tal que el valor en cada Node está representado por val[i] , la tarea de cada Node es encontrar el valor de MEX de su subárbol.
El valor MEX del Node V se define como el número positivo faltante más pequeño en un árbol con raíz en el Node V.
Ejemplos:
Entrada: N = 6, aristas = {{0, 1}, {1, 2}, {0, 3}, {3, 4}, {3, 5}}, val[] = {4, 3, 5 , 1, 0, 2}
Salida: [6, 0, 0, 3, 1, 0]
Explicación:
0(4)
/ \
1(3) 3(1)
/ / \
2(5) 4(0) 5 (2)En los subárboles de:
Node 0: Todos los valores en el rango [0, 5] están presentes, por lo tanto, el valor no negativo más pequeño que no está presente es 6.
Node 1: El valor no negativo más pequeño que no está presente en el subárbol del Node 1 es 0.
Node 2: el valor no negativo más pequeño que no está presente en el subárbol del Node 2 ausente es 0.
Node 3: todos los valores en el rango [0, 2] están presentes, por lo tanto, el valor no negativo más pequeño que no está presente en el subárbol de el Node 3 es 3.
Node 4: el valor no negativo más pequeño que no está presente en el subárbol del Node 4 es 1.
Node 5: el valor no negativo más pequeño que no está presente en el subárbol del Node 5 es 0.
Enfoque: El problema dado se puede resolver utilizando DFS Traversal en el árbol dado y realizando la búsqueda binaria para encontrar los enteros positivos mínimos que faltan en cada subárbol de Nodes. Siga los pasos a continuación para resolver el problema:
- Inicialice una array , diga sol[] para almacenar el MEX para cada Node.
- Realice el DFS Traversal desde el Node 0 y realice los siguientes pasos:
- Almacene todos los Nodes durante DFS para cada Node en el vector.
- Combine los dos vectores en el orden ordenado para cada Node en las llamadas recursivas.
- Aplique la búsqueda binaria en la lista ordenada para encontrar el valor entero no negativo más pequeño que no está presente en la array ordenada y almacene el valor de MEX del subárbol actual en la array sol[] .
- Después de completar los pasos anteriores, imprima el valor almacenado en la array sol[] como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Stores the edges of the tree
vector<vector<int> > edges;
// Function to add edges
void add_edge(int x, int y)
{
edges.push_back({ x, y });
}
// Function to merge two sorted vectors
vector<int> merge(vector<int>& a,
vector<int>& b)
{
// To store the result
vector<int> res;
int i = 0, j = 0;
int n = a.size(), m = b.size();
// Iterating both vectors
while (i < n && j < m) {
if (a[i] < b[j])
res.push_back(a[i++]);
else if (b[j] < a[i])
res.push_back(b[j++]);
}
// Pushing remaining elements of
// vector a
while (i < n)
res.push_back(a[i++]);
// Pushing remaining elements of
// vector b
while (j < m)
res.push_back(b[j++]);
return res;
}
// Function to perform the DFS Traversal
// that returns the subtree of node
// in sorted manner
vector<int> help(vector<int> tree[], int x,
int p, vector<int>& c,
vector<int>& sol)
{
vector<int> res;
res.push_back(c[x]);
// Iterate the childrens
for (auto i : tree[x]) {
// All values of subtree
// i in sorted manner
if (i != p) {
vector<int> tmp
= help(tree, i, x, c, sol);
res = merge(res, tmp);
}
}
int l = 0, r = res.size() - 1;
int ans = res.size();
// Binary search to find MEX
while (l <= r) {
// Find the mid
int mid = (l + r) / 2;
// Update the ranges
if (res[mid] > mid)
r = mid - 1;
else {
ans = mid + 1;
l = mid + 1;
}
}
if (res[0] != 0)
ans = 0;
// Update the MEX for the current
// tree node
sol[x] = ans;
return res;
}
// Function to find MEX of each
// subtree of tree
void solve(int A, vector<int> C)
{
int n = A;
vector<int> tree[n + 1];
for (auto i : edges) {
tree[i[0]].push_back(i[1]);
tree[i[1]].push_back(i[0]);
}
vector<int> sol(n, 0);
// Function Call
help(tree, 0, -1, C, sol);
// Print the ans for each nodes
for (auto i : sol)
cout << i << " ";
}
// Driver Code
int main()
{
int N = 6;
add_edge(0, 1);
add_edge(1, 2);
add_edge(0, 3);
add_edge(3, 4);
add_edge(3, 5);
vector<int> val = { 4, 3, 5, 1, 0, 2 };
solve(N, val);
return 0;
}
Java
// Java program for the above approach
import java.util.ArrayList;
import java.util.Arrays;
public class GFG {
// Stores the edges of the tree
static ArrayList<int[]> edges = new ArrayList<int[]>();
// Function to add edges
static void add_edge(int x, int y)
{
edges.add(new int[] { x, y });
}
// Function to merge two sorted vectors
static ArrayList<Integer> merge(ArrayList<Integer> a,
ArrayList<Integer> b)
{
// To store the result
ArrayList<Integer> res = new ArrayList<Integer>();
int i = 0, j = 0;
int n = a.size(), m = b.size();
// Iterating both vectors
while (i < n && j < m) {
if (a.get(i) < b.get(j))
res.add(a.get(i++));
else if (b.get(j) < a.get(i))
res.add(b.get(j++));
}
// Pushing remaining elements of
// vector a
while (i < n)
res.add(a.get(i++));
// Pushing remaining elements of
// vector b
while (j < m)
res.add(b.get(j++));
return res;
}
// Function to perform the DFS Traversal
// that returns the subtree of node
// in sorted manner
static ArrayList<Integer>
help(ArrayList<Integer>[] tree, int x, int p, int[] c,
int[] sol)
{
ArrayList<Integer> res = new ArrayList<Integer>();
res.add(c[x]);
// Iterate the childrens
for (int i : tree[x]) {
// All values of subtree
// i in sorted manner
if (i != p) {
ArrayList<Integer> tmp
= help(tree, i, x, c, sol);
res = merge(res, tmp);
}
}
int l = 0, r = res.size() - 1;
int ans = res.size();
// Binary search to find MEX
while (l <= r) {
// Find the mid
int mid = (l + r) / 2;
// Update the ranges
if (res.get(mid) > mid)
r = mid - 1;
else {
ans = mid + 1;
l = mid + 1;
}
}
if (res.get(0) != 0)
ans = 0;
// Update the MEX for the current
// tree node
sol[x] = ans;
return res;
}
// Function to find MEX of each
// subtree of tree
@SuppressWarnings("unchecked")
static void solve(int A, int[] C)
{
int n = A;
ArrayList<Integer>[] tree = new ArrayList[n + 1];
for (int i = 0; i <= n; i++)
tree[i] = new ArrayList<Integer>();
for (int[] i : edges) {
tree[i[0]].add(i[1]);
tree[i[1]].add(i[0]);
}
int[] sol = new int[n];
// Function Call
help(tree, 0, -1, C, sol);
// Print the ans for each nodes
for (int i : sol)
System.out.print(i + " ");
}
// Driver Code
public static void main(String[] args)
{
int N = 6;
add_edge(0, 1);
add_edge(1, 2);
add_edge(0, 3);
add_edge(3, 4);
add_edge(3, 5);
int[] val = { 4, 3, 5, 1, 0, 2 };
solve(N, val);
}
}
// This code is contributed by Lovely Jain
Javascript
<script>
// Javascript program for the above approach
// Stores the edges of the tree
let edges = [];
// Function to add edges
function add_edge(x, y) {
edges.push([x, y]);
}
// Function to merge two sorted vectors
function merge(a, b) {
// To store the result
let res = [];
let i = 0,
j = 0;
let n = a.length,
m = b.length;
// Iterating both vectors
while (i < n && j < m) {
if (a[i] < b[j]) res.push(a[i++]);
else if (b[j] < a[i]) res.push(b[j++]);
}
// Pushing remaining elements of
// vector a
while (i < n) res.push(a[i++]);
// Pushing remaining elements of
// vector b
while (j < m) res.push(b[j++]);
return res;
}
// Function to perform the DFS Traversal
// that returns the subtree of node
// in sorted manner
function help(tree, x, p, c, sol) {
let res = [];
res.push(c[x]);
// Iterate the childrens
for (let i of tree[x]) {
// All values of subtree
// i in sorted manner
if (i != p) {
let tmp = help(tree, i, x, c, sol);
res = merge(res, tmp);
}
}
let l = 0,
r = res.length - 1;
let ans = res.length;
// Binary search to find MEX
while (l <= r) {
// Find the mid
let mid = Math.floor((l + r) / 2);
// Update the ranges
if (res[mid] > mid) r = mid - 1;
else {
ans = mid + 1;
l = mid + 1;
}
}
if (res[0] != 0) ans = 0;
// Update the MEX for the current
// tree node
sol[x] = ans;
return res;
}
// Function to find MEX of each
// subtree of tree
function solve(A, C) {
let n = A;
let tree = new Array(n + 1).fill(0).map(() => []);
for (let i of edges) {
tree[i[0]].push(i[1]);
tree[i[1]].push(i[0]);
}
let sol = new Array(n).fill(0);
// Function Call
help(tree, 0, -1, C, sol);
// Print the ans for each nodes
for (let i of sol) document.write(i + " ");
}
// Driver Code
let N = 6;
add_edge(0, 1);
add_edge(1, 2);
add_edge(0, 3);
add_edge(3, 4);
add_edge(3, 5);
let val = [4, 3, 5, 1, 0, 2];
solve(N, val);
// This code is contributed by _saurabh_jaiswal.
</script>
6 0 0 3 1 0
Complejidad de tiempo: O(N*(N + log N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por animeshab99 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA