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
using System ; using System . Collections ; using System . Collections . Generic ; class GFG { static int sz = 100005 ; static int n ; static ArrayList [ ] tree = new ArrayList [ sz ] ; static int [ ] subtree_size = new int [ sz ] ; static int [ ] vis = new int [ sz ] ; static void addEdge ( int a , int b ) { tree [ a ] . Add ( b ) ; tree [ b ] . Add ( a ) ; } static int dfs ( int node ) { vis [ node ] = 1 ; subtree_size [ node ] = 1 ; foreach ( int child in tree [ node ] ) { if ( vis [ child ] == 0 ) { subtree_size [ node ] += dfs ( child ) ; } } return subtree_size [ node ] ; } static void contribution ( int node , ref int ans ) { vis [ node ] = 1 ; foreach ( int child in tree [ node ] ) { if ( vis [ child ] == 0 ) { ans += ( subtree_size [ child ] * ( n - subtree_size [ child ] ) ) ; contribution ( child , ref ans ) ; } } } static int getSum ( ) { Array . Fill ( vis , 0 ) ; dfs ( 0 ) ; int ans = 0 ; Array . Fill ( vis , 0 ) ; contribution ( 0 , ref ans ) ; return ans ; } public static void Main ( ) { n = 5 ; for ( int i = 0 ; i < sz ; i ++ ) { tree [ i ] = new ArrayList ( ) ; } addEdge ( 0 , 1 ) ; addEdge ( 0 , 2 ) ; addEdge ( 1 , 3 ) ; addEdge ( 1 , 4 ) ; Console . Write ( getSum ( ) ) ; } }