Find the number of distinct pairs of vertices which have a distance of exactly k in a tree | PHP 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
< ? php $ N = 5005 ; $ gr = array_fill ( 0 , $ N , array ( ) ) ; $ d = array_fill ( 0 , $ N , array_fill ( 0 , 505 , 0 ) ) ; $ ans = 0 ; function Add_edge ( $ x , $ y ) { global $ gr ; array_push ( $ gr [ $ x ] , $ y ) ; array_push ( $ gr [ $ y ] , $ x ) ; } function dfs ( $ v , $ par ) { global $ d , $ ans , $ k , $ gr ; $ d [ $ v ] [ 0 ] = 1 ; foreach ( $ gr [ $ v ] as & $ i ) { if ( $ i != $ par ) { dfs ( $ i , $ v ) ; for ( $ j = 1 ; $ j <= $ k ; $ j ++ ) $ ans += $ d [ $ i ] [ $ j - 1 ] * $ d [ $ v ] [ $ k - $ j ] ; for ( $ j = 1 ; $ j <= $ k ; $ j ++ ) $ d [ $ v ] [ $ j ] += $ d [ $ i ] [ $ j - 1 ] ; } } } $ n = 5 ; $ k = 2 ; Add_edge ( 1 , 2 ) ; Add_edge ( 2 , 3 ) ; Add_edge ( 3 , 4 ) ; Add_edge ( 2 , 5 ) ; dfs ( 1 , 0 ) ; echo $ ans ; ? >