Disjoint Set Union on trees | Set 2 | CPP code to find maximum possible cost ; Edge structure ; v : Adjacency list representation of Graph p : stores parents of nodes ; Weighted union - find with path compression ; DFS is called to generate parent of a node from adjacency list representation ; Utility function for Union ; Fixed ' i ' as AND ; Generating supermasks of ' i ' ; Checking whether p [ x ] is also a supermask of i . ; Keep track of maximum size of subtree ; Storing maximum cost of subtree with a given AND ; Separating components which are merged during Union operation for next AND value . ; Driver code ; Number of nodes ; Taking edges as input and put them in adjacency list representation ; Initializing parent vertex of '1' as '1' ; Call DFS to generate ' p ' array
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  100010 NEW_LINE struct Edge { int u , v ; } ; vector < int > v [ N ] ; int p [ N ] ; struct wunionfind { int id [ N ] , sz [ N ] ; void initial ( int n ) { for ( int i = 1 ; i <= n ; i ++ ) id [ i ] = i , sz [ i ] = 1 ; } int Root ( int idx ) { int i = idx ; while ( i != id [ i ] ) id [ i ] = id [ id [ i ] ] , i = id [ i ] ; return i ; } void Union ( int a , int b ) { int i = Root ( a ) , j = Root ( b ) ; if ( i != j ) { if ( sz [ i ] >= sz [ j ] ) { id [ j ] = i , sz [ i ] += sz [ j ] ; sz [ j ] = 0 ; } else { id [ i ] = j , sz [ j ] += sz [ i ] ; sz [ i ] = 0 ; } } } } ; wunionfind W ; void dfs ( int u , int parent ) { for ( int i = 0 ; i < v [ u ] . size ( ) ; i ++ ) { int j = v [ u ] [ i ] ; if ( j != parent ) { p [ j ] = u ; dfs ( j , u ) ; } } } int UnionUtil ( int n ) { int ans = 0 ; for ( int i = 1 ; i <= n ; i ++ ) { int maxi = 1 ; for ( int x = i ; x <= n ; x = ( i | ( x + 1 ) ) ) { int y = p [ x ] ; if ( ( y & i ) == i ) { W . Union ( x , y ) ; maxi = max ( maxi , W . sz [ W . Root ( x ) ] ) ; } } ans = max ( ans , maxi * i ) ; for ( int x = i ; x <= n ; x = ( i | ( x + 1 ) ) ) { W . sz [ x ] = 1 ; W . id [ x ] = x ; } } return ans ; } int main ( ) { int n , i ; n = 6 ; W . initial ( n ) ; Edge e [ ] = { { 1 , 2 } , { 2 , 3 } , { 3 , 4 } , { 3 , 5 } , { 5 , 6 } } ; int q = sizeof ( e ) / sizeof ( e [ 0 ] ) ; for ( i = 0 ; i < q ; i ++ ) { int x , y ; x = e [ i ] . u , y = e [ i ] . v ; v [ x ] . push_back ( y ) ; v [ y ] . push_back ( x ) ; } p [ 1 ] = 1 ; dfs ( 1 , -1 ) ; int ans = UnionUtil ( n ) ; printf ( " Maximum ▁ Cost ▁ = ▁ % d STRNEWLINE " , ans ) ; return 0 ; }