Find the number of pair of Ideal nodes in a given tree | Java implementation of the approach ; Adjacency list ; bit : bit array i and j are starting and ending index INCLUSIVE ; bit : bit array n : size of bit array i is the index to be updated diff is ( new_val - old_val ) ; DFS function to find ideal pairs ; Function for initialisation ; Function to add an edge ; Function to find number of ideal pairs ; Find root of the tree ; Driver code ; Add edges ; Function call
import java . util . * ; class GFG { static final int N = 100005 ; static int n , k ; @ SuppressWarnings ( " unchecked " ) static Vector < Integer > [ ] al = new Vector [ N ] ; static long Ideal_pair ; static long [ ] bit = new long [ N ] ; static boolean [ ] root_node = new boolean [ N ] ; static long bit_q ( int i , int j ) { long sum = 0 ; while ( j > 0 ) { sum += bit [ j ] ; j -= ( j & ( j * - 1 ) ) ; } i -- ; while ( i > 0 ) { sum -= bit [ i ] ; i -= ( i & ( i * - 1 ) ) ; } return sum ; } static void bit_up ( int i , long diff ) { while ( i <= n ) { bit [ i ] += diff ; i += i & - i ; } } static void dfs ( int node ) { Ideal_pair += bit_q ( Math . max ( 1 , node - k ) , Math . min ( n , node + k ) ) ; bit_up ( node , 1 ) ; for ( int i = 0 ; i < al [ node ] . size ( ) ; i ++ ) dfs ( al [ node ] . get ( i ) ) ; bit_up ( node , - 1 ) ; } static void initialise ( ) { Ideal_pair = 0 ; for ( int i = 0 ; i <= n ; i ++ ) { root_node [ i ] = true ; bit [ i ] = 0 ; } } static void Add_Edge ( int x , int y ) { al [ x ] . add ( y ) ; root_node [ y ] = false ; } static long Idealpairs ( ) { int r = - 1 ; for ( int i = 1 ; i <= n ; i ++ ) if ( root_node [ i ] ) { r = i ; break ; } dfs ( r ) ; return Ideal_pair ; } public static void main ( String [ ] args ) { n = 6 ; k = 3 ; for ( int i = 0 ; i < al . length ; i ++ ) al [ i ] = new Vector < Integer > ( ) ; initialise ( ) ; Add_Edge ( 1 , 2 ) ; Add_Edge ( 1 , 3 ) ; Add_Edge ( 3 , 4 ) ; Add_Edge ( 3 , 5 ) ; Add_Edge ( 3 , 6 ) ; System . out . print ( Idealpairs ( ) ) ; } }