Dado un árbol que consta de N vértices, con raíz en el vértice 1 y una array val[] que representa los valores asignados a cada vértice, y una array cost[] que representa el costo de cada arista en el árbol , la tarea es encontrar el número mínimo de hojas a ser removidas del árbol dado tal que:
Para cualquier vértice V , la suma del costo de las aristas de un vértice U en su subárbol nunca excede val[U] .
Ejemplos :
Entrada: N = 9, val[] = {88, 22, 83, 14, 95, 91, 98, 53, 11}, cost[] = {-1, 24, -8, 67, 64,
65, 12 , -80, 8 }
Salida: 5
Explicación:
El gráfico final después de la eliminación necesaria de las hojas es el siguiente:
Coste de las aristas (1, 4) = 67 > 14 (= val[4]). Por lo tanto, se elimina el vértice 4.
Coste de las aristas (3, 2) = 24 > 22 (= val[2]). Por lo tanto, se elimina el vértice 2.
Coste de las aristas (1 –> 5 –> 7 –> 3 –> 9) = 64 + 12 + 8 – 8 = 76 > 11 (= val[9]). Por lo tanto, el vértice 9 debe eliminarse. Por lo tanto, se elimina todo el subárbol {9, 6, 8}.
Por lo tanto, se eliminan 5 Nodes del árbol.Entrada: N = 7, val[] = { 11, 16, 27, 21, 15, 9, 11 }, cost[]
= { 12, 1, 7, -17, -2, 2, 17}
edge[] = {{0, 3}, {0, 4}, {3, 6}, {4, 2}, {2, 1}, {2, 5}} Salida
: 7
Enfoque:
siga los pasos a continuación para resolver el problema:
- Si para un vértice V , hay un vértice U tal que el costo del borde (V –> U) excede val[U] , no hay otra opción excepto eliminar todo el subárbol enraizado en U o en V. Esto se debe a que estamos solo se permite borrar los vértices de las hojas.
- Dado que solo se puede eliminar el vértice de la hoja, para eliminar U o V , se debe eliminar todo el subárbol hoja por hoja para llegar al vértice U o V .
- Para minimizar la cantidad de hojas a eliminar, seleccione con avidez el subárbol con una menor cantidad de vértices, es decir, el subárbol de V se eliminará si la cantidad de vértices en el subárbol de V excede la cantidad de vértices en el subárbol de U , y viceversa. viceversa
- Aplique la primera búsqueda en profundidad en el árbol y, para cada vértice no visitado, compruebe si cumple la condición requerida.
- Aumente el conteo por cada vértice que satisfaga la condición. Para los vértices que no cumplen la condición, no es necesario atravesar sus subárboles, ya que es necesario eliminarlos por completo.
- Finalmente, imprima N – cuenta , después de completar el recorrido del árbol, ya que la cuenta contiene la cantidad de vértices que no se requieren eliminar.
A continuación se muestra la implementación del enfoque explicado anteriormente:
C++
// C++ Program to find the minimum
// number of leaves to be deleted
#include <bits/stdc++.h>
using namespace std;
// Stores the count of safe nodes
int cnt = 0;
// Function to perform DFS on the Tree
// to obtain the count of vertices that
// are not required to be deleted
void dfs(int* val, int* cost,
vector<vector<int> >& tr,
int u, int s)
{
// Update cost to reach
// the vertex
s = s + cost[u];
if (s < 0)
s = 0;
// If the vertex does not
// satisfy the condition
if (s > val[u])
return;
// Otherwise
cnt++;
// Traverse its subtree
for (int i = 0; i < tr[u].size(); i++) {
dfs(val, cost, tr, tr[u][i], s);
}
}
// Driver Code
int main()
{
int n = 9;
int val[] = { 88, 22, 83, 14, 95,
91, 98, 53, 11 };
int cost[] = { -1, 24, -8, 67, 64,
65, 12, -80, 8 };
// Stores the Tree
vector<vector<int> > tr(n + 1);
tr[0].push_back(3);
tr[0].push_back(4);
tr[4].push_back(6);
tr[6].push_back(2);
tr[2].push_back(1);
tr[2].push_back(8);
tr[8].push_back(5);
tr[5].push_back(7);
// Perform DFS
dfs(val, cost, tr, 0, 0);
// Print the number of nodes
// to be deleted
cout << n - cnt;
return 0;
}
Java
// Java Program to find the minimum
// number of leaves to be deleted
import java.util.*;
class GFG{
// Stores the count of safe nodes
static int cnt = 0;
// Function to perform DFS on the Tree
// to obtain the count of vertices that
// are not required to be deleted
static void dfs(int []val, int []cost,
Vector<Integer> []tr,
int u, int s)
{
// Update cost to reach
// the vertex
s = s + cost[u];
if (s < 0)
s = 0;
// If the vertex does not
// satisfy the condition
if (s > val[u])
return;
// Otherwise
cnt++;
// Traverse its subtree
for (int i = 0; i < tr[u].size(); i++)
{
dfs(val, cost, tr, tr[u].get(i), s);
}
}
// Driver Code
public static void main(String[] args)
{
int n = 9;
int val[] = {88, 22, 83, 14, 95,
91, 98, 53, 11};
int cost[] = {-1, 24, -8, 67, 64,
65, 12, -80, 8};
// Stores the Tree
@SuppressWarnings("unchecked")
Vector<Integer> []tr = new Vector[n + 1];
for (int i = 0; i < tr.length; i++)
tr[i] = new Vector<Integer>();
tr[0].add(3);
tr[0].add(4);
tr[4].add(6);
tr[6].add(2);
tr[2].add(1);
tr[2].add(8);
tr[8].add(5);
tr[5].add(7);
// Perform DFS
dfs(val, cost, tr, 0, 0);
// Print the number of nodes
// to be deleted
System.out.print(n - cnt);
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program to find the minimum # number of leaves to be deleted # Stores the count of safe nodes cnt = 0 # Function to perform DFS on the Tree # to obtain the count of vertices that # are not required to be deleted def dfs(val, cost, tr, u, s): global cnt # Update cost to reach # the vertex s = s + cost[u] if (s < 0): s = 0 # If the vertex does not # satisfy the condition if (s > val[u]): return # Otherwise cnt += 1 # Traverse its subtree for i in range(0, len(tr[u])): dfs(val, cost, tr, tr[u][i], s) # Driver Code if __name__ == "__main__": n = 9 val = [ 88, 22, 83, 14, 95, 91, 98, 53, 11 ] cost = [ -1, 24, -8, 67, 64, 65, 12, -80, 8] # Stores the Tree tr = [[] for i in range(n + 1)] tr[0].append(3) tr[0].append(4) tr[4].append(6) tr[6].append(2) tr[2].append(1) tr[2].append(8) tr[8].append(5) tr[5].append(7) # Perform DFS dfs(val, cost, tr, 0, 0) # Print the number of nodes # to be deleted print(n - cnt) # This code is contributed by rutvik_56
C#
// C# Program to find the minimum
// number of leaves to be deleted
using System;
using System.Collections.Generic;
class GFG{
// Stores the count of safe nodes
static int cnt = 0;
// Function to perform DFS on the Tree
// to obtain the count of vertices that
// are not required to be deleted
static void dfs(int []val, int []cost,
List<int> []tr,
int u, int s)
{
// Update cost to reach
// the vertex
s = s + cost[u];
if (s < 0)
s = 0;
// If the vertex does not
// satisfy the condition
if (s > val[u])
return;
// Otherwise
cnt++;
// Traverse its subtree
for (int i = 0; i < tr[u].Count; i++)
{
dfs(val, cost, tr, tr[u][i], s);
}
}
// Driver Code
public static void Main(String[] args)
{
int n = 9;
int []val = {88, 22, 83, 14, 95,
91, 98, 53, 11};
int []cost = {-1, 24, -8, 67, 64,
65, 12, -80, 8};
// Stores the Tree
List<int> []tr = new List<int>[n + 1];
for (int i = 0; i < tr.Length; i++)
tr[i] = new List<int>();
tr[0].Add(3);
tr[0].Add(4);
tr[4].Add(6);
tr[6].Add(2);
tr[2].Add(1);
tr[2].Add(8);
tr[8].Add(5);
tr[5].Add(7);
// Perform DFS
dfs(val, cost, tr, 0, 0);
// Print the number of nodes
// to be deleted
Console.Write(n - cnt);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript Program to find the minimum
// number of leaves to be deleted
// Stores the count of safe nodes
var cnt = 0;
// Function to perform DFS on the Tree
// to obtain the count of vertices that
// are not required to be deleted
function dfs(val, cost, tr, u, s)
{
// Update cost to reach
// the vertex
s = s + cost[u];
if (s < 0)
s = 0;
// If the vertex does not
// satisfy the condition
if (s > val[u])
return;
// Otherwise
cnt++;
// Traverse its subtree
for (var i = 0; i < tr[u].length; i++)
{
dfs(val, cost, tr, tr[u][i], s);
}
}
// Driver Code
var n = 9;
var val = [88, 22, 83, 14, 95,
91, 98, 53, 11];
var cost = [-1, 24, -8, 67, 64,
65, 12, -80, 8];
// Stores the Tree
var tr = Array.from(Array(n+1), ()=>Array());
tr[0].push(3);
tr[0].push(4);
tr[4].push(6);
tr[6].push(2);
tr[2].push(1);
tr[2].push(8);
tr[8].push(5);
tr[5].push(7);
// Perform DFS
dfs(val, cost, tr, 0, 0);
// Print the number of nodes
// to be deleted
document.write(n - cnt);
</script>
Producción:
5
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por sharadgoyal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA