Find the number of pair of Ideal nodes in a given tree | Javascript 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
let N = 100005 ; let n , k ; let al = new Array ( N ) . fill ( 0 ) . map ( ( t ) => [ ] ) ; let Ideal_pair ; let bit = new Array ( N ) ; let root_node = new Array ( N ) ; function bit_q ( i , j ) { let 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 ; } function bit_up ( i , diff ) { while ( i <= n ) { bit [ i ] += diff ; i += i & - i ; } } function dfs ( node ) { Ideal_pair += bit_q ( Math . max ( 1 , node - k ) , Math . min ( n , node + k ) ) ; bit_up ( node , 1 ) ; for ( let i = 0 ; i < al [ node ] . length ; i ++ ) dfs ( al [ node ] [ i ] ) ; bit_up ( node , - 1 ) ; } function initialise ( ) { Ideal_pair = 0 ; for ( let i = 0 ; i <= n ; i ++ ) { root_node [ i ] = true ; bit [ i ] = 0 ; } } function Add_Edge ( x , y ) { al [ x ] . push ( y ) ; root_node [ y ] = false ; } function Idealpairs ( ) { let r = - 1 ; for ( let i = 1 ; i <= n ; i ++ ) if ( root_node [ i ] ) { r = i ; break ; } dfs ( r ) ; return Ideal_pair ; } n = 6 , k = 3 ; initialise ( ) ; Add_Edge ( 1 , 2 ) ; Add_Edge ( 1 , 3 ) ; Add_Edge ( 3 , 4 ) ; Add_Edge ( 3 , 5 ) ; Add_Edge ( 3 , 6 ) ; document . write ( Idealpairs ( ) ) ;