Find the number of distinct pairs of vertices which have a distance of exactly k in a tree | Javascript implementation of the approach ; To store vertices and value of k ; To store number vertices at a level i ; To store the final answer ; Function to add an edge between two nodes ; Function to find the number of distinct pairs of the vertices which have a distance of exactly k in a tree ; At level zero vertex itself is counted ; Count the pair of vertices at distance k ; For all levels count vertices ; Driver code ; Add edges ; Function call ; Required answer
let N = 5005 ; let n , k ; let gr = new Array ( N ) ; let d = new Array ( N ) ; for ( let i = 0 ; i < N ; i ++ ) { d [ i ] = new Array ( 505 ) ; for ( let j = 0 ; j < 505 ; j ++ ) { d [ i ] [ j ] = 0 ; } } let ans = 0 ; function Add_edge ( x , y ) { gr [ x ] . push ( y ) ; gr [ y ] . push ( x ) ; } function dfs ( v , par ) { d [ v ] [ 0 ] = 1 ; for ( let i = 0 ; i < gr [ v ] . length ; i ++ ) { if ( gr [ v ] [ i ] != par ) { dfs ( gr [ v ] [ i ] , v ) ; for ( let j = 1 ; j <= k ; j ++ ) ans += d [ gr [ v ] [ i ] ] [ j - 1 ] * d [ v ] [ k - j ] ; for ( let j = 1 ; j <= k ; j ++ ) d [ v ] [ j ] += d [ gr [ v ] [ i ] ] [ j - 1 ] ; } } } n = 5 ; k = 2 ; for ( let i = 0 ; i < N ; i ++ ) gr [ i ] = [ ] ; Add_edge ( 1 , 2 ) ; Add_edge ( 2 , 3 ) ; Add_edge ( 3 , 4 ) ; Add_edge ( 2 , 5 ) ; dfs ( 1 , 0 ) ; document . write ( ans ) ;