Recuento de subárboles de un árbol N-ario que consta de Nodes de un solo color

Dado un árbol N-ario que consiste en N Nodes y una array bordes[][] que consta de N – 1 bordes de la forma (X, Y) que denota el borde entre el Node X y el Node Y y una array col[] que consta de valores : 
 

• 0: Node sin color.
• 1: Node de color rojo.
• 2: Node de color azul.

La tarea es encontrar el número de subárboles del árbol dado que consta de solo Nodes de un solo color.
Ejemplos: 
 

Entrada: 
N = 5, col[] = {2, 0, 0, 1, 2}, 
bordes[][] = {{1, 2}, {2, 3}, {2, 4}, {2, 5}} 
Salida: 1 
Explicación: 
Un subárbol del Node 4 que es {4} no tiene vértice azul y contiene solo un vértice rojo.
Entrada: 
N = 5, col[] = {1, 0, 0, 0, 2}, 
bordes[][] = {{1, 2}, {2, 3}, {3, 4}, {4, 5}} 
Salida: 4 
Explicación: 
A continuación se muestran los subárboles con la propiedad dada: 
 

1. Subárbol con valor de Node raíz 2 {2, 3, 4, 5}
2. Subárbol con valor de Node raíz 3 {3, 4, 5}
3. Subárbol con valor de Node raíz 4 {4, 5}
4. Subárbol con valor de Node raíz 5 {5}

 

Enfoque: El problema dado se puede resolver usando el recorrido de búsqueda primero en profundidad . La idea es calcular la cantidad de Nodes rojos y azules en cada subárbol usando DFS para el árbol dado. Una vez calculado, cuente el número de subárboles que contienen solo Nodes de color azul y solo Nodes de color rojo .
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to implement DFS traversal
void Solution_dfs(int v, int color[], int red,
                  int blue, int* sub_red,
                  int* sub_blue, int* vis,
                  map<int, vector<int> >& adj,
                  int* ans)
{
 
    // Mark node v as visited
    vis[v] = 1;
 
    // Traverse Adj_List of node v
    for (int i = 0; i < adj[v].size();
         i++) {
 
        // If current node is not visited
        if (vis[adj[v][i]] == 0) {
 
            // DFS call for current node
            Solution_dfs(adj[v][i], color,
                         red, blue,
                         sub_red, sub_blue,
                         vis, adj, ans);
 
            // Count the total red and blue
            // nodes of children of its subtree
            sub_red[v] += sub_red[adj[v][i]];
            sub_blue[v] += sub_blue[adj[v][i]];
        }
    }
 
    if (color[v] == 1) {
        sub_red[v]++;
    }
 
    // Count the no. of red and blue
    // nodes in the subtree
    if (color[v] == 2) {
        sub_blue[v]++;
    }
 
    // If subtree contains all
    // red node & no blue node
    if (sub_red[v] == red
        && sub_blue[v] == 0) {
        (*ans)++;
    }
 
    // If subtree contains all
    // blue node & no red node
    if (sub_red[v] == 0
        && sub_blue[v] == blue) {
        (*ans)++;
    }
}
 
// Function to count the number of
// nodes with red color
int countRed(int color[], int n)
{
    int red = 0;
    for (int i = 0; i < n; i++) {
        if (color[i] == 1)
            red++;
    }
    return red;
}
 
// Function to count the number of
// nodes with blue color
int countBlue(int color[], int n)
{
    int blue = 0;
    for (int i = 0; i < n; i++) {
        if (color[i] == 2)
            blue++;
    }
    return blue;
}
 
// Function to create a Tree with
// given vertices
void buildTree(int edge[][2],
               map<int, vector<int> >& m,
               int n)
{
    int u, v, i;
 
    // Traverse the edge[] array
    for (i = 0; i < n - 1; i++) {
 
        u = edge[i][0] - 1;
        v = edge[i][1] - 1;
 
        // Create adjacency list
        m[u].push_back(v);
        m[v].push_back(u);
    }
}
 
