Queries to find sum of distance of a given node to every leaf node in a Weighted Tree | JavaScript 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 ) ;
class pair { constructor ( f , s ) { this . first = f ; this . second = s ; } } let N = 1e5 + 5 ; let v = [ ] ; let dp = new Array ( N ) ; let leaves = new Array ( N ) ; for ( let i = 0 ; i < N ; i ++ ) { dp [ i ] = 0 ; leaves [ i ] = 0 ; } let n ; function dfs ( a , par ) { let leaf = 1 ; for ( let i = 0 ; i < v [ a ] . length ; i ++ ) { if ( v [ a ] [ i ] . first == par ) continue ; leaf = 0 ; dfs ( v [ a ] [ i ] . first , a ) ; } if ( leaf == 1 ) { leaves [ a ] += 1 ; } else { for ( let i = 0 ; i < v [ a ] . length ; i ++ ) { if ( v [ a ] [ i ] . first == par ) continue ; leaves [ a ] += leaves [ v [ a ] [ i ] . first ] ; dp [ a ] = dp [ a ] + dp [ v [ a ] [ i ] . first ] + leaves [ v [ a ] [ i ] . first ] * v [ a ] [ i ] . second ; } } } function dfs2 ( a , par ) { for ( let i = 0 ; i < v [ a ] . length ; i ++ ) { if ( v [ a ] [ i ] . first == par ) continue ; let leafOutside = leaves [ a ] - leaves [ v [ a ] [ i ] . first ] ; dp [ v [ a ] [ i ] . first ] += ( dp [ a ] - dp [ v [ a ] [ i ] . first ] ) ; dp [ v [ a ] [ i ] . first ] += v [ a ] [ i ] . second * ( leafOutside - leaves [ v [ a ] [ i ] . first ] ) ; leaves [ v [ a ] [ i ] . first ] += leafOutside ; dfs2 ( v [ a ] [ i ] . first , a ) ; } } function answerQueries ( queries ) { dfs ( 1 , 0 ) ; dfs2 ( 1 , 0 ) ; for ( let i = 0 ; i < queries . length ; i ++ ) { document . write ( dp [ queries [ i ] ] + " " ) ; } } n = 5 ; v = [ ] ; for ( let i = 0 ; i <= n ; i ++ ) v . push ( [ ] ) ; v [ 1 ] . push ( new pair ( 4 , 4 ) ) ; v [ 4 ] . push ( new pair ( 1 , 4 ) ) ; v [ 1 ] . push ( new pair ( 2 , 2 ) ) ; v [ 2 ] . push ( new pair ( 1 , 2 ) ) ; v [ 2 ] . push ( new pair ( 3 , 3 ) ) ; v [ 3 ] . push ( new pair ( 2 , 3 ) ) ; v [ 2 ] . push ( new pair ( 5 , 5 ) ) ; v [ 5 ] . push ( new pair ( 2 , 5 ) ) ; let queries = [ 1 , 3 , 5 ] ; answerQueries ( queries ) ;