Dado un árbol binario con N Nodes valorados de 0 a N – 1 y N-1 aristas y una array arr[] que consiste en valores de aristas, la tarea es encontrar el costo máximo de dividir el árbol en dos mitades.
El costo de dividir un árbol es igual al producto de la suma de los valores de los Nodes de los subárboles divididos.
Ejemplos:
Entrada: N = 6, arr[] = {13, 8, 7, 4, 5, 9}, Edges[][] = {{0, 1}, {1, 2}, {1, 4}, { 3, 4}, {4, 5}}
Salida: 504
Explicación:
A continuación se muestra el árbol dado y el árbol resultante después de eliminar el borde:
Elimine el borde entre el 1 y el 4, luego
t1 = valor en [0] + valor en [1] + valor en [2] = 13 + 8 + 7
t1 = valor en [3] + valor en [4] + valor en [5] = 4 + 5 + 9
t1*t2 = (13 + 8 + 7) * (4 + 5 + 9) = 504Entrada: N = 7, arr[]= {13, 8, 7, 4, 5, 9, 100}, Edges[][] = { {0, 1}, {1, 2}, {1, 4} , {3, 4}, {4, 5}, {2, 6}}
Salida: 4600
Explicación:
A continuación se muestra el árbol dado y el árbol resultante después de eliminar el borde:
Elimine el borde entre el 2 y el 6, luego
t1 = valor en [0] + valor en [1] + valor en [2] + valor en [3] + valor en [4] + valor en [5] = 13 + 8 + 7 + 4 + 5 + 9
t2 = valor en [6] = 100
t1*t2 = (13 + 8 + 7 + 5 + 4 + 9) * (100) = 4600
Enfoque: la idea es atravesar el árbol dado e intentar romper el árbol en todos los bordes posibles y luego encontrar el costo máximo de dividir en esos bordes. Después de todos los pasos anteriores, imprima el costo máximo entre todas las divisiones. A continuación se muestran los pasos:
- Todos los bordes se almacenan usando los bordes de la lista de adyacencia y los valores en cada Node se almacenan en la array dada arr[] .
- Para el Node actual, encuentre la suma de valores en sus descendientes, incluyéndose a sí mismo.
- Supongamos que si se elimina el borde entre el Node actual y su padre, se pueden formar dos árboles.
- Ahora, calcule los valores de t1, t2 y verifique que el producto de t1 y t2 sea máximo o no.
- Repita este proceso recursivamente para todos los Nodes secundarios del Node actual.
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;
// To store the results and sum of
// all nodes in the array
int ans = 0, allsum = 0;
// To create adjacency list
vector<int> edges[100001];
// Function to add edges into the
// adjacency list
void addedge(int a, int b)
{
edges[a].push_back(b);
edges[b].push_back(a);
}
// Recursive function that calculate
// the value of the cost of splitting
// the tree recursively
void findCost(int r, int p, int arr[])
{
int i, cur;
for (i = 0; i < edges[r].size();
i++) {
// Fetch the child of node-r
cur = edges[r].at(i);
// Neglect if cur node is parent
if (cur == p)
continue;
findCost(cur, r, arr);
// Add all values of nodes
// which are decendents of r
arr[r] += arr[cur];
}
// The two trees formed are rooted
// at 'r' with its decendents
int t1 = arr[r];
int t2 = allsum - t1;
// Check and replace if current
// product t1*t2 is large
if (t1 * t2 > ans) {
ans = t1 * t2;
}
}
// Function to find the maximum cost
// after splitting the tree in 2 halves
void maximumCost(int r, int p,
int N, int M,
int arr[],
int Edges[][2])
{
// Find sum of values in all nodes
for (int i = 0; i < N; i++) {
allsum += arr[i];
}
// Traverse edges to create
// adjacency list
for (int i = 0; i < M; i++) {
addedge(Edges[i][0],
Edges[i][1]);
}
// Function Call
findCost(r, p, arr);
}
// Driver Code
int main()
{
int a, b, N = 6;
// Values in each node
int arr[] = { 13, 8, 7, 4, 5, 9 };
int M = 5;
// Given Edges
int Edges[][2] = { { 0, 1 }, { 1, 2 },
{ 1, 4 }, { 3, 4 },
{ 4, 5 } };
maximumCost(1, -1, N, M, arr, Edges);
cout << ans;
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// To store the results and sum of
// all nodes in the array
static int ans = 0, allsum = 0;
// To create adjacency list
static Vector<Integer> []edges = new Vector[100001];
// Function to add edges into the
// adjacency list
static void addedge(int a, int b)
{
edges[a].add(b);
edges[b].add(a);
}
// Recursive function that calculate
// the value of the cost of splitting
// the tree recursively
static void findCost(int r, int p, int arr[])
{
int i, cur;
for (i = 0; i < edges[r].size(); i++)
{
// Fetch the child of node-r
cur = edges[r].get(i);
// Neglect if cur node is parent
if (cur == p)
continue;
findCost(cur, r, arr);
// Add all values of nodes
// which are decendents of r
arr[r] += arr[cur];
}
// The two trees formed are rooted
// at 'r' with its decendents
int t1 = arr[r];
int t2 = allsum - t1;
// Check and replace if current
// product t1*t2 is large
if (t1 * t2 > ans)
{
ans = t1 * t2;
}
}
// Function to find the maximum cost
// after splitting the tree in 2 halves
static void maximumCost(int r, int p,
int N, int M,
int arr[],
int Edges[][])
{
// Find sum of values in all nodes
for (int i = 0; i < N; i++)
{
allsum += arr[i];
}
// Traverse edges to create
// adjacency list
for (int i = 0; i < M; i++)
{
addedge(Edges[i][0],
Edges[i][1]);
}
// Function Call
findCost(r, p, arr);
}
// Driver Code
public static void main(String[] args)
{
int a, b, N = 6;
// Values in each node
int arr[] = {13, 8, 7, 4, 5, 9};
int M = 5;
// Given Edges
int Edges[][] = {{0, 1}, {1, 2},
{1, 4}, {3, 4},
{4, 5}};
for (int i = 0; i < edges.length; i++)
edges[i] = new Vector<Integer>();
maximumCost(1, -1, N, M, arr, Edges);
System.out.print(ans);
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program for the above approach # To store the results and sum of # all nodes in the array ans = 0 allsum = 0 # To create adjacency list edges = [[] for i in range(100001)] # Function to add edges into the # adjacency list def addedge(a, b): global edges edges[a].append(b) edges[b].append(a) # Recursive function that calculate # the value of the cost of splitting # the tree recursively def findCost(r, p, arr): global edges global ans global allsum i = 0 for i in range(len(edges[r])): # Fetch the child of node-r cur = edges[r][i] # Neglect if cur node is parent if (cur == p): continue findCost(cur, r, arr) # Add all values of nodes # which are decendents of r arr[r] += arr[cur] # The two trees formed are rooted # at 'r' with its decendents t1 = arr[r] t2 = allsum - t1 # Check and replace if current # product t1*t2 is large if (t1 * t2 > ans): ans = t1 * t2 # Function to find the maximum cost # after splitting the tree in 2 halves def maximumCost(r, p, N, M, arr, Edges): global allsum # Find sum of values in all nodes for i in range(N): allsum += arr[i] # Traverse edges to create # adjacency list for i in range(M): addedge(Edges[i][0], Edges[i][1]) # Function Call findCost(r, p, arr) # Driver Code if __name__ == '__main__': N = 6 # Values in each node arr = [ 13, 8, 7, 4, 5, 9 ] M = 5 # Given Edges Edges = [ [ 0, 1 ], [ 1, 2 ], [ 1, 4 ], [ 3, 4 ], [ 4, 5 ] ] maximumCost(1, -1, N, M, arr, Edges) print(ans) # This code is contributed by ipg2016107
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// To store the results and sum of
// all nodes in the array
static int ans = 0, allsum = 0;
// To create adjacency list
static List<int> []edges = new List<int>[100001];
// Function to add edges into the
// adjacency list
static void addedge(int a, int b)
{
edges[a].Add(b);
edges[b].Add(a);
}
// Recursive function that calculate
// the value of the cost of splitting
// the tree recursively
static void findCost(int r, int p, int []arr)
{
int i, cur;
for (i = 0; i < edges[r].Count; i++)
{
// Fetch the child of node-r
cur = edges[r][i];
// Neglect if cur node is parent
if (cur == p)
continue;
findCost(cur, r, arr);
// Add all values of nodes
// which are decendents of r
arr[r] += arr[cur];
}
// The two trees formed are rooted
// at 'r' with its decendents
int t1 = arr[r];
int t2 = allsum - t1;
// Check and replace if current
// product t1*t2 is large
if (t1 * t2 > ans)
{
ans = t1 * t2;
}
}
// Function to find the maximum cost
// after splitting the tree in 2 halves
static void maximumCost(int r, int p,
int N, int M,
int []arr, int [, ]Edges)
{
// Find sum of values in all nodes
for (int i = 0; i < N; i++)
{
allsum += arr[i];
}
// Traverse edges to create
// adjacency list
for (int i = 0; i < M; i++)
{
addedge(Edges[i, 0],
Edges[i, 1]);
}
// Function Call
findCost(r, p, arr);
}
// Driver Code
public static void Main(String[] args)
{
int N = 6;
// Values in each node
int []arr = {13, 8, 7, 4, 5, 9};
int M = 5;
// Given Edges
int [,]Edges = {{0, 1},
{1, 2}, {1, 4},
{3, 4}, {4, 5}};
for (int i = 0; i < edges.Length; i++)
edges[i] = new List<int>();
maximumCost(1, -1, N, M, arr, Edges);
Console.Write(ans);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program for the above approach
// To store the results and sum of
// all nodes in the array
let ans = 0, allsum = 0;
// To create adjacency list
let edges = new Array(100001);
// Function to add edges into the
// adjacency list
function addedge(a, b)
{
edges[a].push(b);
edges[b].push(a);
}
// Recursive function that calculate
// the value of the cost of splitting
// the tree recursively
function findCost(r, p, arr)
{
let i, cur;
for (i = 0; i < edges[r].length; i++)
{
// Fetch the child of node-r
cur = edges[r][i];
// Neglect if cur node is parent
if (cur == p)
continue;
findCost(cur, r, arr);
// Add all values of nodes
// which are decendents of r
arr[r] += arr[cur];
}
// The two trees formed are rooted
// at 'r' with its decendents
let t1 = arr[r];
let t2 = allsum - t1;
// Check and replace if current
// product t1*t2 is large
if (t1 * t2 > ans)
{
ans = t1 * t2;
}
}
// Function to find the maximum cost
// after splitting the tree in 2 halves
function maximumCost(r, p, N, M, arr, Edges)
{
// Find sum of values in all nodes
for (let i = 0; i < N; i++)
{
allsum += arr[i];
}
// Traverse edges to create
// adjacency list
for (let i = 0; i < M; i++)
{
addedge(Edges[i][0], Edges[i][1]);
}
// Function Call
findCost(r, p, arr);
}
let N = 6;
// Values in each node
let arr = [13, 8, 7, 4, 5, 9];
let M = 5;
// Given Edges
let Edges = [[0, 1], [1, 2], [1, 4], [3, 4], [4, 5]];
for (let i = 0; i < edges.length; i++)
edges[i] = [];
maximumCost(1, -1, N, M, arr, Edges);
document.write(ans);
</script>
Producción:
504
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por saideepgummadavelly y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA