Horje
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:

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

Output: 

9

 

Time Complexity: O(N*log(N))
Auxiliary Space: O(N*log(N))


 


Reffered: https://www.geeksforgeeks.org

Tree

Related
Count number of nodes in a complete Binary Tree Count number of nodes in a complete Binary Tree
Minimum path need to reverse to reach each node in a tree from each vertex Minimum path need to reverse to reach each node in a tree from each vertex
ZigZag Level Order Traversal of an N-ary Tree ZigZag Level Order Traversal of an N-ary Tree
Minimum distance between two given nodes in an N-ary tree Minimum distance between two given nodes in an N-ary tree
Check if given inorder and preorder traversals are valid for any Binary Tree without building the tree Check if given inorder and preorder traversals are valid for any Binary Tree without building the tree

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 13



 

Horje