Count of all possible Paths in a Tree such that Node X does not appear before Node Y | C ++ Program to implement the above approach ; 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
#include <bits/stdc++.h> NEW_LINE #define int  long long int NEW_LINE using namespace std ; const int NN = 3e5 ; vector < int > G [ NN + 1 ] ; int dfs ( int node , int A , int * subtree_size , int * visited , int * check_subtree ) { visited [ node ] = true ; subtree_size [ node ] = 1 ; if ( node == A ) { check_subtree [ node ] = true ; } else check_subtree [ node ] = false ; for ( int v : G [ node ] ) { if ( ! visited [ v ] ) { subtree_size [ node ] += dfs ( v , A , subtree_size , visited , check_subtree ) ; check_subtree [ node ] = check_subtree [ node ] | check_subtree [ v ] ; } } return subtree_size [ node ] ; } void addedge ( int node1 , int node2 ) { G [ node1 ] . push_back ( node2 ) ; G [ node2 ] . push_back ( node1 ) ; } int numberOfPairs ( int N , int B , int A ) { int subtree_size [ N + 1 ] ; int visited [ N + 1 ] ; memset ( visited , 0 , sizeof ( visited ) ) ; int check_subtree [ N + 1 ] ; dfs ( B , A , subtree_size , visited , check_subtree ) ; int difference ; for ( int v : G [ B ] ) { if ( check_subtree [ v ] ) { difference = N - subtree_size [ v ] ; break ; } } return ( N * ( N - 1 ) ) - difference * ( subtree_size [ A ] ) ; } int32_t main ( ) { int N = 9 ; int X = 5 , Y = 3 ; addedge ( 0 , 2 ) ; addedge ( 1 , 2 ) ; addedge ( 2 , 3 ) ; addedge ( 3 , 4 ) ; addedge ( 4 , 6 ) ; addedge ( 4 , 5 ) ; addedge ( 5 , 7 ) ; addedge ( 5 , 8 ) ; cout << numberOfPairs ( N , Y , X ) ; return 0 ; }