Count of subtrees possible from an N | C ++ program of the above approach ; Adjacency list to represent the graph ; Stores the count of subtrees possible from given N - ary Tree ; Utility function to count the number of subtrees possible from given N - ary Tree ; Stores the count of subtrees when cur node is the root ; Traverse the adjacency list ; Iterate over every ancestor ; Calculate product of the number of subtrees for each child node ; Update the value of ans ; Return the resultant count ; Function to count the number of subtrees in the given tree ; Initialize an adjacency matrix ; Add the edges ; Function Call to count the number of subtrees possible ; Print count of subtrees ; Driver Code
#include <bits/stdc++.h> NEW_LINE #define MAX  300004 NEW_LINE using namespace std ; vector < int > graph [ MAX ] ; int mod = 1e9 + 7 ; int ans = 0 ; int countSubtreesUtil ( int cur , int par ) { int res = 1 ; for ( int i = 0 ; i < graph [ cur ] . size ( ) ; i ++ ) { int v = graph [ cur ] [ i ] ; if ( v == par ) continue ; res = ( res * ( countSubtreesUtil ( v , cur ) + 1 ) ) % mod ; } ans = ( ans + res ) % mod ; return res ; } void countSubtrees ( int N , vector < pair < int , int > > & adj ) { for ( int i = 0 ; i < N - 1 ; i ++ ) { int a = adj [ i ] . first ; int b = adj [ i ] . second ; graph [ a ] . push_back ( b ) ; graph [ b ] . push_back ( a ) ; } countSubtreesUtil ( 1 , 1 ) ; cout << ans + 1 ; } int main ( ) { int N = 3 ; vector < pair < int , int > > adj = { { 0 , 1 } , { 1 , 2 } } ; countSubtrees ( N , adj ) ; return 0 ; }