Queries to find the count of shortest paths in a Tree that contains a given edge | Javascript implementation for the above approach ; Adjacency list to represent the tree ; Number of vertices ; Mark visited / unvisited vertices ; Stores the subtree size of the corresponding nodes ; Function to create an edge between two vertices ; Add a to b 's list ; Add b to a 's list ; Function to perform DFS ; Mark the vertex visited ; Include the node in the subtree ; Traverse all its children ; Function to print the required number of paths ; Number of vertices ; Calling modified dfs function ; Count pairs of vertices in the tree
var sz = 100005 ; var tree = Array . from ( Array ( sz ) , ( ) => Array ( ) ) var n ; var vis = Array ( sz ) ; var subtreeSize = Array ( sz ) ; function addEdge ( a , b ) { tree [ a ] . push ( b ) ; tree [ b ] . push ( a ) ; } function dfs ( x ) { vis [ x ] = true ; subtreeSize [ x ] = 1 ; tree [ x ] . forEach ( i => { if ( ! vis [ i ] ) { dfs ( i ) ; subtreeSize [ x ] += subtreeSize [ i ] ; } } ) ; } function countPairs ( a , b ) { var sub = Math . min ( subtreeSize [ a ] , subtreeSize [ b ] ) ; document . write ( sub * ( n - sub ) + " " ) ; } n = 6 ; addEdge ( 0 , 1 ) ; addEdge ( 0 , 2 ) ; addEdge ( 1 , 3 ) ; addEdge ( 3 , 4 ) ; addEdge ( 3 , 5 ) ; dfs ( 0 ) ; countPairs ( 1 , 3 ) ; countPairs ( 0 , 2 ) ;