Maximize sum of paths from LCA of nodes u and v to one of those nodes
Given a tree consisting of N nodes an array edges[][3] of size N – 1 such that for each {X, Y, W} in edges[] there exists an edge between node X and node Y with a weight of W and two nodes u and v, the task is to find the maximum sum of weights of edges in the path from Lowest Common Ancestor(LCA) of nodes (u, v) to node u and node v.
Examples:
Input: N = 7, edges[][] = {{1, 2, 2}, {1, 3, 3}, {3, 4, 4}, {4, 6, 5}, {3, 5, 7}, {5, 7, 6}}, u = 6, v = 5
Output: 9
Explanation:The path sum from node 3 to node 5 is 7.
The path sum from node 3 to node 6 is 4 + 5 = 9.
Therefore, the maximum among the two paths is 9.Input: N = 4, edges[][] = {{1, 2, 3}, {2, 3, 4}, {3, 4, 5}, u = 1, v = 4
Output: 12
Approach: The given problem can be solved by using the concept of Binary Lifting to find the LCA. Follow the steps below to solve the problem:
- Create the tree from the given input of edges.
- Find LCA for the given nodes u and v using the approach discussed in this article.
- Perform the Depth First Search to find the path sum i.e., the sum of weights of edges in the path from LCA to node u and node v and store it in the variables, say maxPath1 and maxPath2 respectively.
- After completing the above steps, print the maximum of maxPath1 and maxPath2 as the result.
Below is the implementation of the above approach:
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> |
Python3
# Python program for the above approach import math N = 100001 M = int (math.log2(N)) + 1 # Keeps the track of 2^i ancestors anc = [[ 0 ] * M for i in range (N)] # Keeps the track of sum of path from # 2^i ancestor to current node val = [[ 0 ] * M for i in range (N)] # Stores the depth for each node depth = [ 0 ] * N # Function to build tree to find the # LCA of the two nodes def build(tree, x, p, w, d = 0 ): # Base Case anc[x][ 0 ] = p val[x][ 0 ] = w depth[x] = d # Traverse the given edges[] for i in range ( 1 , M): 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 in tree[x]: if i[ 0 ] ! = p: # Recursive Call for building # the child node build(tree, i[ 0 ], x, i[ 1 ], d + 1 ) # Function to find LCA and calculate # the maximum distance def findMaxPath(x, y): if x = = y: return 1 # Stores the path sum from LCA # to node x and y l = 0 r = 0 # If not on same depth, then # make the same depth if depth[x] ! = depth[y]: # Find the difference dif = abs (depth[x] - depth[y]) if depth[x] > depth[y]: x, y = y, x for i in range (M): if ( 1 << 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 i in range (M - 1 , - 1 , - 1 ): 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 # Given Tree N = 7 tree = [[] for i in range (N + 1 )] tree[ 1 ].append(( 2 , 2 )) tree[ 2 ].append(( 1 , 2 )) tree[ 1 ].append(( 3 , 3 )) tree[ 2 ].append(( 1 , 3 )) tree[ 3 ].append(( 4 , 4 )) tree[ 4 ].append(( 3 , 4 )) tree[ 4 ].append(( 6 , 5 )) tree[ 6 ].append(( 4 , 5 )) tree[ 3 ].append(( 5 , 7 )) tree[ 5 ].append(( 3 , 7 )) tree[ 5 ].append(( 7 , 6 )) tree[ 7 ].append(( 5 , 6 )) # Building ancestor and val[] array build(tree, 1 , 0 , 0 ) u = 6 v = 5 # Find maximum distance between two nodes print (findMaxPath(u, v)) #This code is contributed by Potta Lokesh |
9
Time Complexity: O(N*log(N))
Auxiliary Space: O(N*log(N))