Dado un árbol con N Nodes y un número entero P , la tarea es eliminar los bordes en el rango [1, P) y encontrar el XOR de los Nodes para cada componente conectado formado. Si los valores de los Nodes resultan ser iguales para todos los componentes conectados formados, imprima «SÍ» de lo contrario «NO».
Ejemplos:
Entrada: N = 5, P = 5, Bordes[][]={ { 1, 2 }, { 2, 3 }, { 1, 4 }, { 4, 5 }}, Nodes[] = {2, 2 , 2, 2, 2}
Salida: SÍ
Explicación: Podemos eliminar todos los bordes, luego habrá 5 componentes conectados, cada uno con un Node con valor 2, por lo tanto, XOR de cada uno de ellos será 2.
Entrada: N = 5, P = 2, Bordes[][]={ { 1, 2 }, { 2, 3 }, { 1, 4 }, { 4, 5 }}, Nodes[] = {1, 6 , 4, 1, 2}
Salida: SÍ
Explicación: Como, p = 2, al menos un borde debe eliminarse, por lo que, al eliminar el borde (4, 5), se obtienen dos componentes conectados.
XOR del primer componente sería, arr 1 XOR arr 2 XOR arr 3 XOR arr 4 = 1 XOR 6 XOR 4 XOR 1 => 2.
XOR del segundo componente sería arr 5 = 2. (Así, ambos iguales).
Enfoque: El enfoque para resolver este problema se basa en las siguientes observaciones:
El hecho aquí es que la eliminación de bordes debe ser una o dos veces, como:
- Eliminar un borde nos da 2 componentes conectados, que deberían tener el mismo XOR y, por lo tanto, por las propiedades de xor si XOR1 == XOR2 , entonces XOR1 ^ XOR2 = 0 , donde ^ es el XOR bit a bit.
- De manera similar, si XOR de todo el árbol es 0, eliminando cualquier borde, dará 2 componentes conectados donde ambos componentes tendrían el mismo valor, por lo tanto, responda = «SÍ».
- Ahora, si eliminamos 2 bordes, eliminar más que eso solo fusionaría los otros componentes entre sí. Por ejemplo: si hay 4 o más componentes conectados, podemos reducirlos y fusionarlos, como para 4 se puede reducir a 2 componentes (que caerá en el caso si eliminamos 1 borde).
- Ahora, eliminar 2 aristas nos da un mínimo de 3 componentes conectados, usando propiedades de x o sabemos que XOR1 ^ XOR2 ^ XOR3 = digamos algún valor (y) , lo que significa que necesitamos encontrar tales subárboles (o digamos buscar 2 bordes a eliminar) cuyo XOR es igual a algún valor (y) , y si lo encontramos, respondemos = “SÍ” sino “NO”, tal que p>2 .
- Por ejemplo: digamos, si tenemos XOR total = algún valor (y) , con N = 4 , puede haber 3 segmentos cuyo XOR hubiera sido y , entonces los elementos totales podrían obtener XOR = y, tal que p > 2.
Entonces, en general, se puede decir que si encontramos dos subárboles cuyo XOR = y , y si nuestro XOR total fuera y , podemos decir que nuestro componente/segmento XOR excluido también sería y , por lo tanto, responda = «SÍ», tal que p > 2 , usando la propiedad anterior XOR1 ^ XOR2 ^ XOR3 = algún valor (y) ,
Siga los pasos a continuación para aplicar el enfoque anterior:
Para encontrar dichos subárboles, con un mínimo de 3 componentes conectados, se puede hacer fácilmente usando DFS transversal y durante el retroceso, almacenaremos cada índice XOR en cada iteración.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for Check after removing
// edges bitwise XOR of each connected
// component formed is equal
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
// adjacency list to form a tree
vector<int> adj[N];
// array arr defined to store node values
// array cal_XOR defined to store
// xor values rooted at i'th level
int nodes[N], cal_XOR[N];
// defined a visited array
vector<bool> visited(N);
// defined a counter to store
// number of subtrees having value equal
// to whole tree XOR
int counter = 0;
// first dfs function to find
// xor of subtrees
int dfs_First(int x)
{
// initializing cal_XOR
// array with tree node's value
cal_XOR[x] = nodes[x];
// marking each visited node as true
visited[x] = true;
// iterating through current node children
for (auto y : adj[x]) {
// check if node->child is not visited
if (!visited[y]) {
// computing xor of subtree rooted at x
cal_XOR[x] ^= dfs_First(y);
}
}
// returning xor of subtree rooted at x
return cal_XOR[x];
}
// second dfs function to count
// subtrees having values equal
// to entire XOR of tree nodes values
// and returning subtree XOR till that point
int dfs_Second(int x)
{
// marking each visited node as true
visited[x] = true;
// storing value of nodes[x]
// to another variable temp
// for further calculation
int temp = nodes[x];
// iterating through current node children
for (auto y : adj[x]) {
// check if node->child is not visited
if (!visited[y]) {
// storing xor of subtree
temp ^= dfs_Second(y);
}
}
// now, checking if xor of subtree
// computed till now is equal to
// entire XOR of tree (root)
// i.e. value at cal_XOR[0] ->
// which will give entire XOR of the tree
if (temp == cal_XOR[0]) {
// then, make that xor 0
temp = 0;
// increase count by 1, which
// means we found a subtree
counter++;
}
// return xor of subtree
// till that point
return temp;
}
// Function to add edges
void addEdge(int u, int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
// Function to take input
// for (n-1) edges
void init(int edges[4][2], int numEdges)
{
for (int i = 0; i < numEdges; i++) {
edges[i][0]--;
edges[i][1]--;
addEdge(edges[i][0], edges[i][1]);
}
}
// Driver Code
int main()
{
// taking input
int n = 5, p = 2;
nodes[0] = 1, nodes[1] = 6, nodes[2] = 4,
nodes[3] = 1, nodes[4] = 2;
// making our visited array false
for (int i = 0; i < n; i++) {
visited[i] = false;
}
// taking input for (n-1) edges
int edges[4][2]
= { { 1, 2 }, { 2, 3 }, { 1, 4 }, { 4, 5 } };
init(edges, 4);
// First dfs Function call
dfs_First(0);
// again, marking visited array to false
for (int i = 0; i < n; i++) {
visited[i] = false;
}
// initializing answer variable
bool answer = false;
// if we found XOR of entire tree
// equal to zero, answer = "YES", as
// it means there are two connected
// components equal to each other
// thus, a single edge can be removed
if (cal_XOR[0] == 0) {
answer = true;
}
else {
// second DFS function call
dfs_Second(0);
// if we found 2 subtree having
// equal value with XOR of entire tree
// answer is always "YES", such that
// p > 2
if (counter >= 2 and p != 2) {
answer = true;
}
}
// printing the final answer
if (answer == true) {
cout << "YES"
<< "\n";
}
else {
cout << "NO"
<< "\n";
}
// making counter = 0 for next iteration
counter = 0;
for (int i = 0; i < n; i++) {
// similarly clearing adjacency list
// and both arr and cal_XOR array
adj[i].clear();
cal_XOR[i] = nodes[i] = 0;
}
}
Java
// Java code for Check after removing
// edges bitwise XOR of each connected
// component formed is equal
import java.util.*;
public class GFG {
static int N = 100000;
// adjacency list to form a tree
static ArrayList<ArrayList<Integer> > adj
= new ArrayList<>();
// array arr defined to store node values
// array cal_XOR defined to store
// xor values rooted at i'th level
static int[] nodes = new int[N];
static int[] cal_XOR = new int[N];
// defined a visited array
static boolean[] visited = new boolean[N];
// defined a counter to store
// number of subtrees having value equal
// to whole tree XOR
static int counter = 0;
// first dfs function to find
// xor of subtrees
static int dfs_First(int x)
{
// initializing cal_XOR
// array with tree node's value
cal_XOR[x] = nodes[x];
// marking each visited node as true
visited[x] = true;
// iterating through current node children
for (Integer y : adj.get(x))
{
// check if node->child is not visited
if (!visited[y])
{
// computing xor of subtree rooted at x
cal_XOR[x] ^= dfs_First(y);
}
}
// returning xor of subtree rooted at x
return cal_XOR[x];
}
// second dfs function to count
// subtrees having values equal
// to entire XOR of tree nodes values
// and returning subtree XOR till that point
static int dfs_Second(int x)
{
// marking each visited node as true
visited[x] = true;
// storing value of nodes[x]
// to another variable temp
// for further calculation
int temp = nodes[x];
// iterating through current node children
for (Integer y : adj.get(x)) {
// check if node->child is not visited
if (!visited[y]) {
// storing xor of subtree
temp ^= dfs_Second(y);
}
}
// now, checking if xor of subtree
// computed till now is equal to
// entire XOR of tree (root)
// i.e. value at cal_XOR[0] ->
// which will give entire XOR of the tree
if (temp == cal_XOR[0])
{
// then, make that xor 0
temp = 0;
// increase count by 1, which
// means we found a subtree
counter++;
}
// return xor of subtree
// till that point
return temp;
}
// Function to add edges
static void addEdge(int u, int v)
{
adj.get(u).add(v);
adj.get(v).add(u);
}
// Function to take input
// for (n-1) edges
static void init(int[][] edges, int numEdges)
{
for (int i = 0; i < numEdges; i++) {
edges[i][0]--;
edges[i][1]--;
addEdge(edges[i][0], edges[i][1]);
}
}
// Driver Code
public static void main(String[] args)
{
// taking input
int n = 5, p = 2;
nodes[0] = 1;
nodes[1] = 6;
nodes[2] = 4;
nodes[3] = 1;
nodes[4] = 2;
for (int i = 0; i < n; i++) {
adj.add(new ArrayList<>());
}
// taking input for (n-1) edges
int[][] edges
= { { 1, 2 }, { 2, 3 }, { 1, 4 }, { 4, 5 } };
init(edges, 4);
// First dfs Function call
dfs_First(0);
// again, marking visited array to false
for (int i = 0; i < n; i++) {
visited[i] = false;
}
// initializing answer variable
boolean answer = false;
// if we found XOR of entire tree
// equal to zero, answer = "YES", as
// it means there are two connected
// components equal to each other
// thus, a single edge can be removed
if (cal_XOR[0] == 0) {
answer = true;
}
else {
// second DFS function call
dfs_Second(0);
// if we found 2 subtree having
// equal value with XOR of entire tree
// answer is always "YES", such that
// p > 2
if (counter >= 2 && p != 2) {
answer = true;
}
}
// printing the final answer
if (answer == true) {
System.out.println("YES");
}
else {
System.out.println("NO");
}
// making counter = 0 for next iteration
counter = 0;
for (int i = 0; i < n; i++) {
// similarly clearing adjacency list
// and both arr and cal_XOR array
adj.get(i).clear();
cal_XOR[i] = nodes[i] = 0;
}
}
}
// This code is contributed by karandeep1234.
Python3
# python3 code for Check after removing
# edges bitwise XOR of each connected
# component formed is equal
N = int(1e5)
# adjacency list to form a tree
adj = [[] for _ in range(N)]
# array arr defined to store node values
# array cal_XOR defined to store
# xor values rooted at i'th level
nodes, cal_XOR = [0 for _ in range(N)], [0 for _ in range(N)]
# defined a visited array
visited = [0 for _ in range(N)]
# defined a counter to store
# number of subtrees having value equal
# to whole tree XOR
counter = 0
# first dfs function to find
# xor of subtrees
def dfs_First(x):
global N, adj, nodes, cal_XOR, visited, counter
# initializing cal_XOR
# array with tree node's value
cal_XOR[x] = nodes[x]
# marking each visited node as true
visited[x] = True
# iterating through current node children
for y in adj[x]:
# check if node->child is not visited
if (not visited[y]):
# computing xor of subtree rooted at x
cal_XOR[x] ^= dfs_First(y)
# returning xor of subtree rooted at x
return cal_XOR[x]
# second dfs function to count
# subtrees having values equal
# to entire XOR of tree nodes values
# and returning subtree XOR till that point
def dfs_Second(x):
global N, adj, nodes, cal_XOR, visited, counter
# marking each visited node as true
visited[x] = True
# storing value of nodes[x]
# to another variable temp
# for further calculation
temp = nodes[x]
# iterating through current node children
for y in adj[x]:
# check if node->child is not visited
if (not visited[y]):
# storing xor of subtree
temp ^= dfs_Second(y)
# now, checking if xor of subtree
# computed till now is equal to
# entire XOR of tree (root)
# i.e. value at cal_XOR[0] ->
# which will give entire XOR of the tree
if (temp == cal_XOR[0]):
# then, make that xor 0
temp = 0
# increase count by 1, which
# means we found a subtree
counter += 1
# return xor of subtree
# till that point
return temp
# Function to add edges
def addEdge(u, v):
global N, adj, nodes, cal_XOR, visited, counter
adj[u].append(v)
adj[v].append(u)
# Function to take input
# for (n-1) edges
def init(edges, numEdges):
global N, adj, nodes, cal_XOR, visited, counter
for i in range(0, numEdges):
edges[i][0] -= 1
edges[i][1] -= 1
addEdge(edges[i][0], edges[i][1])
# Driver Code
if __name__ == "__main__":
# taking input
n, p = 5, 2
nodes[0], nodes[1], nodes[2] = 1, 6, 4
nodes[3], nodes[4] = 1, 2
# making our visited array false
for i in range(0, n):
visited[i] = False
# taking input for (n-1) edges
edges = [[1, 2], [2, 3], [1, 4], [4, 5]]
init(edges, 4)
# First dfs Function call
dfs_First(0)
# again, marking visited array to false
for i in range(0, n):
visited[i] = False
# initializing answer variable
answer = False
# if we found XOR of entire tree
# equal to zero, answer = "YES", as
# it means there are two connected
# components equal to each other
# thus, a single edge can be removed
if (cal_XOR[0] == 0):
answer = True
else:
# second DFS function call
dfs_Second(0)
# if we found 2 subtree having
# equal value with XOR of entire tree
# answer is always "YES", such that
# p > 2
if (counter >= 2 and p != 2):
answer = True
# printing the final answer
if (answer == True):
print("YES")
else:
print("NO")
# making counter = 0 for next iteration
counter = 0
for i in range(0, n):
# similarly clearing adjacency list
# and both arr and cal_XOR array
adj[i] = []
cal_XOR[i] = nodes[i] = 0
# This code is contributed by rakeshsahni
Javascript
<script>
// JavaScript code for the above approach
let N = 1e5;
// adjacency list to form a tree
let adj = new Array(N);
for (let i = 0; i < N; i++) {
adj[i] = [];
}
// array arr defined to store node values
// array cal_XOR defined to store
// xor values rooted at i'th level
let nodes = new Array(N), cal_XOR = new Array(N);
// defined a visited array
let visited = new Array(N).fill(false);
// defined a counter to store
// number of subtrees having value equal
// to whole tree XOR
let counter = 0;
// first dfs function to find
// xor of subtrees
function dfs_First(x)
{
// initializing cal_XOR
// array with tree node's value
cal_XOR[x] = nodes[x];
// marking each visited node as true
visited[x] = true;
// iterating through current node children
for (let y of adj[x])
{
// check if node->child is not visited
if (!visited[y])
{
// computing xor of subtree rooted at x
cal_XOR[x] ^= dfs_First(y);
}
}
// returning xor of subtree rooted at x
return cal_XOR[x];
}
// second dfs function to count
// subtrees having values equal
// to entire XOR of tree nodes values
// and returning subtree XOR till that point
function dfs_Second(x) {
// marking each visited node as true
visited[x] = true;
// storing value of nodes[x]
// to another variable temp
// for further calculation
let temp = nodes[x];
// iterating through current node children
for (let y of adj[x]) {
// check if node->child is not visited
if (!visited[y]) {
// storing xor of subtree
temp ^= dfs_Second(y);
}
}
// now, checking if xor of subtree
// computed till now is equal to
// entire XOR of tree (root)
// i.e. value at cal_XOR[0] ->
// which will give entire XOR of the tree
if (temp == cal_XOR[0]) {
// then, make that xor 0
temp = 0;
// increase count by 1, which
// means we found a subtree
counter++;
}
// return xor of subtree
// till that point
return temp;
}
// Function to add edges
function addEdge(u, v) {
adj[u].push(v);
adj[v].push(u);
}
// Function to take input
// for (n-1) edges
function init(edges, numEdges) {
for (let i = 0; i < numEdges; i++) {
edges[i][0]--;
edges[i][1]--;
addEdge(edges[i][0], edges[i][1]);
}
}
// Driver Code
// taking input
let n = 5, p = 2;
nodes[0] = 1, nodes[1] = 6, nodes[2] = 4,
nodes[3] = 1, nodes[4] = 2;
// making our visited array false
for (let i = 0; i < n; i++) {
visited[i] = false;
}
// taking input for (n-1) edges
let edges =
[[1, 2], [2, 3], [1, 4], [4, 5]];
init(edges, 4);
// First dfs Function call
dfs_First(0);
// again, marking visited array to false
for (let i = 0; i < n; i++) {
visited[i] = false;
}
// initializing answer variable
let answer = false;
// if we found XOR of entire tree
// equal to zero, answer = "YES", as
// it means there are two connected
// components equal to each other
// thus, a single edge can be removed
if (cal_XOR[0] == 0) {
answer = true;
}
else {
// second DFS function call
dfs_Second(0);
// if we found 2 subtree having
// equal value with XOR of entire tree
// answer is always "YES", such that
// p > 2
if (counter >= 2 && p != 2) {
answer = true;
}
}
// printing the final answer
if (answer == true) {
document.write("YES" + '<br>')
}
else {
document.write("NO" + '<br>')
}
// making counter = 0 for next iteration
counter = 0;
for (let i = 0; i < n; i++) {
// similarly clearing adjacency list
// and both arr and cal_XOR array
adj[i] = [];
cal_XOR[i] = nodes[i] = 0;
}
// This code is contributed by Potta Lokesh
</script>
Producción
YES
Complejidad de tiempo: O(N+E), donde N= número de Nodes y E = número de aristas
Espacio auxiliar: O(N+E), donde N= número de Nodes y E = número de aristas
Publicación traducida automáticamente
Artículo escrito por singhh3010 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA