Count of subtrees possible from an N | Javascript 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
var MAX = 300004 ; var graph = Array . from ( Array ( MAX ) , ( ) => new Array ( ) ) ; var mod = 1000000007 ; var ans = 0 ; function countSubtreesUtil ( cur , par ) { var res = 1 ; for ( var i = 0 ; i < graph [ cur ] . length ; i ++ ) { var v = graph [ cur ] [ i ] ; if ( v == par ) continue ; res = ( res * ( countSubtreesUtil ( v , cur ) + 1 ) ) % mod ; } ans = ( ans + res ) % mod ; return res ; } function countSubtrees ( N , adj ) { for ( var i = 0 ; i < N - 1 ; i ++ ) { var a = adj [ i ] [ 0 ] ; var b = adj [ i ] [ 1 ] ; graph [ a ] . push ( b ) ; graph [ b ] . push ( a ) ; } countSubtreesUtil ( 1 , 1 ) ; document . write ( ans + 1 ) ; } var N = 3 ; var adj = [ [ 0 , 1 ] , [ 1 , 2 ] ] ; countSubtrees ( N , adj ) ;