Número de Nodes especiales en un árbol n-ario

Dado un árbol n-ario con raíz en el vértice 1. El árbol tiene n vértices y n-1 aristas. Cada Node tiene un valor asociado y el árbol se ingresa en forma de lista de adyacencia. La tarea es encontrar el número de Nodes especiales en el árbol. Un Node es especial si la ruta desde la raíz hasta el Node consta de Nodes de valores distintos.
Ejemplos: 
 

Input: val[] = {1, 2, 3, 4, 5, 7, 2, 3}
                1
               / \
              2   3
             / \   \
            4   5   7
               / \
              2   3
     
Output: 7
All nodes except the leaf node 2 are special.

Input: val[] = {2, 1, 4, 3, 4, 8, 10, 2, 5, 1}
                2
               / \
              1   4
            / \ \  \
           3  4  8  10
            / \ \
           2  5  1
    
Output: 8
Leaf nodes 2 and 1 are not special.

Enfoque: la idea es realizar dfs en un árbol dado usando una lista de adyacencia. Al realizar dfs, inserte valores de los Nodes visitados en un conjunto. Si el valor del Node actual ya está presente en el conjunto, entonces el Node actual y todos los Nodes en el subárbol con raíz en el Node actual no son especiales. Después de atravesar el subárbol enraizado en el Node actual, borre el valor del Node actual del conjunto, ya que este valor o Node no se encuentra en la ruta desde la raíz a todos los demás Nodes no visitados. 
A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// DFS function to traverse the tree and find
// number of special nodes
void dfs(int val[], int n, vector<int> adj[], int v,
         unordered_set<int>& values, int& ans)
{
 
    // If value of current node is already
    // present earlier in path then this
    // node and all other nodes connected to
    // it are not special
    if (values.count(val[v]))
        return;
 
    // Insert value of current node in
    // set of values traversed
    ans++;
    values.insert(val[v]);
 
    // Call dfs on all adjacent nodes
    for (auto ele : adj[v]) {
        dfs(val, n, adj, ele, values, ans);
    }
 
    // Erase value of current node as all paths
    // passing through current node are traversed
    values.erase(val[v]);
}
 
// Driver code
int main()
{
    int val[] = { 0, 2, 1, 4, 3, 4, 8, 10, 2, 5, 1 };
    int n = sizeof(val) / sizeof(val[0]);
 
    vector<int> adj[n];
 
    adj[1].push_back(2);
    adj[1].push_back(3);
    adj[2].push_back(4);
    adj[2].push_back(5);
    adj[2].push_back(6);
    adj[3].push_back(7);
    adj[5].push_back(8);
    adj[5].push_back(9);
    adj[5].push_back(10);
 
    unordered_set<int> values;
 
    int ans = 0;
 
    dfs(val, n, adj, 1, values, ans);
 
    cout << ans;
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
static int ans;
 
// DFS function to traverse the tree and find
// number of special nodes
static void dfs(int val[], int n, Vector<Integer> adj[], int v,
        HashSet<Integer> values)
{
 
    // If value of current node is already
    // present earlier in path then this
    // node and all other nodes connected to
    // it are not special
    if (values.contains(val[v]))
        return;
 
    // Insert value of current node in
    // set of values traversed
    ans++;
    values.add(val[v]);
 
    // Call dfs on all adjacent nodes
    for (int ele : adj[v])
    {
        dfs(val, n, adj, ele, values);
    }
 
    // Erase value of current node as all paths
    // passing through current node are traversed
    values.remove(val[v]);
}
 
// Driver code
public static void main(String[] args)
{
    int val[] = { 0, 2, 1, 4, 3, 4, 8, 10, 2, 5, 1 };
    int n = val.length;
 
    Vector<Integer> []adj = new Vector[n];
    for(int i = 0; i < n ; i++)
    {
        adj[i] = new Vector<Integer>();
    }
    adj[1].add(2);
    adj[1].add(3);
    adj[2].add(4);
    adj[2].add(5);
    adj[2].add(6);
    adj[3].add(7);
    adj[5].add(8);
    adj[5].add(9);
    adj[5].add(10);
 
    ans = 0;
    dfs(val, n, adj, 1, new HashSet<Integer>());
    System.out.print(ans);
}
}
 
