text: Find the number of pair of Ideal nodes in a given tree | C ++ 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
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  100005 NEW_LINE int n , k ; vector < int > al [ N ] ; long long Ideal_pair ; long long bit [ N ] ; bool root_node [ N ] ; long long bit_q ( int i , int j ) { long long sum = 0ll ; while ( j > 0 ) { sum += bit [ j ] ; j -= ( j & ( j * -1 ) ) ; } i -- ; while ( i > 0 ) { sum -= bit [ i ] ; i -= ( i & ( i * -1 ) ) ; } return sum ; } void bit_up ( int i , long long diff ) { while ( i <= n ) { bit [ i ] += diff ; i += i & - i ; } } void dfs ( int node ) { Ideal_pair += bit_q ( max ( 1 , node - k ) , min ( n , node + k ) ) ; bit_up ( node , 1 ) ; for ( int i = 0 ; i < al [ node ] . size ( ) ; i ++ ) dfs ( al [ node ] [ i ] ) ; bit_up ( node , -1 ) ; } void initialise ( ) { Ideal_pair = 0 ; for ( int i = 0 ; i <= n ; i ++ ) { root_node [ i ] = true ; bit [ i ] = 0LL ; } } void Add_Edge ( int x , int y ) { al [ x ] . push_back ( y ) ; root_node [ y ] = false ; } long long Idealpairs ( ) { int r = -1 ; for ( int i = 1 ; i <= n ; i ++ ) if ( root_node [ i ] ) { r = i ; break ; } dfs ( r ) ; return Ideal_pair ; } int main ( ) { 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 ) ; cout << Idealpairs ( ) ; return 0 ; }