Find the number of distinct pairs of vertices which have a distance of exactly k in a tree | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  5005 NEW_LINE int n , k ; vector < int > gr [ N ] ; int d [ N ] [ 505 ] ; int ans = 0 ; void Add_edge ( int x , int y ) { gr [ x ] . push_back ( y ) ; gr [ y ] . push_back ( x ) ; } void dfs ( int v , int par ) { d [ v ] [ 0 ] = 1 ; for ( auto i : gr [ v ] ) { if ( i != par ) { dfs ( i , v ) ; for ( int j = 1 ; j <= k ; j ++ ) ans += d [ i ] [ j - 1 ] * d [ v ] [ k - j ] ; for ( int j = 1 ; j <= k ; j ++ ) d [ v ] [ j ] += d [ i ] [ j - 1 ] ; } } } int main ( ) { n = 5 , k = 2 ; Add_edge ( 1 , 2 ) ; Add_edge ( 2 , 3 ) ; Add_edge ( 3 , 4 ) ; Add_edge ( 2 , 5 ) ; dfs ( 1 , 0 ) ; cout << ans ; return 0 ; }