Dado un árbol y los pesos de todos los Nodes, la tarea es encontrar la raíz del subárbol cuya suma ponderada XOR con el entero X dado es mínima.
Ejemplos:
Aporte:
X = 15
Salida: 5
Peso del subárbol para padre 1 = ((-1) + (5) + (-2) + (-1) + (3)) XOR 15 = 4 XOR 15 = 11
Peso del sub -árbol para padre 2 = ((5) + (-1) + (3)) XOR 15 = 7 XOR 15 = 8
Peso del subárbol para padre 3 = -1 XOR 15 = -16
Peso del subárbol para padre 4 = 3 XOR 15 = 12
Peso del subárbol para el padre 5 = -2 XOR 15 = -15
El Node 3 proporciona la suma ponderada mínima del subárbol XOR X.
Enfoque: Realice dfs en el árbol y, para cada Node, calcule la suma ponderada del subárbol enraizada en el Node actual, luego encuentre el valor mínimo (suma XOR X) para un Node.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
int ans = 0, mini = INT_MAX;
vector<int> graph[100];
vector<int> weight(100);
// Function to perform dfs and update the tree
// such that every node's weight is the sum of
// the weights of all the nodes in the sub-tree
// of the current node including itself
void dfs(int node, int parent)
{
for (int to : graph[node]) {
if (to == parent)
continue;
dfs(to, node);
// Calculating the weighted
// sum of the subtree
weight[node] += weight[to];
}
}
// Function to find the node
// having minimum sub-tree sum XOR x
void findMinX(int n, int x)
{
// For every node
for (int i = 1; i <= n; i++) {
// If current node's weight XOR x
// is minimum so far
if (mini > (weight[i] ^ x)) {
mini = (weight[i] ^ x);
ans = i;
}
}
}
// Driver code
int main()
{
int x = 15;
int n = 5;
// Weights of the node
weight[1] = -1;
weight[2] = 5;
weight[3] = -1;
weight[4] = 3;
weight[5] = -2;
// Edges of the tree
graph[1].push_back(2);
graph[2].push_back(3);
graph[2].push_back(4);
graph[1].push_back(5);
dfs(1, 1);
findMinX(n, x);
cout << ans;
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
static int ans = 0, mini = Integer.MAX_VALUE;
static Vector<Integer>[] graph = new Vector[100];
static Integer[] weight = new Integer[100];
// Function to perform dfs and update the tree
// such that every node's weight is the sum of
// the weights of all the nodes in the sub-tree
// of the current node including itself
static void dfs(int node, int parent)
{
for (int to : graph[node])
{
if (to == parent)
continue;
dfs(to, node);
// Calculating the weighted
// sum of the subtree
weight[node] += weight[to];
}
}
// Function to find the node
// having minimum sub-tree sum XOR x
static void findMinX(int n, int x)
{
// For every node
for (int i = 1; i <= n; i++)
{
// If current node's weight XOR x
// is minimum so far
if (mini > (weight[i] ^ x))
{
mini = (weight[i] ^ x);
ans = i;
}
}
}
// Driver code
public static void main(String[] args)
{
int x = 15;
int n = 5;
for (int i = 0; i < 100; i++)
graph[i] = new Vector<Integer>();
// Weights of the node
weight[1] = -1;
weight[2] = 5;
weight[3] = -1;
weight[4] = 3;
weight[5] = -2;
// Edges of the tree
graph[1].add(2);
graph[2].add(3);
graph[2].add(4);
graph[1].add(5);
dfs(1, 1);
findMinX(n, x);
System.out.print(ans);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach ans = 0 mini = 2**32 graph = [[] for i in range(100)] weight = [0] * 100 # Function to perform dfs and update the tree # such that every node's weight is the sum of # the weights of all the nodes in the sub-tree # of the current node including itself def dfs(node, parent): global ans, mini, graph, weight, x for to in graph[node]: if (to == parent): continue dfs(to, node) # Calculating the weighted # sum of the subtree weight[node] += weight[to] # Function to find the node # having minimum sub-tree sum XOR x def findMinX(n, x): global ans, mini,graph,weight # For every node for i in range(1, n + 1): # If current node's weight XOR x # is minimum so far if (mini > (weight[i] ^ x)): mini = (weight[i] ^ x) ans = i # Driver code x = 15 n = 5 # Weights of the node weight[1] = -1 weight[2] = 5 weight[3] = -1 weight[4] = 3 weight[5] = -2 # Edges of the tree graph[1].append(2) graph[2].append(3) graph[2].append(4) graph[1].append(5) dfs(1, 1) findMinX(n, x) print(ans) # This code is contributed by SHUBHAMSINGH10
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
static int ans = 0, mini = int.MaxValue;
static List<int>[] graph = new List<int>[100];
static int[] weight = new int[100];
// Function to perform dfs and update the tree
// such that every node's weight is the sum of
// the weights of all the nodes in the sub-tree
// of the current node including itself
static void dfs(int node, int parent)
{
foreach (int to in graph[node])
{
if (to == parent)
continue;
dfs(to, node);
// Calculating the weighted
// sum of the subtree
weight[node] += weight[to];
}
}
// Function to find the node
// having minimum sub-tree sum XOR x
static void findMinX(int n, int x)
{
// For every node
for (int i = 1; i <= n; i++)
{
// If current node's weight XOR x
// is minimum so far
if (mini > (weight[i] ^ x))
{
mini = (weight[i] ^ x);
ans = i;
}
}
}
// Driver code
public static void Main(String[] args)
{
int x = 15;
int n = 5;
for (int i = 0; i < 100; i++)
graph[i] = new List<int>();
// Weights of the node
weight[1] = -1;
weight[2] = 5;
weight[3] = -1;
weight[4] = 3;
weight[5] = -2;
// Edges of the tree
graph[1].Add(2);
graph[2].Add(3);
graph[2].Add(4);
graph[1].Add(5);
dfs(1, 1);
findMinX(n, x);
Console.Write(ans);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript implementation of the approach
let ans = 0, mini = Number.MAX_VALUE;
let graph=new Array(100);
let weight = new Array(100);
for(let i=0;i<100;i++)
{
graph[i]=[];
weight[i]=0;
}
// Function to perform dfs and update the tree
// such that every node's weight is the sum of
// the weights of all the nodes in the sub-tree
// of the current node including itself
function dfs(node,parent)
{
for (let to=0;to<graph[node].length;to++)
{
if (graph[node][to] == parent)
continue;
dfs(graph[node][to], node);
// Calculating the weighted
// sum of the subtree
weight[node] += weight[to];
}
}
// Function to find the node
// having minimum sub-tree sum XOR x
function findMinX(n,X)
{
// For every node
for (let i = 1; i <= n; i++)
{
// If current node's weight XOR x
// is minimum so far
if (mini > (weight[i] ^ x))
{
mini = (weight[i] ^ x);
ans = i;
}
}
}
// Driver code
let x = 15;
let n = 5;
// Weights of the node
weight[1] = -1;
weight[2] = 5;
weight[3] = -1;
weight[4] = 3;
weight[5] = -2;
// Edges of the tree
graph[1].push(2);
graph[2].push(3);
graph[2].push(4);
graph[1].push(5);
dfs(1, 1);
findMinX(n, x);
document.write(ans);
// This code is contributed by unknown2108
</script>
Producción:
3
Análisis de Complejidad:
- Complejidad temporal: O(N).
En dfs, cada Node del árbol se procesa una vez y, por lo tanto, la complejidad debida a dfs es O(N) si hay un total de N Nodes en el árbol. Por lo tanto, la complejidad del tiempo es O(N). - Espacio Auxiliar : O(n).
El espacio de la pila de recursividad puede ser de hasta O(n).
Publicación traducida automáticamente
Artículo escrito por mohit kumar 29 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA