Recuento de subárboles posibles de un árbol N-ario

Dado un árbol N-ario que consta de N Nodes con valores de 0 a (N – 1) , la tarea es encontrar el número total de subárboles presentes en el árbol dado. Dado que el recuento puede ser muy grande, imprima el módulo de recuento 1000000007 .

Ejemplos:

Entrada: N = 3
           0
        / 
     1
   /
2
Salida: 7
Explicación:
El número total de Nodes de subárboles son {}, {0}, {1}, {2}, {0, 1}, {1, 2}, { 0, 1, 2}. 

Entrada: N = 2
        0
     /
  1
Salida: 4

Enfoque: El enfoque para resolver el problema dado es realizar DFS Traversal en el árbol dado. Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos contar como 0 , para almacenar el recuento del número total de subárboles presentes en el árbol dado.
• Declare una función DFS(int src, int parent) para contar el número de subárboles para el Node src y realice las siguientes operaciones: 
  • Inicialice una variable, diga res como 1 .
  • Recorra la lista de adyacencia del Node actual y si el Node en la lista de adyacencia , digamos que X no es el mismo que el Node principal , luego llame recursivamente a la función DFS para el Node X y el Node src como el Node principal como DFS (X, origen) .
  • Deje que el valor devuelto a la llamada recursiva anterior sea value , luego actualice el valor de res como (res * (value + 1)) % (10 ⁹ + 7) .
  • Actualice el valor de count como (count + res) % (10 ⁹ + 7) .
  • Devuelve el valor de res de cada llamada recursiva.
• Llame a la función DFS() para el Node raíz 1 .
• Después de completar los pasos anteriores, imprima el valor de conteo como resultado.

A continuación se muestra la implementación del enfoque anterior:

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

// Java program of above approach
import java.util.*;
 
class GFG{
     
static int MAX = 300004;
 
// Adjacency list to
// represent the graph
static ArrayList<ArrayList<Integer>> graph;
static long mod = (long)1e9 + 7;
  
// Stores the count of subtrees
// possible from given N-ary Tree
static int ans = 0;
  
// Utility function to count the number of
// subtrees possible from given N-ary Tree
static int countSubtreesUtil(int cur, int par)
{
     
    // Stores the count of subtrees
    // when cur node is the root
    int res = 1;
  
    // Traverse the adjacency list
    for(int i = 0;
            i < graph.get(cur).size(); i++)
    {
  
        // Iterate over every ancestor
        int v = graph.get(cur).get(i);
  
        if (v == par)
            continue;
  
        // Calculate product of the number
        // of subtrees for each child node
        res = (int)((res * (countSubtreesUtil(
                 v, cur) + 1)) % mod);
    }
  
    // Update the value of ans
    ans = (int)((ans + res) % mod);
  
    // Return the resultant count
    return res;
}
  
// Function to count the number of
// subtrees in the given tree
static void countSubtrees(int N, int[][] adj)
{
     
    // Initialize an adjacency matrix
    for(int i = 0; i < N - 1; i++)
    {
        int a = adj[i][0];
        int b = adj[i][1];
  
        // Add the edges
        graph.get(a).add(b);
        graph.get(b).add(a);
    }
  
    // Function Call to count the
    // number of subtrees possible
    countSubtreesUtil(1, 1);
  
    // Print count of subtrees
   System.out.println(ans + 1);
}
 
// Driver code
public static void main(String[] args)
{
    int N = 3;
     
    int[][] adj = { { 0, 1 }, { 1, 2 } };
     
    graph = new ArrayList<>();
     
    for(int i = 0; i < MAX; i++)
        graph.add(new ArrayList<>());
     
    countSubtrees(N, adj);
}
}
 
// This code is contributed by offbeat

# Python3 program of the above approach
MAX = 300004
 
# Adjacency list to
# represent the graph
graph = [[] for i in range(MAX)]
mod = 10**9 + 7
 
# Stores the count of subtrees
# possible from given N-ary Tree
ans = 0
 
# Utility function to count the number of
# subtrees possible from given N-ary Tree
def countSubtreesUtil(cur, par):
    global mod, ans
     
    # Stores the count of subtrees
    # when cur node is the root
    res = 1
 
    # Traverse the adjacency list
    for i in range(len(graph[cur])):
 
        # Iterate over every ancestor
        v = graph[cur][i]
 
        if (v == par):
            continue
 
        # Calculate product of the number
        # of subtrees for each child node
        res = (res * (countSubtreesUtil(v, cur)+ 1)) % mod
 
    # Update the value of ans
    ans = (ans + res) % mod
 
    # Return the resultant count
    return res
 