// This code is contributed by Rajput-Ji

# Python3 implementation of the approach
 
# DFS function to traverse the tree
# and find number of special nodes
def dfs(val, n, adj, v, values):
 
    # If value of current node is already
    # present earlier in path then this
    # node and all other nodes connected
    # to it are not special
    if val[v] in values:
        return
     
    global ans
 
    # Insert value of current node in
    # set of values traversed
    ans += 1
    values.add(val[v])
 
    # Call dfs on all adjacent nodes
    for ele in adj[v]:
        dfs(val, n, adj, ele, values)
 
    # Erase value of current node as all
    # paths passing through current node
    # are traversed
    values.remove(val[v])
 
# Driver code
if __name__ == "__main__":
 
    val = [0, 2, 1, 4, 3, 4, 8, 10, 2, 5, 1]
    n = len(val)
 
    adj = [[] for i in range(n)]
 
    adj[1].append(2)
    adj[1].append(3)
    adj[2].append(4)
    adj[2].append(5)
    adj[2].append(6)
    adj[3].append(7)
    adj[5].append(8)
    adj[5].append(9)
    adj[5].append(10)
 
    values = set()
    ans = 0
    dfs(val, n, adj, 1, values)
    print(ans)
 
# This code is contributed by Rituraj Jain

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG
{
  
static int ans;
  
// DFS function to traverse the tree and find
// number of special nodes
static void dfs(int []val, int n, List<int> []adj, int v,
        HashSet<int> values)
{
  
    // If value of current node is already
    // present earlier in path then this
    // node and all other nodes connected to
    // it are not special
    if (values.Contains(val[v]))
        return;
  
    // Insert value of current node in
    // set of values traversed
    ans++;
    values.Add(val[v]);
  
    // Call dfs on all adjacent nodes
    foreach (int ele in adj[v])
    {
        dfs(val, n, adj, ele, values);
    }
  
    // Erase value of current node as all paths
    // passing through current node are traversed
    values.Remove(val[v]);
}
  
// Driver code
public static void Main(String[] args)
{
    int []val = { 0, 2, 1, 4, 3, 4, 8, 10, 2, 5, 1 };
    int n = val.Length;
  
    List<int> []adj = new List<int>[n];
    for(int i = 0; i < n ; i++)
    {
        adj[i] = new List<int>();
    }
    adj[1].Add(2);
    adj[1].Add(3);
    adj[2].Add(4);
    adj[2].Add(5);
    adj[2].Add(6);
    adj[3].Add(7);
    adj[5].Add(8);
    adj[5].Add(9);
    adj[5].Add(10);
  
    ans = 0;
    dfs(val, n, adj, 1, new HashSet<int>());
    Console.Write(ans);
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
// JavaScript implementation of the approach
 
    var ans;
 
    // DFS function to traverse the tree and find
    // number of special nodes
    function dfs(val , n, adj , v,  values) {
 
        // If value of current node is already
        // present earlier in path then this
        // node and all other nodes connected to
        // it are not special
        if (values.has(val[v]))
            return;
 
        // Insert value of current node in
        // set of values traversed
        ans++;
        values.add(val[v]);
 
        // Call dfs on all adjacent nodes
        adj[v].forEach(function(ele) {
    
            dfs(val, n, adj, ele, values);
        });
 
        // Erase value of current node as all paths
        // passing through current node are traversed
        values.delete(val[v]);
    }
 
    // Driver code
     
        var val = [ 0, 2, 1, 4, 3, 4, 8, 10, 2, 5, 1 ];
        var n = val.length;
 
        var adj = [];
        for (var i = 0; i < n; i++) {
            adj[i] = [];
        }
        adj[1].push(2);
        adj[1].push(3);
        adj[2].push(4);
        adj[2].push(5);
        adj[2].push(6);
        adj[3].push(7);
        adj[5].push(8);
        adj[5].push(9);
        adj[5].push(10);
 
        ans = 0;
        dfs(val, n, adj, 1, new Set());
        document.write(ans);
 
// This code contributed by aashish1995
 
</script>

8

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