text: Find the number of pair of Ideal nodes in a given tree | C # implementation of the above 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: using System ; using System . Collections . Generic ; class GFG { static readonly int N = 100005 ; static int n , k ; static List < int > [ ] al = new List < int > [ N ] ; static long Ideal_pair ; static long [ ] bit = new long [ N ] ; static bool [ ] root_node = new bool [ 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 ] . Count ; i ++ ) dfs ( al [ node ] [ 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 List < int > ( ) ; initialise ( ) ; Add_Edge ( 1 , 2 ) ; Add_Edge ( 1 , 3 ) ; Add_Edge ( 3 , 4 ) ; Add_Edge ( 3 , 5 ) ; Add_Edge ( 3 , 6 ) ; Console . Write ( Idealpairs ( ) ) ; } }