Encuentre la raíz del subárbol cuya suma ponderada XOR con X es mínima

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:
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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *