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
NN = int ( 3e5 ) NEW_LINE G = [ ] NEW_LINE for i in range ( NN + 1 ) : NEW_LINE INDENT G . append ( [ ] ) NEW_LINE DEDENT def dfs ( node , A , subtree_size , visited , check_subtree ) : NEW_LINE INDENT visited [ node ] = True NEW_LINE subtree_size [ node ] = 1 NEW_LINE if ( node == A ) : NEW_LINE INDENT check_subtree [ node ] = True NEW_LINE DEDENT else : NEW_LINE INDENT check_subtree [ node ] = False NEW_LINE DEDENT for v in G [ node ] : NEW_LINE INDENT if ( not visited [ v ] ) : NEW_LINE INDENT subtree_size [ node ] += dfs ( v , A , subtree_size , visited , check_subtree ) NEW_LINE check_subtree [ node ] = ( check_subtree [ node ] check_subtree [ v ] ) NEW_LINE DEDENT DEDENT return subtree_size [ node ] NEW_LINE DEDENT def addedge ( node1 , node2 ) : NEW_LINE INDENT G [ node1 ] += [ node2 ] NEW_LINE G [ node2 ] += [ node1 ] NEW_LINE DEDENT def numberOfPairs ( N , B , A ) : NEW_LINE INDENT subtree_size = [ 0 ] * ( N + 1 ) NEW_LINE visited = [ 0 ] * ( N + 1 ) NEW_LINE check_subtree = [ 0 ] * ( N + 1 ) NEW_LINE dfs ( B , A , subtree_size , visited , check_subtree ) NEW_LINE difference = 0 NEW_LINE for v in G [ B ] : NEW_LINE INDENT if ( check_subtree [ v ] ) : NEW_LINE INDENT difference = N - subtree_size [ v ] NEW_LINE break NEW_LINE DEDENT DEDENT return ( ( N * ( N - 1 ) ) - difference * ( subtree_size [ A ] ) ) NEW_LINE DEDENT N = 9 NEW_LINE X = 5 NEW_LINE Y = 3 NEW_LINE addedge ( 0 , 2 ) NEW_LINE addedge ( 1 , 2 ) NEW_LINE addedge ( 2 , 3 ) NEW_LINE addedge ( 3 , 4 ) NEW_LINE addedge ( 4 , 6 ) NEW_LINE addedge ( 4 , 5 ) NEW_LINE addedge ( 5 , 7 ) NEW_LINE addedge ( 5 , 8 ) NEW_LINE print ( numberOfPairs ( N , Y , X ) ) NEW_LINE