Mayor suma de subárboles para cada vértice del árbol N-ario dado

Dado un árbol de N-arrays de N Nodes, con raíz en 1 , con bordes en la forma {u, v} , y una array de valores[] que consta de N enteros. Cada vértice i tiene un valor entero indicado por valores[i] . La tarea es encontrar la suma de subárbol más grande posible para cada vértice i agregando su valor a un subconjunto no vacío de sus vértices secundarios.

Ejemplos: 

Entrada: Bordes[][] = {{1, 2}, {1, 3}, {3, 4}}, valores[] = {1, -1, 0, 1}
Salida: 2 -1 1 1
Explicación :
A continuación se muestra el árbol dado:

                          1
                        / \
                     2 3
                              \
                               4
Se pueden elegir los siguientes subconjuntos para cada vértice:
Vértice 1: Se puede elegir el subconjunto de vértices {1, 3, 4} con valores {1, 0, 1}. Por lo tanto, suma = 1 + 0 + 1 = 2.
Vértice 2: Se puede elegir el subconjunto de vértices {2} con valores {-1}. Por lo tanto, suma = -1.
Vértice 3: el subconjunto de vértices {3, 4} se puede elegir con valores {0, 1}. Por lo tanto, suma = 0 + 1 = 1.
Vértice 4: Se puede elegir el subconjunto de vértices {4} con valores {1}. Por lo tanto, suma = 1.

Entrada: Bordes[][] = {{1, 2}, {1, 3}, {2, 4}, {2, 5}}, valores[] = {1, -1, -2, 1, 3 }
Salida: 5 4 -2 1 3
Explicación:
A continuación se muestra el árbol dado:

                          1
                        / \
                     2 3
                  / \    
                4 5
Se pueden elegir los siguientes subconjuntos para cada vértice:
Vértice 1: Se puede elegir el subconjunto de vértices {1, 4, 5} con valores {1, 1, 3}. Por lo tanto, suma = 1 + 1 + 3 = 5.
Vértice 2: Se puede elegir el subconjunto de vértices {4, 5} con valores {1, 3}. Por lo tanto, suma = 1 + 3 = 4. 
Vértice 3: Se puede elegir el subconjunto de vértices {3} con valores {-2}. Por lo tanto, suma = -2.
Vértice 4: el subconjunto de vértices {4} se puede elegir con valores {1}. Por lo tanto, suma = 1.
Vértice 5: El subconjunto de vértices {5} se puede elegir con valores {3}. Por lo tanto, suma = 3. 

Enfoque ingenuo: el enfoque más simple es atravesar el subárbol de cada vértice i de 1 a N y realizar DFS Traversal en él. Para cada vértice i , elija el subconjunto de sus vértices secundarios que tengan valores no negativos. Si el subconjunto de vértices elegidos está vacío, busque e imprima el Node que tenga el valor mínimo de modo que sea el Node secundario del vértice i . De lo contrario, imprima la suma de los valores de los Nodes presentes en el subconjunto. 

Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N) 

Enfoque eficiente: la idea es utilizar el enfoque de programación dinámica y transversal DFS . Siga los pasos a continuación para resolver el problema:

  • Inicialice una array ans[] de tamaño N para almacenar la suma máxima del subárbol para cada vértice.
  • Realice DFS Traversal para cada vértice y para cada vértice inicialice v , ans[v] con un valor negativo grande.
  • Si el vértice v es un vértice de hoja, entonces la respuesta para ese vértice sería valores[v] . Por lo tanto, asigne ans[v] = valores[v] .
  • De lo contrario, recorre los vértices adyacentes al vértice v y para cada vértice adyacente u , actualiza ans[v] como ans[v] = max(ans[u] + valores[v], valores[v], ans[u]) .
  • Después de los pasos anteriores, imprima los valores almacenados en la array ans[] como la respuesta para cada vértice.

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;
#define V 3
#define M 2
 
// Function to perform the DFS
// Traversal on the given Tree
void dfs(int v, int p,
         vector<int> adj[],
     int ans[], int vals[])
{
     
    // To check if v is leaf vertex
    bool isLeaf = 1;
 
    // Initialize answer for vertex v
    ans[v] = INT_MIN;
 
    // Traverse adjacency list of v
    for(int u : adj[v])
    {
        if (u == p)
            continue;
             
        isLeaf = 0;
        dfs(u, v, adj, ans, vals);
 
        // Update maximum subtree sum
        ans[v] = max(ans[u] + vals[v],
                 max(ans[u], vals[u]));
    }
 
    // If v is leaf
    if (isLeaf)
    {
        ans[v] = vals[v];
    }
}
 
