Dado un árbol que consta de N Nodes, una array de bordes[][3] de tamaño N – 1 tal que para cada {X, Y, W} en los bordes[] existe un borde entre el Node X y el Node Y con un peso de W y dos Nodes u y v , la tarea es encontrar la suma máxima de pesos de los bordes en la ruta desde el ancestro común más bajo (LCA) de los Nodes (u, v) hasta el Node u y el Node v .
Ejemplos:
Entrada: N = 7, bordes[][] = {{1, 2, 2}, {1, 3, 3}, {3, 4, 4}, {4, 6, 5}, {3, 5, 7}, {5, 7, 6}}, u = 6, v = 5
Salida: 9
Explicación:
La suma de caminos del Node 3 al Node 5 es 7.
La suma de caminos del Node 3 al Node 6 es 4 + 5 = 9.
Por lo tanto, el máximo entre los dos caminos es 9.Entrada: N = 4, bordes[][] = {{1, 2, 3}, {2, 3, 4}, {3, 4, 5}, u = 1, v = 4
Salida: 12
Enfoque: el problema dado se puede resolver utilizando el concepto de elevación binaria para encontrar el LCA . Siga los pasos a continuación para resolver el problema:
- Cree el árbol a partir de la entrada dada de bordes .
- Encuentre LCA para los Nodes uyv dados usando el enfoque discutido en este artículo .
- Realice la primera búsqueda en profundidad para encontrar la suma de la ruta, es decir, la suma de los pesos de los bordes en la ruta desde LCA hasta el Node u y el Node v , y guárdela en las variables, digamos maxPath1 y maxPath2 respectivamente.
- Después de completar los pasos anteriores, imprima el máximo de maxPath1 y maxPath2 como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
const ll N = 100001;
const ll M = log2(N) + 1;
// Keeps the track of 2^i ancestors
ll anc[N][M];
// Keeps the track of sum of path from
// 2^i ancestor to current node
ll val[N][M];
// Stores the depth for each node
ll depth[N];
// Function to build tree to find the
// LCA of the two nodes
void build(vector<pair<ll, ll> > tree[],
ll x, ll p, ll w, ll d = 0)
{
// Base Case
anc[x][0] = p;
val[x][0] = w;
depth[x] = d;
// Traverse the given edges[]
for (int i = 1; i < M; i++) {
anc[x][i] = anc[anc[x][i - 1]][i - 1];
val[x][i]
= val[anc[x][i - 1]][i - 1]
+ val[x][i - 1];
}
// Traverse the edges of node x
for (auto i : tree[x]) {
if (i.first != p) {
// Recursive Call for building
// the child node
build(tree, i.first, x,
i.second, d + 1);
}
}
}
// Function to find LCA and calculate
// the maximum distance
ll findMaxPath(ll x, ll y)
{
if (x == y)
return 1;
// Stores the path sum from LCA
// to node x and y
ll l = 0, r = 0;
// If not on same depth, then
// make the same depth
if (depth[x] != depth[y]) {
// Find the difference
ll dif = abs(depth[x] - depth[y]);
if (depth[x] > depth[y])
swap(x, y);
for (int i = 0; i < M; i++) {
if ((1ll << i) & (dif)) {
// Lifting y to reach the
// depth of node x
r += val[y][i];
// Value of weights path
// traversed to r
y = anc[y][i];
}
}
}
// If x == y the LCA is reached,
if (x == y)
return r + 1;
// And the maximum distance
for (int i = M - 1; i >= 0; i--) {
if (anc[x][i] != anc[y][i]) {
// Lifting both node x and y
// to reach LCA
l += val[x][i];
r += val[y][i];
x = anc[x][i];
y = anc[y][i];
}
}
l += val[x][0];
r += val[y][0];
// Return the maximum path sum
return max(l, r);
}
// Driver Code
int main()
{
// Given Tree
ll N = 7;
vector<pair<ll, ll> > tree[N + 1];
tree[1].push_back({ 2, 2 });
tree[2].push_back({ 1, 2 });
tree[1].push_back({ 3, 3 });
tree[2].push_back({ 1, 3 });
tree[3].push_back({ 4, 4 });
tree[4].push_back({ 3, 4 });
tree[4].push_back({ 6, 5 });
tree[6].push_back({ 4, 5 });
tree[3].push_back({ 5, 7 });
tree[5].push_back({ 3, 7 });
tree[5].push_back({ 7, 6 });
tree[7].push_back({ 5, 6 });
// Building ancestor and val[] array
build(tree, 1, 0, 0);
ll u, v;
u = 6, v = 5;
// Function Call
cout << findMaxPath(u, v);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
static int N = 100001;
static int M = (int) Math.log(N) + 1;
static class pair {
int first, second;
public pair(int first, int second) {
this.first = first;
this.second = second;
}
}
// Keeps the track of 2^i ancestors
static int[][] anc = new int[N][M];
// Keeps the track of sum of path from
// 2^i ancestor to current node
static int[][] val = new int[N][M];
// Stores the depth for each node
static int[] depth = new int[N];
// Function to build tree to find the
// LCA of the two nodes
static void build(Vector<pair> tree[], int x, int p, int w, int d) {
// Base Case
anc[x][0] = p;
val[x][0] = w;
depth[x] = d;
// Traverse the given edges[]
for (int i = 1; i < M; i++) {
anc[x][i] = anc[anc[x][i - 1]][i - 1];
val[x][i] = val[anc[x][i - 1]][i - 1] + val[x][i - 1];
}
// Traverse the edges of node x
for (pair i : tree[x]) {
if (i.first != p) {
// Recursive Call for building
// the child node
build(tree, i.first, x, i.second, d + 1);
}
}
}
// Function to find LCA and calculate
// the maximum distance
static int findMaxPath(int x, int y) {
if (x == y)
return 1;
// Stores the path sum from LCA
// to node x and y
int l = 0, r = 0;
// If not on same depth, then
// make the same depth
if (depth[x] != depth[y]) {
// Find the difference
int dif = Math.abs(depth[x] - depth[y]);
if (depth[x] > depth[y]) {
int t = x;
x = y;
y = t;
}
for (int i = 0; i < M; i++) {
if (((1L << i) & (dif)) != 0) {
// Lifting y to reach the
// depth of node x
r += val[y][i];
// Value of weights path
// traversed to r
y = anc[y][i];
}
}
}
// If x == y the LCA is reached,
if (x == y)
return r + 1;
// And the maximum distance
for (int i = M - 1; i >= 0; i--) {
if (anc[x][i] != anc[y][i]) {
// Lifting both node x and y
// to reach LCA
l += val[x][i];
r += val[y][i];
x = anc[x][i];
y = anc[y][i];
}
}
l += val[x][0];
r += val[y][0];
// Return the maximum path sum
return Math.max(l, r);
}
// Driver Code
public static void main(String[] args) {
// Given Tree
int N = 7;
@SuppressWarnings("unchecked")
Vector<pair>[] tree = new Vector[N + 1];
for (int i = 0; i < tree.length; i++)
tree[i] = new Vector<pair>();
tree[1].add(new pair(2, 2));
tree[2].add(new pair(1, 2));
tree[1].add(new pair(3, 3));
tree[2].add(new pair(1, 3));
tree[3].add(new pair(4, 4));
tree[4].add(new pair(3, 4));
tree[4].add(new pair(6, 5));
tree[6].add(new pair(4, 5));
tree[3].add(new pair(5, 7));
tree[5].add(new pair(3, 7));
tree[5].add(new pair(7, 6));
tree[7].add(new pair(5, 6));
// Building ancestor and val[] array
build(tree, 1, 0, 0, 0);
int u = 6;
int v = 5;
// Function Call
System.out.print(findMaxPath(u, v));
}
}
// This code is contributed by umadevi9616
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG {
static int N = 100001;
static int M = (int) Math.Log(N) + 1;
public class pair {
public int first, second;
public pair(int first, int second) {
this.first = first;
this.second = second;
}
}
// Keeps the track of 2^i ancestors
static int[,] anc = new int[N,M];
// Keeps the track of sum of path from
// 2^i ancestor to current node
static int[,] val = new int[N,M];
// Stores the depth for each node
static int[] depth = new int[N];
// Function to build tree to find the
// LCA of the two nodes
static void build(List<pair> []tree, int x, int p, int w, int d) {
// Base Case
anc[x,0] = p;
val[x,0] = w;
depth[x] = d;
// Traverse the given edges[]
for (int i = 1; i < M; i++) {
anc[x,i] = anc[anc[x,i - 1],i - 1];
val[x,i] = val[anc[x,i - 1],i - 1] + val[x,i - 1];
}
// Traverse the edges of node x
foreach (pair i in tree[x]) {
if (i.first != p) {
// Recursive Call for building
// the child node
build(tree, i.first, x, i.second, d + 1);
}
}
}
// Function to find LCA and calculate
// the maximum distance
static int findMaxPath(int x, int y) {
if (x == y)
return 1;
// Stores the path sum from LCA
// to node x and y
int l = 0, r = 0;
// If not on same depth, then
// make the same depth
if (depth[x] != depth[y]) {
// Find the difference
int dif = Math.Abs(depth[x] - depth[y]);
if (depth[x] > depth[y]) {
int t = x;
x = y;
y = t;
}
for (int i = 0; i < M; i++) {
if (((1L << i) & (dif)) != 0) {
// Lifting y to reach the
// depth of node x
r += val[y,i];
// Value of weights path
// traversed to r
y = anc[y,i];
}
}
}
// If x == y the LCA is reached,
if (x == y)
return r + 1;
// And the maximum distance
for (int i = M - 1; i >= 0; i--) {
if (anc[x,i] != anc[y,i]) {
// Lifting both node x and y
// to reach LCA
l += val[x,i];
r += val[y,i];
x = anc[x,i];
y = anc[y,i];
}
}
l += val[x,0];
r += val[y,0];
// Return the maximum path sum
return Math.Max(l, r);
}
// Driver Code
public static void Main(String[] args) {
// Given Tree
int N = 7;
List<pair>[] tree = new List<pair>[N + 1];
for (int i = 0; i < tree.Length; i++)
tree[i] = new List<pair>();
tree[1].Add(new pair(2, 2));
tree[2].Add(new pair(1, 2));
tree[1].Add(new pair(3, 3));
tree[2].Add(new pair(1, 3));
tree[3].Add(new pair(4, 4));
tree[4].Add(new pair(3, 4));
tree[4].Add(new pair(6, 5));
tree[6].Add(new pair(4, 5));
tree[3].Add(new pair(5, 7));
tree[5].Add(new pair(3, 7));
tree[5].Add(new pair(7, 6));
tree[7].Add(new pair(5, 6));
// Building ancestor and val[] array
build(tree, 1, 0, 0, 0);
int u = 6;
int v = 5;
// Function Call
Console.Write(findMaxPath(u, v));
}
}
// This code is contributed by umadevi9616
Javascript
<script>
// javascript program for the above approach
var N = 100001;
var M = parseInt( Math.log(N)) + 1;
class pair {
constructor(first , second) {
this.first = first;
this.second = second;
}
}
// Keeps the track of 2^i ancestors
var anc = Array(N).fill().map(()=>Array(M).fill(0));
// Keeps the track of sum of path from
// 2^i ancestor to current node
var val = Array(N).fill().map(()=>Array(M).fill(0));
// Stores the depth for each node
var depth = Array(N).fill(0);
// Function to build tree to find the
// LCA of the two nodes
function build( tree , x , p , w , d) {
// Base Case
anc[x][0] = p;
val[x][0] = w;
depth[x] = d;
// Traverse the given edges
for (var i = 1; i < M; i++) {
anc[x][i] = anc[anc[x][i - 1]][i - 1];
val[x][i] = val[anc[x][i - 1]][i - 1] + val[x][i - 1];
}
// Traverse the edges of node x
for (i of tree[x]) {
if (i.first != p) {
// Recursive Call for building
// the child node
build(tree, i.first, x, i.second, d + 1);
}
}
}
// Function to find LCA and calculate
// the maximum distance
function findMaxPath(x , y) {
if (x == y)
return 1;
// Stores the path sum from LCA
// to node x and y
var l = 0, r = 0;
// If not on same depth, then
// make the same depth
if (depth[x] != depth[y]) {
// Find the difference
var dif = Math.abs(depth[x] - depth[y]);
if (depth[x] > depth[y]) {
var t = x;
x = y;
y = t;
}
for (i = 0; i < M; i++) {
if (((1 << i) & (dif)) != 0) {
// Lifting y to reach the
// depth of node x
r += val[y][i];
// Value of weights path
// traversed to r
y = anc[y][i];
}
}
}
// If x == y the LCA is reached,
if (x == y)
return r + 1;
// And the maximum distance
for (i = M - 1; i >= 0; i--) {
if (anc[x][i] != anc[y][i]) {
// Lifting both node x and y
// to reach LCA
l += val[x][i];
r += val[y][i];
x = anc[x][i];
y = anc[y][i];
}
}
l += val[x][0];
r += val[y][0];
// Return the maximum path sum
return Math.max(l, r);
}
// Driver Code
// Given Tree
var N = 7;
var tree = Array(N + 1);
for (i = 0; i < tree.length; i++)
tree[i] = [];
tree[1].push(new pair(2, 2));
tree[2].push(new pair(1, 2));
tree[1].push(new pair(3, 3));
tree[2].push(new pair(1, 3));
tree[3].push(new pair(4, 4));
tree[4].push(new pair(3, 4));
tree[4].push(new pair(6, 5));
tree[6].push(new pair(4, 5));
tree[3].push(new pair(5, 7));
tree[5].push(new pair(3, 7));
tree[5].push(new pair(7, 6));
tree[7].push(new pair(5, 6));
// Building ancestor and val array
build(tree, 1, 0, 0, 0);
var u = 6;
var v = 5;
// Function Call
document.write(findMaxPath(u, v));
// This code is contributed by gauravrajput1
</script>
Producción:
9
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(N*log(N))