Count pairs of nodes having minimum distance between them equal to the difference of their distances from root | C ++ program for the above approach ; Stores the count of pairs ; Store the adjacency list of the connecting vertex ; Function for theto perform DFS traversal of the given tree ; Traverse the adjacency list of the current node u ; If the current node is the parent node ; Add number of ancestors , which is same as depth of the node ; Function for DFS traversal of the given tree ; Print the result ; Function to find the count of pairs such that the minimum distance between them is equal to the difference between distance of the nodes from root node ; Add edges to adj [ ] ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; long long ans = 0 ; vector < int > adj [ int ( 1e5 ) + 1 ] ; void dfsUtil ( int u , int par , int depth ) { for ( auto it : adj [ u ] ) { if ( it != par ) { dfsUtil ( it , u , depth + 1 ) ; } } ans += depth ; } void dfs ( int u , int par , int depth ) { dfsUtil ( u , par , depth ) ; cout << ans << endl ; } void countPairs ( vector < vector < int > > edges ) { for ( int i = 0 ; i < edges . size ( ) ; i ++ ) { int u = edges [ i ] [ 0 ] ; int v = edges [ i ] [ 1 ] ; adj [ u ] . push_back ( v ) ; adj [ v ] . push_back ( u ) ; } dfs ( 1 , 1 , 1 ) ; } int main ( ) { vector < vector < int > > edges = { { 1 , 2 } , { 1 , 3 } , { 2 , 4 } } ; countPairs ( edges ) ; return 0 ; }