Dado un árbol de N Nodes, la tarea es convertir el árbol dado en su Árbol de suma (incluido su propio peso) y encontrar la diferencia mínima entre el peso de dos Nodes cualquiera del árbol de suma.
Nota: Los N Nodes del árbol dado se dan en forma de arriba hacia abajo con N-1 línea donde cada línea describe dos Nodes que están conectados.
Ejemplos:
Aporte:
Salida: 1
Explicación:
peso total del Node 1: 3 (peso propio) + (10 + 6 + 5 + 8 + 2 + 7 + 11) (peso del Node del subárbol) = 52
Peso total del Node 2: 5 (peso propio ) peso) + (2 + 7 + 11) (peso del Node del subárbol) = 25
peso total del Node 3: 8 (peso propio) + (0) (peso del Node del subárbol) = 8
peso total del Node 4: 10 (peso propio) + (0) (peso del Node del subárbol) = 10
peso total del Node 5: 2 (peso propio) + (0) (peso del Node del subárbol) = 2
peso total del Node 6: 6 (peso propio ) peso) + (5 + 8 + 2 + 7 + 11) (peso del Node del subárbol) = 39
peso total del Node 7: 7 (peso propio) + (0) (peso del Node del subárbol) = 7
peso total del Node Node 8: 11 (peso propio) + (0) (peso del Node del subárbol) = 11
Al observar el peso total de cada Node, el Node 4 y el 8 tienen una diferencia mínima (11-10) = 1Aporte:
Salida: 0
Acercarse:
- Atravesaremos el árbol dado desde abajo y almacenaremos el peso de ese Node más el peso del Node del subárbol en una array y marcaremos el índice de cada Node como visitado. Entonces, en el medio, si volvemos a visitar ese Node, entonces no tenemos que contar el peso de ese Node nuevamente.
- Ordenaremos la array donde hemos almacenado el peso total de cada Node.
- Ahora encuentre la diferencia por pares en la array ordenada y el par que dio la diferencia mínima imprima esa diferencia mínima al final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find minimum
// difference between any two node
void MinimumDifference(int total_weight[],
int N)
{
int min_difference = INT_MAX;
for (int i = 1; i < N; i++) {
// Pairwise difference
if (total_weight[i]
- total_weight[i - 1]
< min_difference) {
min_difference
= total_weight[i]
- total_weight[i - 1];
}
}
cout << min_difference << endl;
}
// Function to find total weight
// of each individual node
void SumTree(vector<pair<int, int> > v,
int individual_weight[],
int N)
{
// Array to store total weight
// of each node from 1 to N
int total_weight[N] = { 0 };
// Array to keep track of node
// previously counted or not
int visited[N] = { 0 };
// To store node no. from
/// N-1 lines
int first, second;
// To traverse from (N-1)
// line to 1 line
for (int i = (N - 2); i >= 0; i--) {
first = v[i].first;
second = v[i].second;
// Node is note visited
if (visited[second - 1] == 0) {
total_weight[second - 1]
+= individual_weight[second - 1];
// Make node visited
visited[second - 1] = 1;
}
total_weight[first - 1]
+= total_weight[second - 1];
// Node is note visited
if (visited[first - 1] == 0) {
total_weight[first - 1]
+= individual_weight[first - 1];
// Make node visited
visited[first - 1] = 1;
}
}
// Sort the total weight of each node
sort(total_weight, total_weight + N);
// Call function to find minimum
// difference
MinimumDifference(total_weight, N);
}
// Driver code
int main()
{
// Total node of rooted tree
int N = 8;
vector<pair<int, int> > v;
// N-1 lines describing
// rooted tree from top
// to bottom
v.push_back(make_pair(1, 4));
v.push_back(make_pair(1, 6));
v.push_back(make_pair(6, 2));
v.push_back(make_pair(6, 3));
v.push_back(make_pair(2, 5));
v.push_back(make_pair(2, 7));
v.push_back(make_pair(2, 8));
// Array describing weight
// of each node from 1 to N
int individual_weight[N] = { 3, 5, 8, 10,
2, 6, 7, 11 };
SumTree(v, individual_weight, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to find minimum
// difference between any two node
static void MinimumDifference(int total_weight[],
int N)
{
int min_difference = Integer.MAX_VALUE;
for(int i = 1; i < N; i++)
{
// Pairwise difference
if (total_weight[i] -
total_weight[i - 1] <
min_difference)
{
min_difference = total_weight[i] -
total_weight[i - 1];
}
}
System.out.print(min_difference + "\n");
}
// Function to find total weight
// of each individual node
static void SumTree(Vector<pair> v,
int individual_weight[],
int N)
{
// Array to store total weight
// of each node from 1 to N
int total_weight[] = new int[N];
// Array to keep track of node
// previously counted or not
int visited[] = new int[N];
// To store node no. from
/// N-1 lines
int first, second;
// To traverse from (N-1)
// line to 1 line
for(int i = (N - 2); i >= 0; i--)
{
first = v.get(i).first;
second = v.get(i).second;
// Node is note visited
if (visited[second - 1] == 0)
{
total_weight[second - 1] +=
individual_weight[second - 1];
// Make node visited
visited[second - 1] = 1;
}
total_weight[first - 1] +=
total_weight[second - 1];
// Node is note visited
if (visited[first - 1] == 0)
{
total_weight[first - 1] +=
individual_weight[first - 1];
// Make node visited
visited[first - 1] = 1;
}
}
// Sort the total weight of each node
Arrays.sort(total_weight);
// Call function to find minimum
// difference
MinimumDifference(total_weight, N);
}
// Driver code
public static void main(String[] args)
{
// Total node of rooted tree
int N = 8;
Vector<pair> v = new Vector<>();
// N-1 lines describing
// rooted tree from top
// to bottom
v.add(new pair(1, 4));
v.add(new pair(1, 6));
v.add(new pair(6, 2));
v.add(new pair(6, 3));
v.add(new pair(2, 5));
v.add(new pair(2, 7));
v.add(new pair(2, 8));
// Array describing weight
// of each node from 1 to N
int individual_weight[] = { 3, 5, 8, 10,
2, 6, 7, 11 };
SumTree(v, individual_weight, N);
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program for the above approach import sys # Function to find minimum difference # between any two node def minimum_difference(total_weight, n): min_difference = sys.maxsize for i in range(1, n): # Pairwise difference if (total_weight[i] - total_weight[i - 1] < min_difference): min_difference = (total_weight[i] - total_weight[i - 1]) print(min_difference) # Function to find total weight # of each individual node def SumTree(v, individual_weight, N): # Array to store total weight of # each node from 1 to n total_weight = [0 for i in range(N)] # Array to keep track of node # previously counted or not visited = [0 for i in range(N)] # To traverse from (n-1) line to 1 line for i in range(N - 2, -1, -1): first = v[i][0] second = v[i][1] if visited[second - 1] == 0: total_weight[second - 1] += ( individual_weight[second - 1]) # Make node visited visited[second - 1] = 1 total_weight[first - 1] += ( total_weight[second - 1]) # Node is note visited if visited[first - 1] == 0: total_weight[first - 1] += ( individual_weight[first - 1]) # Make node visited visited[first - 1] = 1 # Sort the total weight of each node total_weight.sort() # Call function to find minimum difference minimum_difference(total_weight, n) # Driver Code if __name__=='__main__': # Total node of rooted tree n = 8 v = [] # n-1 lines describing rooted # tree from top to bottom v.append([1, 4]) v.append([1, 6]) v.append([6, 2]) v.append([6, 3]) v.append([2, 5]) v.append([2, 7]) v.append([2, 8]) # Array describing weight of each # node from 1 to n individual_weight = [ 3, 5, 8, 10, 2, 6, 7, 11 ] SumTree(v, individual_weight, n) # This code is contributed by rutvik_56
C#
// C# program for the
// above approach
using System;
using System.Collections.Generic;
class GFG{
class pair
{
public int first,
second;
public pair(int first,
int second)
{
this.first = first;
this.second = second;
}
}
// Function to find minimum
// difference between any two node
static void MinimumDifference(int []total_weight,
int N)
{
int min_difference = int.MaxValue;
for(int i = 1; i < N; i++)
{
// Pairwise difference
if (total_weight[i] -
total_weight[i - 1] <
min_difference)
{
min_difference = total_weight[i] -
total_weight[i - 1];
}
}
Console.Write(min_difference + "\n");
}
// Function to find total weight
// of each individual node
static void SumTree(List<pair> v,
int []individual_weight,
int N)
{
// Array to store total weight
// of each node from 1 to N
int []total_weight = new int[N];
// Array to keep track of node
// previously counted or not
int []visited = new int[N];
// To store node no. from
/// N-1 lines
int first, second;
// To traverse from (N-1)
// line to 1 line
for(int i = (N - 2); i >= 0; i--)
{
first = v[i].first;
second = v[i].second;
// Node is note visited
if (visited[second - 1] == 0)
{
total_weight[second - 1] +=
individual_weight[second - 1];
// Make node visited
visited[second - 1] = 1;
}
total_weight[first - 1] +=
total_weight[second - 1];
// Node is note visited
if (visited[first - 1] == 0)
{
total_weight[first - 1] +=
individual_weight[first - 1];
// Make node visited
visited[first - 1] = 1;
}
}
// Sort the total weight
// of each node
Array.Sort(total_weight);
// Call function to find minimum
// difference
MinimumDifference(total_weight, N);
}
// Driver code
public static void Main(String[] args)
{
// Total node of rooted tree
int N = 8;
List<pair> v = new List<pair>();
// N-1 lines describing
// rooted tree from top
// to bottom
v.Add(new pair(1, 4));
v.Add(new pair(1, 6));
v.Add(new pair(6, 2));
v.Add(new pair(6, 3));
v.Add(new pair(2, 5));
v.Add(new pair(2, 7));
v.Add(new pair(2, 8));
// Array describing weight
// of each node from 1 to N
int []individual_weight = {3, 5, 8, 10,
2, 6, 7, 11};
SumTree(v, individual_weight, N);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program for the above approach
// Function to find minimum
// difference between any two node
function MinimumDifference(total_weight, N)
{
let min_difference = Number.MAX_VALUE;
for (let i = 1; i < N; i++) {
// Pairwise difference
if (total_weight[i]
- total_weight[i - 1]
< min_difference) {
min_difference
= total_weight[i]
- total_weight[i - 1];
}
}
document.write(min_difference + "</br>");
}
// Function to find total weight
// of each individual node
function SumTree(v, individual_weight, N)
{
// Array to store total weight
// of each node from 1 to N
let total_weight = new Array(N);
total_weight.fill(0);
// Array to keep track of node
// previously counted or not
let visited = new Array(N);
visited.fill(0);
// To store node no. from
/// N-1 lines
let first, second;
// To traverse from (N-1)
// line to 1 line
for (let i = (N - 2); i >= 0; i--) {
first = v[i][0];
second = v[i][1];
// Node is note visited
if (visited[second - 1] == 0) {
total_weight[second - 1]
+= individual_weight[second - 1];
// Make node visited
visited[second - 1] = 1;
}
total_weight[first - 1]
+= total_weight[second - 1];
// Node is note visited
if (visited[first - 1] == 0) {
total_weight[first - 1]
+= individual_weight[first - 1];
// Make node visited
visited[first - 1] = 1;
}
}
// Sort the total weight of each node
total_weight.sort(function(a, b){return a - b});
// Call function to find minimum
// difference
MinimumDifference(total_weight, N);
}
// Total node of rooted tree
let N = 8;
let v = [];
// N-1 lines describing
// rooted tree from top
// to bottom
v.push([1, 4]);
v.push([1, 6]);
v.push([6, 2]);
v.push([6, 3]);
v.push([2, 5]);
v.push([2, 7]);
v.push([2, 8]);
// Array describing weight
// of each node from 1 to N
let individual_weight = [ 3, 5, 8, 10, 2, 6, 7, 11 ];
SumTree(v, individual_weight, N);
// This code is contributed by decode2207.
</script>
Producción:
1
Complejidad de tiempo: O(N * Log(N)) , donde N es el total de Nodes en el árbol enraizado.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por divyeshrabadiya07 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA