Maximum weighted edge in path between two nodes in an N | C ++ implementation to find the maximum weighted edge in the simple path between two nodes in N - ary Tree ; Depths of Nodes ; Parent at every 2 ^ i level ; Maximum node at every 2 ^ i level ; Graph that stores destinations and its weight ; Function to traverse the nodes using the Depth - First Search Traversal ; Condition to check if its equal to its parent then skip ; DFS Recursive Call ; Function to find the ansector ; Loop to set every 2 ^ i distance ; Loop to calculate for each node in the N - ary tree ; Storing maximum edge ; Swaping if node a is at more depth than node b because we will always take at more depth ; Difference between the depth of the two given nodes ; Changing Node B to its parent at 2 ^ i distance ; Subtracting distance by 2 ^ i ; Take both a , b to its lca and find maximum ; Loop to find the 2 ^ ith parent that is different for both a and b i . e below the lca ; Updating ans ; Changing value to its parent ; Function to compute the Least common Ansector ; Driver Code ; Undirected tree ; Computing LCA
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int N = 100005 ; vector < int > level ( N ) ; const int LG = 20 ; vector < vector < int > > dp ( LG , vector < int > ( N ) ) ; vector < vector < int > > mx ( LG , vector < int > ( N ) ) ; vector < vector < pair < int , int > > > v ( N ) ; int n ; void dfs_lca ( int a , int par , int lev ) { dp [ 0 ] [ a ] = par ; level [ a ] = lev ; for ( auto i : v [ a ] ) { if ( i . first == par ) continue ; mx [ 0 ] [ i . first ] = i . second ; dfs_lca ( i . first , a , lev + 1 ) ; } } void find_ancestor ( ) { for ( int i = 1 ; i < LG ; i ++ ) { for ( int j = 1 ; j <= n ; j ++ ) { dp [ i ] [ j ] = dp [ i - 1 ] [ dp [ i - 1 ] [ j ] ] ; mx [ i ] [ j ] = max ( mx [ i - 1 ] [ j ] , mx [ i - 1 ] [ dp [ i - 1 ] [ j ] ] ) ; } } } int getMax ( int a , int b ) { if ( level [ b ] < level [ a ] ) swap ( a , b ) ; int ans = 0 ; int diff = level [ b ] - level [ a ] ; while ( diff > 0 ) { int log = log2 ( diff ) ; ans = max ( ans , mx [ log ] [ b ] ) ; b = dp [ log ] [ b ] ; diff -= ( 1 << log ) ; } while ( a != b ) { int i = log2 ( level [ a ] ) ; while ( i > 0 && dp [ i ] [ a ] == dp [ i ] [ b ] ) i -- ; ans = max ( ans , mx [ i ] [ a ] ) ; ans = max ( ans , mx [ i ] [ b ] ) ; a = dp [ i ] [ a ] ; b = dp [ i ] [ b ] ; } return ans ; } void compute_lca ( ) { dfs_lca ( 1 , 0 , 0 ) ; find_ancestor ( ) ; } int main ( ) { n = 5 ; v [ 1 ] . push_back ( make_pair ( 2 , 2 ) ) ; v [ 2 ] . push_back ( make_pair ( 1 , 2 ) ) ; v [ 1 ] . push_back ( make_pair ( 3 , 5 ) ) ; v [ 3 ] . push_back ( make_pair ( 1 , 5 ) ) ; v [ 3 ] . push_back ( make_pair ( 4 , 3 ) ) ; v [ 4 ] . push_back ( make_pair ( 3 , 4 ) ) ; v [ 3 ] . push_back ( make_pair ( 5 , 1 ) ) ; v [ 5 ] . push_back ( make_pair ( 3 , 1 ) ) ; compute_lca ( ) ; int queries [ ] [ 2 ] = { { 3 , 5 } , { 2 , 3 } , { 2 , 4 } } ; int q = 3 ; for ( int i = 0 ; i < q ; i ++ ) { int max_edge = getMax ( queries [ i ] [ 0 ] , queries [ i ] [ 1 ] ) ; cout << max_edge << endl ; } return 0 ; }