Queries to find sum of distance of a given node to every leaf node in a Weighted Tree | C # program for the above problem ; MAX size ; Graph with { destination , weight } ; For storing the sum for ith node ; Leaves in subtree of ith . ; dfs to find sum of distance of leaves in the subtree of a node ; flag is the node is leaf or not ; Skipping if parent ; Setting flag to false ; Doing dfs call ; Doing calculation in postorder . ; If the node is leaf then we just increment the no . of leaves under the subtree of a node ; Adding num of leaves ; Calculating answer for the sum in the subtree ; dfs function to find the sum of distance of leaves outside the subtree ; Number of leaves other than the leaves in the subtree of i ; Adding the contribution of leaves outside to the ith node ; Adding the leafs outside to ith node 's leaves. ; Calculating the sum of distance of leaves in the subtree of a node assuming the root of the tree is 1 ; Calculating the sum of distance of leaves outside the subtree of node assuming the root of the tree is 1 ; Answering the queries ; 1 ( 4 ) / \ ( 2 ) / \ 4 2 ( 5 ) / \ ( 3 ) / \ 5 3 ; initialising tree ; System . out . println ( v ) ;
using System ; using System . Collections . Generic ; class GFG { static int N = 100005 ; static List < List < Tuple < int , int > > > v = new List < List < Tuple < int , int > > > ( ) ; static int [ ] dp = new int [ N ] ; static int [ ] leaves = new int [ N ] ; static void dfs ( int a , int par ) { bool leaf = true ; foreach ( Tuple < int , int > i in v [ a ] ) { if ( i . Item1 == par ) continue ; leaf = false ; dfs ( i . Item1 , a ) ; } if ( leaf == true ) { leaves [ a ] += 1 ; } else { foreach ( Tuple < int , int > i in v [ a ] ) { if ( i . Item1 == par ) continue ; leaves [ a ] += leaves [ i . Item1 ] ; dp [ a ] = ( dp [ a ] + dp [ i . Item1 ] + leaves [ i . Item1 ] * i . Item2 ) ; } } } static void dfs2 ( int a , int par ) { foreach ( Tuple < int , int > i in v [ a ] ) { if ( i . Item1 == par ) continue ; int leafOutside = leaves [ a ] - leaves [ i . Item1 ] ; dp [ i . Item1 ] += ( dp [ a ] - dp [ i . Item1 ] ) ; dp [ i . Item1 ] += i . Item2 * ( leafOutside - leaves [ i . Item1 ] ) ; leaves [ i . Item1 ] += leafOutside ; dfs2 ( i . Item1 , a ) ; } } static void answerQueries ( List < int > queries ) { dfs ( 1 , 0 ) ; dfs2 ( 1 , 0 ) ; for ( int i = 0 ; i < queries . Count ; i ++ ) Console . WriteLine ( dp [ queries [ i ] ] ) ; } static void Main ( ) { for ( int i = 0 ; i < N ; i ++ ) { v . Add ( new List < Tuple < int , int > > ( ) ) ; } v [ 1 ] . Add ( new Tuple < int , int > ( 4 , 4 ) ) ; v [ 4 ] . Add ( new Tuple < int , int > ( 1 , 4 ) ) ; v [ 1 ] . Add ( new Tuple < int , int > ( 2 , 2 ) ) ; v [ 2 ] . Add ( new Tuple < int , int > ( 1 , 2 ) ) ; v [ 2 ] . Add ( new Tuple < int , int > ( 3 , 3 ) ) ; v [ 3 ] . Add ( new Tuple < int , int > ( 2 , 3 ) ) ; v [ 2 ] . Add ( new Tuple < int , int > ( 5 , 5 ) ) ; v [ 5 ] . Add ( new Tuple < int , int > ( 2 , 5 ) ) ; List < int > queries = new List < int > { 1 , 3 , 5 } ; answerQueries ( queries ) ; } }