Dado un árbol no dirigido con N Nodes numerados del 1 al N y un arreglo A[] donde A[i] denota el valor asignado a (i+1) el Node . Las conexiones entre los Nodes se proporcionan en una array bidimensional edge [] . La tarea es encontrar la suma máxima de rutas entre dos Nodes cualesquiera. (Ambos Nodes pueden ser iguales también).
Nota: La suma del camino es igual a la suma del valor de los Nodes de ese camino.
Ejemplos:
Entrada: N = 6, A[] = {4, -1, -3, 5, 7, -2},
bordes[][] = {{1, 2}, {1, 3}, {2, 4 }, {2, 5}, {2, 6}}
Salida: 11
Explicación: La suma de la ruta simple entre los Nodes 4 y 6 hasta el Node 2, es decir, 5-1+7 = 11
suma máxima de rutas = 11
Entrada: N = 3, A[] = {2, 3, 4}, bordes[][] = {{1, 2}, {1, 3}}
Salida: 9
Enfoque ingenuo: una solución simple es encontrar la suma de la ruta entre cada dos Nodes por profundidad, primero busque en el árbol y luego encuentre el máximo de ellos.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: un enfoque eficiente para resolver el problema en un primer recorrido de búsqueda en profundidad se basa en la siguiente idea:
La idea es que, para cada Node, encuentre dos caminos (los caminos que comienzan en ese Node y llegan a cualquier profundidad) con la suma máxima de caminos. El resultado máximo para ese Node será igual a la suma de esos dos caminos con el Node.
El máximo entre todos los Nodes es la suma máxima de rutas del árbol.
Siga los pasos para resolver el problema:
- Utilice un recorrido DFS a partir de la raíz.
- Use una array para almacenar la suma máxima de rutas a partir de un Node.
- En cada recorrido DFS:
- Encuentre las dos sumas máximas de rutas a partir de eso (por ejemplo, maximumBranchSum1 y maximumBranchSum2 ) que almacena 0 si la suma máxima de rutas es negativa (porque el Node inicial y final de una ruta puede ser el mismo que se menciona en el problema).
- Almacene la suma máxima de rutas en la array
- La suma máxima de caminos del camino que pasa por el Node actual y que pertenece a su subárbol es la suma de los dos caminos máximos y A[i] .
- El valor máximo entre todas esas sumas máximas de rutas es la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Final result variable
int result = 0;
// Helper function to calculate
// the maximum path sum using DFS
void findMaximumPathSum(int currentNode,
int previousNode,
vector<int> adj[],
int A[])
{
// Nodes to which currentNode is
// connected to
vector<int> v = adj[currentNode];
int maximumBranchSum1 = 0;
int maximumBranchSum2 = 0;
for (int i = 0; i < v.size(); i++) {
// checking whether the branch is
// visited already
if (v[i] == previousNode) {
continue;
}
findMaximumPathSum(v[i], currentNode,
adj, A);
// Storing the maximum of value of
// branch path sums
// maximumBranchSum1 will store the
// maximum value
// maximumBranchSum2 will store the
// 2nd most maximum value
if (A[v[i]] > maximumBranchSum1) {
maximumBranchSum2 = maximumBranchSum1;
maximumBranchSum1 = A[v[i]];
}
else {
maximumBranchSum2
= max(maximumBranchSum2, A[v[i]]);
}
}
result = max(result,
A[currentNode] + maximumBranchSum1
+ maximumBranchSum2);
// updating the value of current value
// with maximum path sum including
// currentNode
A[currentNode] += maximumBranchSum1;
}
// Function to get the maximum path sum
void print(int A[], int N, pair<int, int> edges[])
{
vector<int> adj[N];
// adjacency list for undirected graph
for (int i = 0; i < N - 1; i++) {
int x = edges[i].first;
int y = edges[i].second;
adj[x - 1].push_back(y - 1);
adj[y - 1].push_back(x - 1);
}
findMaximumPathSum(0, -1, adj, A);
cout << result << endl;
}
// Driver code
int main()
{
int N = 6;
int A[N] = { 4, -1, -3, 5, 7, -2 };
pair<int, int> edges[N - 1] = {
{ 1, 2 }, { 1, 3 }, { 2, 4 }, { 2, 5 }, { 2, 6 }
};
// Function call
print(A, N, edges);
return 0;
}
Java
// Java code to implement the approach
import java.io.*;
import java.util.*;
class GFG {
// Function to add edge
static void addEdge(ArrayList<ArrayList<Integer> > adj,
int s, int d)
{
adj.get(s).add(d);
adj.get(d).add(s);
}
static int result = 0;
// Helper function to calculate
// the maximum path sum using DFS
public static void
findMaximumPathSum(int currentNode,
int previousNode,
ArrayList<ArrayList<Integer> > adj,
int A[])
{
// Nodes to which currentNode
// is connected to
ArrayList<Integer> v = adj.get(currentNode);
int maximumBranchSum1 = 0, maximumBranchSum2 = 0;
for (int i = 0; i < v.size(); i++) {
// Checking whether the branch
// is visited already
if (v.get(i) == previousNode) {
continue;
}
findMaximumPathSum(v.get(i),
currentNode, adj,
A);
// Storing the maximum of value of branch path
// sums maximumBranchSum1 will store the maximum
// value maximumBranchSum2 will store the 2nd
// most maximum value
if (A[v.get(i)] > maximumBranchSum1) {
maximumBranchSum2
= maximumBranchSum1;
maximumBranchSum1
= A[v.get(i)];
}
else {
maximumBranchSum2 = Math.max(
maximumBranchSum2, A[v.get(i)]);
}
}
result = Math.max(result, A[currentNode]
+ maximumBranchSum1
+ maximumBranchSum2);
// Updating the value of current node with
// maximum path sum including currentNode
A[currentNode] += maximumBranchSum1;
}
// Driver code
public static void main(String[] args)
{
int N = 6;
int A[] = { 4, -1, -3, 5, 7, -2 };
ArrayList<ArrayList<Integer> > adj
= new ArrayList<ArrayList<Integer> >(N);
for (int i = 0; i < N; i++)
adj.add(new ArrayList<Integer>());
addEdge(adj, 0, 1);
addEdge(adj, 0, 2);
addEdge(adj, 1, 3);
addEdge(adj, 1, 4);
addEdge(adj, 1, 5);
// Driver code
findMaximumPathSum(0, -1, adj, A);
System.out.println(result);
}
}
Python3
# Python code to implement the approach # Function to add edge def addEdge(adj, s, d): adj[s].append(d) adj[d].append(s) result = 0 # Helper function to calculate # the maximum path sum using DFS def findMaximumPathSum(currentNode, previousNode, adj, A): # Nodes to which currentNode # is connected to v = adj[currentNode] maximumBranchSum1 = 0 maximumBranchSum2 = 0 for i in range(len(v)): # Checking whether the branch # is visited already if (v[i] == previousNode): continue findMaximumPathSum(v[i], currentNode, adj, A) # Storing the maximum of value of branch path # sums maximumBranchSum1 will store the maximum # value maximumBranchSum2 will store the 2nd # most maximum value if (A[v[i]] > maximumBranchSum1): maximumBranchSum2 = maximumBranchSum1 maximumBranchSum1 = A[v[i]] else: maximumBranchSum2 = max(maximumBranchSum2, A[v[i]]) global result result = max(result, A[currentNode] + maximumBranchSum1 + maximumBranchSum2) # Updating the value of current node with # maximum path sum including currentNode A[currentNode] += maximumBranchSum1 # Driver code N = 6 A = [4, -1, -3, 5, 7, -2] adj = [] for i in range(N): adj.append([]) addEdge(adj, 0, 1) addEdge(adj, 0, 2) addEdge(adj, 1, 3) addEdge(adj, 1, 4) addEdge(adj, 1, 5) # Driver code findMaximumPathSum(0, -1, adj, A) print(result) # This code is contributed by gfgking.
Javascript
<script>
// Javascript code to implement the approach
// Function to add edge
function addEdge(adj, s, d) {
adj[s].push(d);
adj[d].push(s);
}
let result = 0;
// Helper function to calculate
// the maximum path sum using DFS
function findMaximumPathSum(currentNode, previousNode, adj, A) {
// Nodes to which currentNode
// is connected to
let v = adj[currentNode];
let maximumBranchSum1 = 0, maximumBranchSum2 = 0;
for (let i = 0; i < v.length; i++) {
// Checking whether the branch
// is visited already
if (v[i] == previousNode) {
continue;
}
findMaximumPathSum(v[i],
currentNode, adj,
A);
// Storing the maximum of value of branch path
// sums maximumBranchSum1 will store the maximum
// value maximumBranchSum2 will store the 2nd
// most maximum value
if (A[v[i]] > maximumBranchSum1) {
maximumBranchSum2
= maximumBranchSum1;
maximumBranchSum1
= A[v[i]];
}
else {
maximumBranchSum2 = Math.max(
maximumBranchSum2, A[v[i]]);
}
}
result = Math.max(result, A[currentNode]
+ maximumBranchSum1
+ maximumBranchSum2);
// Updating the value of current node with
// maximum path sum including currentNode
A[currentNode] += maximumBranchSum1;
}
// Driver code
let N = 6;
let A = [4, -1, -3, 5, 7, -2];
let adj = [];
for (let i = 0; i < N; i++)
adj.push([]);
addEdge(adj, 0, 1);
addEdge(adj, 0, 2);
addEdge(adj, 1, 3);
addEdge(adj, 1, 4);
addEdge(adj, 1, 5);
// Driver code
findMaximumPathSum(0, -1, adj, A);
document.write(result);
// This code is contributed by Saurabh Jaiswal
</script>
Producción
11
Complejidad temporal: O(N)
Espacio auxiliar: O(N)