# Function to count the number of
# subtrees in the given tree
def countSubtrees(N, adj):
   
    # Initialize an adjacency matrix
    for i in range(N-1):
        a = adj[i][0]
        b = adj[i][1]
 
        # Add the edges
        graph[a].append(b)
        graph[b].append(a)
 
    # Function Call to count the
    # number of subtrees possible
    countSubtreesUtil(1, 1)
 
    # Print count of subtrees
    print (ans + 1)
 
# Driver Code
if __name__ == '__main__':
    N = 3
 
    adj = [ [ 0, 1 ], [ 1, 2 ] ]
 
    countSubtrees(N, adj)
 
# This code is contributed by mohit kumar 29.

// C# program of above approach
using System;
using System.Collections.Generic;
 
public class GFG
{
 
    static int MAX = 300004;
 
    // Adjacency list to
    // represent the graph
    static List<List<int>> graph;
    static long mod = (long) 1e9 + 7;
 
    // Stores the count of subtrees
    // possible from given N-ary Tree
    static int ans = 0;
 
    // Utility function to count the number of
    // subtrees possible from given N-ary Tree
    static int countSubtreesUtil(int cur, int par) {
 
        // Stores the count of subtrees
        // when cur node is the root
        int res = 1;
 
        // Traverse the adjacency list
        for (int i = 0; i < graph[cur].Count; i++) {
 
            // Iterate over every ancestor
            int v = graph[cur][i];
 
            if (v == par)
                continue;
 
            // Calculate product of the number
            // of subtrees for each child node
            res = (int) ((res * (countSubtreesUtil(v, cur) + 1)) % mod);
        }
 
        // Update the value of ans
        ans = (int) ((ans + res) % mod);
 
        // Return the resultant count
        return res;
    }
 
    // Function to count the number of
    // subtrees in the given tree
    static void countSubtrees(int N, int[,] adj) {
 
        // Initialize an adjacency matrix
        for (int i = 0; i < N - 1; i++) {
            int a = adj[i,0];
            int b = adj[i,1];
 
            // Add the edges
            graph[a].Add(b);
            graph[b].Add(a);
        }
 
        // Function Call to count the
        // number of subtrees possible
        countSubtreesUtil(1, 1);
 
        // Print count of subtrees
        Console.WriteLine(ans + 1);
    }
 
    // Driver code
    public static void Main(String[] args) {
        int N = 3;
 
        int[,] adj = { { 0, 1 }, { 1, 2 } };
 
        graph = new List<List<int>>();
 
         
for (int i = 0; i < MAX; i++)
            graph.Add(new List<int>());
        countSubtrees(N, adj);
    }
}
 
// This code is contributed by Amit Katiyar

<script>
 
// Javascript program of the above approach
 
var MAX = 300004;
 
// Adjacency list to
// represent the graph
var graph = Array.from(Array(MAX),()=>new Array());
var mod = 1000000007;
 
// Stores the count of subtrees
// possible from given N-ary Tree
var ans = 0;
 
// Utility function to count the number of
// subtrees possible from given N-ary Tree
function countSubtreesUtil(cur, par)
{
    // Stores the count of subtrees
    // when cur node is the root
    var res = 1;
 
    // Traverse the adjacency list
    for (var i = 0;
         i < graph[cur].length; i++) {
 
        // Iterate over every ancestor
        var v = graph[cur][i];
 
        if (v == par)
            continue;
 
        // Calculate product of the number
        // of subtrees for each child node
        res = (res
               * (countSubtreesUtil(
                      v, cur)
                  + 1))
              % mod;
    }
 
    // Update the value of ans
    ans = (ans + res) % mod;
 
    // Return the resultant count
    return res;
}
 
// Function to count the number of
// subtrees in the given tree
function countSubtrees(N, adj)
{
    // Initialize an adjacency matrix
    for (var i = 0; i < N - 1; i++) {
        var a = adj[i][0];
        var b = adj[i][1];
 
        // Add the edges
        graph[a].push(b);
        graph[b].push(a);
    }
 
    // Function Call to count the
    // number of subtrees possible
    countSubtreesUtil(1, 1);
 
    // Print count of subtrees
    document.write( ans + 1);
}
 
// Driver Code
var N = 3;
var adj
    = [[ 0, 1 ], [1, 2 ]];
countSubtrees(N, adj);
 
// This code is contributed by itsok.
</script>

7

Complejidad temporal: O(N)
Espacio auxiliar: O(N)