Count of all possible Paths in a Tree such that Node X does not appear before Node Y | Maximum number of nodes ; Vector to store the tree ; Function to perform DFS Traversal ; Mark the node as visited ; Initialize the subtree size of each node as 1 ; If the node is same as A ; Mark check_subtree [ node ] as true ; Otherwise ; Iterate over the adjacent nodes ; If the adjacent node is not visited ; Update the size of the subtree of current node ; Check if the subtree of current node contains node A ; Return size of subtree of node ; Function to add edges to the tree ; Function to calculate the number of possible paths ; Stores the size of subtree of each node ; Stores which nodes are visited ; Stores if the subtree of a node contains node A ; DFS Call ; Stores the difference between total number of nodes and subtree size of an immediate child of Y lies between the path from A to B ; Iterate over the adjacent nodes B ; If the node is in the path from A to B ; Calculate the difference ; Return the final answer ; Driver Code ; Insert Edges
let NN = 3e5 ; let G = new Array ( NN + 1 ) ; function dfs ( node , A , subtree_size , visited , check_subtree ) { visited [ node ] = 1 ; subtree_size [ node ] = 1 ; if ( node == A ) { check_subtree [ node ] = 1 ; } else check_subtree [ node ] = 0 ; for ( let v = 0 ; v < G [ node ] . length ; v ++ ) { if ( visited [ G [ node ] [ v ] ] == 0 ) { subtree_size [ node ] += dfs ( G [ node ] [ v ] , A , subtree_size , visited , check_subtree ) ; check_subtree [ node ] = check_subtree [ node ] | check_subtree [ G [ node ] [ v ] ] ; } } return subtree_size [ node ] ; } function addedge ( node1 , node2 ) { G [ node1 ] . push ( node2 ) ; G [ node2 ] . push ( node1 ) ; } function numberOfPairs ( N , B , A ) { let subtree_size = new Array ( N + 1 ) ; subtree_size . fill ( 0 ) ; let visited = new Array ( N + 1 ) ; visited . fill ( 0 ) ; let check_subtree = new Array ( N + 1 ) ; check_subtree . fill ( 0 ) ; dfs ( B , A , subtree_size , visited , check_subtree ) ; let difference = 0 ; for ( let v = 0 ; v < G [ B ] . length ; v ++ ) { if ( check_subtree [ G [ B ] [ v ] ] > 0 ) { difference = N - subtree_size [ G [ B ] [ v ] ] ; break ; } } return ( N * ( N - 1 ) ) - difference * ( subtree_size [ A ] ) ; } let N = 9 ; let X = 5 , Y = 3 ; for ( let i = 0 ; i < G . length ; i ++ ) G [ i ] = [ ] ; addedge ( 0 , 2 ) ; addedge ( 1 , 2 ) ; addedge ( 2 , 3 ) ; addedge ( 3 , 4 ) ; addedge ( 4 , 6 ) ; addedge ( 4 , 5 ) ; addedge ( 5 , 7 ) ; addedge ( 5 , 8 ) ; document . write ( numberOfPairs ( N , Y , X ) ) ;