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 intusing namespace std;const ll N = 100001;const ll M = log2(N) + 1;// Keeps the track of 2^i ancestorsll anc[N][M];// Keeps the track of sum of path from// 2^i ancestor to current nodell val[N][M];// Stores the depth for each nodell depth[N];// Function to build tree to find the// LCA of the two nodesvoid 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 distancell 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 Codeint 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 approachimport 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 approachusing 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 approachimport mathN = 100001M = int(math.log2(N)) + 1# Keeps the track of 2^i ancestorsanc = [[0] * M for i in range(N)]# Keeps the track of sum of path from# 2^i ancestor to current nodeval = [[0] * M for i in range(N)]# Stores the depth for each nodedepth = [0] * N# Function to build tree to find the# LCA of the two nodesdef 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 distancedef 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 TreeN = 7tree = [[] 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[] arraybuild(tree, 1, 0, 0)u=6v=5# Find maximum distance between two nodesprint(findMaxPath(u, v))#This code is contributed by Potta Lokesh |
Output:
9
Time Complexity: O(N*log(N))
Auxiliary Space: O(N*log(N))
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