// Function to count the number of
// subtree with the given condition
void countSubtree(int color[], int n,
                  int edge[][2])
{
 
    // For creating adjacency list
    map<int, vector<int> > adj;
    int ans = 0;
 
    // To store the count of subtree
    // with only blue and red color
    int sub_red[n + 3] = { 0 };
    int sub_blue[n + 3] = { 0 };
 
    // visited array for DFS Traversal
    int vis[n + 3] = { 0 };
 
    // Count the number of red
    // node in the tree
    int red = countRed(color, n);
 
    // Count the number of blue
    // node in the tree
    int blue = countBlue(color, n);
 
    // Function Call to build tree
    buildTree(edge, adj, n);
 
    // DFS Traversal
    Solution_dfs(0, color, red, blue,
                 sub_red, sub_blue,
                 vis, adj, &ans);
 
    // Print the final count
    cout << ans;
}
// Driver Code
int main()
{
    int N = 5;
    int color[] = { 1, 0, 0, 0, 2 };
    int edge[][2] = { { 1, 2 },
                      { 2, 3 },
                      { 3, 4 },
                      { 4, 5 } };
 
    countSubtree(color, N, edge);
 
    return 0;
}

# Function to implement DFS traversal
def Solution_dfs(v, color, red, blue, sub_red, sub_blue, vis, adj, ans):
  
    # Mark node v as visited
    vis[v] = 1;
  
    # Traverse Adj_List of node v
    for i in range(len(adj[v])):
  
        # If current node is not visited
        if (vis[adj[v][i]] == 0):
  
            # DFS call for current node
            ans=Solution_dfs(adj[v][i], color,red, blue,sub_red, sub_blue,vis, adj, ans);
  
            # Count the total red and blue
            # nodes of children of its subtree
            sub_red[v] += sub_red[adj[v][i]];
            sub_blue[v] += sub_blue[adj[v][i]];
         
    if (color[v] == 1):
        sub_red[v] += 1;
     
    # Count the no. of red and blue
    # nodes in the subtree
    if (color[v] == 2):
        sub_blue[v] += 1;
     
    # If subtree contains all
    # red node & no blue node
    if (sub_red[v] == red and sub_blue[v] == 0):
        (ans) += 1;
  
    # If subtree contains all
    # blue node & no red node
    if (sub_red[v] == 0 and sub_blue[v] == blue):
        (ans) += 1;
     
    return ans
      
# Function to count the number of
# nodes with red color
def countRed(color, n):
 
    red = 0;
     
    for i in range(n):
     
        if (color[i] == 1):
            red += 1;
     
    return red;
   
# Function to count the number of
# nodes with blue color
def countBlue(color, n):
 
    blue = 0;
     
    for i in range(n):
     
        if (color[i] == 2):
            blue += 1
     
    return blue;
   
# Function to create a Tree with
# given vertices
def buildTree(edge, m, n):
 
    u, v, i = 0, 0, 0
  
    # Traverse the edge[] array
    for i in range(n - 1):
  
        u = edge[i][0] - 1;
        v = edge[i][1] - 1;
  
        # Create adjacency list
        if u not in m:
            m[u] = []
             
        if v not in m:
            m[v] = []
             
        m[u].append(v)
        m[v].append(u);
         
# Function to count the number of
# subtree with the given condition
def countSubtree(color, n, edge):
  
    # For creating adjacency list
    adj = dict()
    ans = 0;
  
    # To store the count of subtree
    # with only blue and red color
    sub_red = [0 for i in range(n + 3)]
    sub_blue = [0 for i in range(n + 3)]
  
    # visited array for DFS Traversal
    vis = [0 for i in range(n + 3)]
  
    # Count the number of red
    # node in the tree
    red = countRed(color, n);
  
    # Count the number of blue
    # node in the tree
    blue = countBlue(color, n);
  
    # Function Call to build tree
    buildTree(edge, adj, n);
  
    # DFS Traversal
    ans=Solution_dfs(0, color, red, blue,sub_red, sub_blue, vis, adj, ans);
  
    # Print the final count
    print(ans, end = '')
     
# Driver Code
if __name__=='__main__':
 
    N = 5;
    color = [ 1, 0, 0, 0, 2 ]
    edge = [ [ 1, 2 ], [ 2, 3 ], [ 3, 4 ], [ 4, 5 ] ];
  
    countSubtree(color, N, edge);
   
# This code is contributed by rutvik_56

4

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