Find the number of distinct pairs of vertices which have a distance of exactly k in a tree | Python3 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
N = 5005 NEW_LINE n , k = 0 , 0 NEW_LINE gr = [ [ ] for i in range ( N ) ] NEW_LINE d = [ [ 0 for i in range ( 505 ) ] for i in range ( N ) ] NEW_LINE ans = 0 NEW_LINE def Add_edge ( x , y ) : NEW_LINE INDENT gr [ x ] . append ( y ) NEW_LINE gr [ y ] . append ( x ) NEW_LINE DEDENT def dfs ( v , par ) : NEW_LINE INDENT global ans NEW_LINE d [ v ] [ 0 ] = 1 NEW_LINE for i in gr [ v ] : NEW_LINE INDENT if ( i != par ) : NEW_LINE INDENT dfs ( i , v ) NEW_LINE for j in range ( 1 , k + 1 ) : NEW_LINE INDENT ans += d [ i ] [ j - 1 ] * d [ v ] [ k - j ] NEW_LINE DEDENT for j in range ( 1 , k + 1 ) : NEW_LINE INDENT d [ v ] [ j ] += d [ i ] [ j - 1 ] NEW_LINE DEDENT DEDENT DEDENT DEDENT n = 5 NEW_LINE k = 2 NEW_LINE Add_edge ( 1 , 2 ) NEW_LINE Add_edge ( 2 , 3 ) NEW_LINE Add_edge ( 3 , 4 ) NEW_LINE Add_edge ( 2 , 5 ) NEW_LINE dfs ( 1 , 0 ) NEW_LINE print ( ans ) NEW_LINE