Dado un árbol que tiene N Nodes enraizados en el Node 0 y una array val[] que indica el valor en cada Node, la tarea es encontrar el producto máximo posible de XOR de componentes conectados después de eliminar un borde del árbol y también el borde que se elimina.
Nota: si hay varios bordes que dan el valor máximo, imprímalos todos en cualquier orden.
Ejemplos:
Entrada: bordes[][] = { {0, 5}, {0, 4}, {5, 1}, {5, 3}, {5, 2} }, val[ ] = { 7, 15, 9 , 1, 1, 12}
Salida: max_xor_product = 66
Aristas: {0, 5}
Explicación : si eliminamos una arista {0, 5} , el árbol se dividirá en dos componentes.
El XOR del primer componente es (1^7) = 6.
Y el XOR del segundo componente es ( 12^15^1^9) = 11.
El producto de xor de esos componentes es ( 6*11) = 66 Del mismo modo ,
si eliminamos una arista {5, 1}, el árbol vuelve a dividirse en dos componentes.
El XOR del primer componente es (15) (porque solo tiene un Node)
y el XOR del segundo componente es (7^1^12^9^1) = 2.
Y el producto de XOR de esos componentes es ( 15 * 2 ) = 30.
Si esto se repite el valor máximo del producto de XOR de componentes será 66,
que se puede conseguir si eliminamos la arista {0, 5}.Mira la imagen de abajo para entenderlo mejor
Entrada: bordes[][] = { {0, 1}, {0, 2}}, val[ ]={ 17, 17, 17}
Salida : max_xor_product = 0
Bordes: {{0, 1}, {0, 2}}
Enfoque ingenuo: elimine cada borde y recorra los componentes y tome xor de los valores de los Nodes en esos componentes, luego haga el producto de xor, almacene el valor máximo y el borde correspondiente a ese valor.
Complejidad temporal: O(N*N)
Espacio auxiliar: O(N)
Método eficiente: este problema se puede resolver precalculando el XOR del subárbol de cada Node y usando la propiedad XOR bit a bit de la siguiente manera:
Si se elimina un borde de un árbol, el árbol siempre se dividirá en dos componentes. El XOR de un componente será el mismo que el XOR del subárbol (digamos X) y el otro componente tendrá XOR = (XOR total de todos los Nodes ^ X).
Para cada borde, considere que se elimina y luego encuentre el XOR de ambos componentes (usando la observación anterior) y su producto. Mantenga un registro del máximo y elimine qué borde da como resultado eso.
Siga la ilustración que se muestra a continuación para una mejor comprensión.
Ilustración:
Considere el primer ejemplo dado a continuación
edge[][] = { {0, 5}, {0, 4}, {5, 1}, {5, 3}, {5, 2} }, val[ ] = { 7 , 15, 9, 1, 1, 12}Eliminar borde {0, 4} :
=> Dos componentes son {1} y {7, 12, 15, 1, 9}
=> Los valores XOR son 1 y 12
=> Producto = 1*12 = 12Eliminar borde {0, 5} :
=> Dos componentes son {1, 7} y {12, 15, 1, 9}
=> Los valores XOR son 6 y 11
=> Producto = 6*11 = 66Eliminar borde {5, 1} :
=> Dos componentes son {1, 7, 12, 1, 9} y {15}
=> Los valores XOR son 2 y 15
=> Producto = 2*15 = 30Eliminar borde {5, 2} :
=> Dos componentes son {1, 7, 12, 15, 1} y {9}
=> Los valores XOR son 4 y 9
=> Producto = 4*9 = 36Eliminar borde {5, 3} :
=> Dos componentes son {1, 7, 12, 15, 9} y {1}
=> Los valores XOR son 1 y 12
=> Producto = 1*12 = 12Entonces, el valor máximo es 66, que se logra cuando se elimina el borde {0, 5}
Siga los pasos a continuación para resolver este problema:
- Calcule el XOR de todos los valores dados de todos los Nodes del árbol (digamos tot_xor )
- Cree una array (digamos subtree_xor[] ) y almacene el xor bit a bit del subárbol del Node i mediante DFS .
- Ahora recorra el árbol usando DFS y para cada Node:
- Considere que se elimina el borde entre el Node actual y su padre .
- Los dos componentes serán: el Node actual con su subárbol y el resto del árbol.
- Calcule el xor bit a bit del Node actual con su subárbol y del árbol restante como se menciona en la observación anterior.
- Encuentre el producto de los valores XOR.
- Actualice el valor máximo y los bordes eliminados en consecuencia.
- Devuelve el valor máximo y los bordes eliminados.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
const int mxx = 1e6 + 7;
int subtree_xor[mxx];
unordered_map<long long,
vector<pair<int, int> > >
store;
// To add edges in tree
void addEdge(vector<int> tree[], int u, int v)
{
tree[u].push_back(v);
tree[v].push_back(u);
}
// To precompute xor value of each subtree
void dfs(vector<int> tree[], int val[],
int cur_node, int par)
{
// assign value of current node
subtree_xor[cur_node] = val[cur_node];
for (auto& child : tree[cur_node]) {
if (child == par)
continue;
dfs(tree, val, child, cur_node);
// take xor of all child node
subtree_xor[cur_node]
^= subtree_xor[child];
}
}
// To store all xor_product
// and it's corresponding edges
void store_xor_product(vector<int> tree[],
int cur_node,
int par, int tot_xor)
{
for (auto& child : tree[cur_node]) {
if (child == par)
continue;
// Xor of first component
int first_comp_xor
= subtree_xor[child];
// Xor of second component
int second_comp_xor
= tot_xor ^ first_comp_xor;
// Product can exceed int range
// so store it in long long data type
long long xor_product
= first_comp_xor * 1LL
* second_comp_xor;
// Store edges corresponding
// to its product
store[xor_product].push_back({ cur_node,
child });
store_xor_product(tree, child,
cur_node, tot_xor);
}
}
// To print edges corresponding
// to max_xor_product of components
void print_edges(long long mx_product)
{
for (auto edges : store[mx_product]) {
cout << edges.first << " "
<< edges.second << "\n";
}
}
// Driver code
int findVal(int N, int val[],
vector<vector<int> >& edges)
{
int tot_xor = 0;
// Store the xor of all values
for (int i = 0; i < N; i++)
tot_xor ^= val[i];
vector<int> tree[N];
// Create a tree from given edges
for (int i = 0; i < N - 1; i++)
addEdge(tree, edges[i][0],
edges[i][1]);
// Dfs travel to store subtree xor
dfs(tree, val, 0, -1);
// To store edges corresponding
// to xor_product
store_xor_product(tree, 0, -1, tot_xor);
// Find maximum xor_product
long long mx_product = -1;
for (auto ele : store) {
long long cur_product = ele.first;
mx_product
= max(mx_product, cur_product);
}
return mx_product;
}
// Driver code
int main()
{
int N = 6;
vector<vector<int> > edges = {
{ 0, 5 }, { 0, 4 }, { 5, 1 }, { 5, 3 }, { 5, 2 }
};
int val[] = { 7, 15, 9, 1, 1, 12 };
int mx_product = findVal(N, val, edges);
cout << mx_product << "\n";
// To print edges corresponding
// to maximum xor_product
print_edges(mx_product);
return 0;
}
Java
// Java code for the above approach:
import java.util.*;
public class Main {
static int mxx = 1000007;
static int subtree_xor[];
static HashMap <Long,
ArrayList <IntPair > > store;
static class IntPair {
int first;
int second;
IntPair(int x, int y) {
this.first = x;
this.second = y;
}
}
// To add edges in tree
static void addEdge(ArrayList <ArrayList <Integer>> tree, int u, int v)
{
tree.get(u).add(v);
tree.get(v).add(u);
}
// To precompute xor value of each subtree
static void dfs(ArrayList <ArrayList <Integer>> tree, int val[],
int cur_node, int par)
{
// assign value of current node
subtree_xor[cur_node] = val[cur_node];
for (Integer child : tree.get(cur_node)) {
if (child == par)
continue;
dfs(tree, val, child, cur_node);
// take xor of all child node
subtree_xor[cur_node]
^= subtree_xor[child];
}
}
// To store all xor_product
// and it's corresponding edges
static void store_xor_product(ArrayList <ArrayList <Integer>> tree,
int cur_node,
int par, int tot_xor)
{
for (Integer child : tree.get(cur_node)) {
if (child == par)
continue;
// Xor of first component
long first_comp_xor
= subtree_xor[child];
// Xor of second component
long second_comp_xor
= tot_xor ^ first_comp_xor;
// Product can exceed int range
// so store it in long long data type
long xor_product
= first_comp_xor * second_comp_xor;
// Store edges corresponding
// to its product
if( ! store.containsKey(xor_product) ){
store.put(xor_product,new ArrayList<IntPair> ());
}
store.get(xor_product).add(new IntPair(cur_node, child) );
store_xor_product(tree, child,
cur_node, tot_xor);
}
}
// To print edges corresponding
// to max_xor_product of components
static void print_edges(long mx_product)
{
if(store.containsKey(mx_product) ) {
for (IntPair edges : store.get(mx_product) ) {
System.out.println(edges.first + " "
+ edges.second );
}
}
}
static long findVal(int N, int val[],
int[][] edges)
{
int tot_xor = 0;
// Store the xor of all values
for (int i = 0; i < N; i++)
tot_xor ^= val[i];
ArrayList <ArrayList <Integer> > tree =
new ArrayList <ArrayList <Integer>> (N);
for(int i = 0; i < N; i++){
tree.add(new ArrayList <Integer>());
}
// Create a tree from given edges
for (int i = 0; i < N - 1; i++)
addEdge(tree, edges[i][0],
edges[i][1]);
// Dfs travel to store subtree xor
dfs(tree, val, 0, -1);
// To store edges corresponding
// to xor_product
store_xor_product(tree, 0, -1, tot_xor);
// Find maximum xor_product
long mx_product = -1;
for (HashMap.Entry < Long, ArrayList <IntPair> > ele : store.entrySet()) {
long cur_product = ele.getKey();
mx_product
= Math.max(mx_product, cur_product);
}
return mx_product;
}
// Driver Code
public static void main(String args[]) {
int N = 6;
int[][] edges = {
{ 0, 5 }, { 0, 4 }, { 5, 1 }, { 5, 3 }, { 5, 2 }
};
subtree_xor = new int[mxx];
store = new HashMap <Long, ArrayList <IntPair > > ();
int val[] = { 7, 15, 9, 1, 1, 12 };
long mx_product = findVal(N, val, edges);
System.out.println( mx_product);
// To print edges corresponding
// to maximum xor_product
print_edges(mx_product);
}
}
// This code is contributed by Sachin Sahara (sachin801)
66 0 5
Complejidad de Tiempo : O( N )
Espacio Auxiliar : O( N )
Publicación traducida automáticamente
Artículo escrito por patilnainesh911 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA