Sum of lengths of all paths possible in a given tree | C ++ implementation of the approach ; Number of vertices ; Adjacency list representation of the tree ; Array that stores the subtree size ; Array to mark all the vertices which are visited ; Utility function to create an edge between two vertices ; Add a to b 's list ; Add b to a 's list ; Function to calculate the subtree size ; Mark visited ; For every adjacent node ; If not already visited ; Recursive call for the child ; Function to calculate the contribution of each edge ; Mark current node as visited ; For every adjacent node ; If it is not already visisted ; Function to return the required sum ; First pass of the dfs ; Second pass ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int sz = 1e5 ; int n ; vector < int > tree [ sz ] ; int subtree_size [ sz ] ; int vis [ sz ] ; void addEdge ( int a , int b ) { tree [ a ] . push_back ( b ) ; tree [ b ] . push_back ( a ) ; } int dfs ( int node ) { vis [ node ] = 1 ; subtree_size [ node ] = 1 ; for ( auto child : tree [ node ] ) { if ( ! vis [ child ] ) { subtree_size [ node ] += dfs ( child ) ; } } return subtree_size [ node ] ; } void contribution ( int node , int & ans ) { vis [ node ] = true ; for ( int child : tree [ node ] ) { if ( ! vis [ child ] ) { ans += ( subtree_size [ child ] * ( n - subtree_size [ child ] ) ) ; contribution ( child , ans ) ; } } } int getSum ( ) { memset ( vis , 0 , sizeof ( vis ) ) ; dfs ( 0 ) ; int ans = 0 ; memset ( vis , 0 , sizeof ( vis ) ) ; contribution ( 0 , ans ) ; return ans ; } int main ( ) { n = 5 ; addEdge ( 0 , 1 ) ; addEdge ( 0 , 2 ) ; addEdge ( 1 , 3 ) ; addEdge ( 1 , 4 ) ; cout << getSum ( ) ; return 0 ; }