// Function to calculate maximum
// subtree sum for each vertex
void printAnswer(int n,
                 int edges[V][M],
                 int values[])
{
     
    // Stores the adjacency list
    vector<int> adj[n];
     
    // Add Edges to the list
    for(int i = 0; i < n - 1; i++)
    {
        int u = edges[i][0] - 1;
        int v = edges[i][1] - 1;
         
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
 
    // Stores largest subtree
    // sum for each vertex
    int ans[n] ;
 
    // Calculate answer
    dfs(0, -1, adj, ans, values);
 
    // Print the result
    for(auto x : ans)
    {
        cout << x << " ";
    }
}
 
// Driver Code
int main()
{
     
    // Given nodes
    int N = 4;
 
    // Give N edges
    int edges[V][M] = { { 1, 2 },
                        { 1, 3 },
                        { 3, 4 } };
 
    // Given values
    int values[] = { 1, -1, 0, 1 };
 
    // Function Call
    printAnswer(N, edges, values);
}
 
// This code is contributed by Princi Singh

Java

// Java program for the above approach
 
import java.io.*;
import java.util.ArrayList;
 
@SuppressWarnings("unchecked")
class GFG {
 
    // Function to perform the DFS
    // Traversal on the given Tree
    static void dfs(int v, int p,
                    ArrayList<Integer> adj[],
                    int ans[], int vals[])
    {
 
        // To check if v is leaf vertex
        boolean isLeaf = true;
 
        // Initialize answer for vertex v
        ans[v] = Integer.MIN_VALUE;
 
        // Traverse adjacency list of v
        for (int u : adj[v]) {
            if (u == p)
                continue;
            isLeaf = false;
            dfs(u, v, adj, ans, vals);
 
            // Update maximum subtree sum
            ans[v] = Math.max(
                ans[u] + vals[v],
                Math.max(ans[u],
                         vals[u]));
        }
 
        // If v is leaf
        if (isLeaf) {
            ans[v] = vals[v];
        }
    }
 
    // Function to calculate maximum
    // subtree sum for each vertex
    static void printAnswer(
        int n, int edges[][], int values[])
    {
 
        // Stores the adjacency list
        ArrayList<Integer> adj[]
            = new ArrayList[n];
 
        for (int i = 0; i < n; i++)
            adj[i] = new ArrayList<>();
 
        // Add Edges to the list
        for (int i = 0; i < n - 1; i++) {
 
            int u = edges[i][0] - 1;
            int v = edges[i][1] - 1;
            adj[u].add(v);
            adj[v].add(u);
        }
 
        // Stores largest subtree
        // sum for each vertex
        int ans[] = new int[n];
 
        // Calculate answer
        dfs(0, -1, adj, ans, values);
 
        // Print the result
        for (int x : ans) {
            System.out.print(x + " ");
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given nodes
        int N = 4;
 
        // Give N edges
        int edges[][]
            = new int[][] { { 1, 2 },
                            { 1, 3 },
                            { 3, 4 } };
 
        // Given values
        int values[] = { 1, -1, 0, 1 };
 
        // Function Call
        printAnswer(N, edges, values);
    }
}

Python3

# Python3 program for the above approach
 
V = 3
M = 2
 
# Function to perform the DFS
# Traversal on the given Tree
def dfs(v, p):
 
    # To check if v is leaf vertex
    isLeaf = 1
 
    # Initialize answer for vertex v
    ans[v] = -10**9
 
    # Traverse adjacency list of v
    for u in adj[v]:
        if (u == p):
            continue
 
        isLeaf = 0
        dfs(u, v)
 
        # Update maximum subtree sum
        ans[v] = max(ans[u] + vals[v],max(ans[u], vals[u]))
 
    # If v is leaf
    if (isLeaf):
        ans[v] = vals[v]
 
# Function to calculate maximum
# subtree sum for each vertex
def printAnswer(n, edges, vals):
 
    # Stores the adjacency list
    # vector<int> adj[n];
 
    # Add Edges to the list
    for i in range(n - 1):
        u = edges[i][0] - 1
        v = edges[i][1] - 1
 
        adj[u].append(v)
        adj[v].append(u)
 
    # Calculate answer
    dfs(0, -1)
 
    # Print the result
    for x in ans:
        print(x, end=" ")
 
# Driver Code
if __name__ == '__main__':
 
    # Given nodes
    N = 4
 
    # Give N edges
    edges=[ [ 1, 2],
            [ 1, 3],
            [ 3, 4] ]
 
    adj=[[] for i in range(N)]
    ans=[0 for i in range(N)]
 
    # Given values
    vals=[1, -1, 0, 1]
 
    # Function Call
    printAnswer(N, edges, vals)
 
# This code is contributed by mohit kumar 29

C#

// C# program for the
// above approach
using System;
using System.Collections.Generic;
class GFG{
 
// Function to perform the DFS
// Traversal on the given Tree
static void dfs(int v, int p,
                List<int> []adj,
                int []ans, int []vals)
{
  // To check if v is leaf
  // vertex
  bool isLeaf = true;
 
  // Initialize answer for
  // vertex v
  ans[v] = int.MinValue;
 
  // Traverse adjacency list
  // of v
  foreach (int u in adj[v])
  {
    if (u == p)
      continue;
    isLeaf = false;
    dfs(u, v, adj, ans, vals);
 
    // Update maximum subtree
    // sum
    ans[v] = Math.Max(ans[u] +
                      vals[v],
             Math.Max(ans[u],
                      vals[u]));
  }
 
  // If v is leaf
  if (isLeaf)
  {
    ans[v] = vals[v];
  }
}
 
// Function to calculate maximum
// subtree sum for each vertex
static void printAnswer(int n,
                        int [,]edges,
                        int []values)
{
  // Stores the adjacency list
  List<int> []adj =
       new List<int>[n];
 
  for (int i = 0; i < n; i++)
    adj[i] = new List<int>();
 
  // Add Edges to the list
  for (int i = 0;
           i < n - 1; i++)
  {
    int u = edges[i, 0] - 1;
    int v = edges[i, 1] - 1;
    adj[u].Add(v);
    adj[v].Add(u);
  }
 
  // Stores largest subtree
  // sum for each vertex
  int []ans = new int[n];
 
  // Calculate answer
  dfs(0, -1, adj,
      ans, values);
 
  // Print the result
  foreach (int x in ans)
  {
    Console.Write(x + " ");
  }
}
 
// Driver Code
public static void Main(String[] args)
{
  // Given nodes
  int N = 4;
 
  // Give N edges
  int [,]edges = new int[,] {{1, 2},
                             {1, 3},
                             {3, 4}};
  // Given values
  int []values = {1, -1, 0, 1};
 
  // Function Call
  printAnswer(N, edges, values);
}
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
 
    // JavaScript program for the above approach
     
    // Function to perform the DFS
    // Traversal on the given Tree
    function dfs(v, p, adj, ans, vals)
    {
      // To check if v is leaf
      // vertex
      let isLeaf = true;
 
      // Initialize answer for
      // vertex v
      ans[v] = Number.MIN_VALUE;
 
      // Traverse adjacency list
      // of v
      for(let u = 0; u < adj[v].length; u++)
      {
        if (adj[v][u] == p)
          continue;
        isLeaf = false;
        dfs(adj[v][u], v, adj, ans, vals);
 
        // Update maximum subtree
        // sum
        ans[v] = Math.max(ans[adj[v][u]] +
                          vals[v],
                 Math.max(ans[adj[v][u]],
                          vals[adj[v][u]]));
      }
 
      // If v is leaf
      if (isLeaf)
      {
        ans[v] = vals[v];
      }
    }
 
    // Function to calculate maximum
    // subtree sum for each vertex
    function printAnswer(n, edges, values)
    {
      // Stores the adjacency list
      let adj = new Array(n);
 
      for (let i = 0; i < n; i++)
        adj[i] = [];
 
      // Add Edges to the list
      for (let i = 0; i < n - 1; i++)
      {
        let u = edges[i][0] - 1;
        let v = edges[i][1] - 1;
        adj[u].push(v);
        adj[v].push(u);
      }
 
      // Stores largest subtree
      // sum for each vertex
      let ans = new Array(n);
 
      // Calculate answer
      dfs(0, -1, adj, ans, values);
 
      // Print the result
      for(let x = 0; x < ans.length; x++)
      {
        document.write(ans[x] + " ");
      }
    }
     
    // Given nodes
    let N = 4;
 
    // Give N edges
    let edges = [[1, 2], [1, 3], [3, 4]];
    // Given values
    let values = [1, -1, 0, 1];
 
    // Function Call
    printAnswer(N, edges, values);
 
</script>
Producción: 

2 -1 1 1

 

Complejidad temporal: O(N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por kd710306 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 *