HackerEarth Tree And Special node problem solution

In this HackerEarth Tree And Special node problem solution Given a rooted undirected tree T consisting of N nodes with 1 as the root of the tree. Each node of the tree has a value associated with it, where the value of the ith node is A[i]. A node x is said to be special if the path from the root to node x contains all distinct values. Your task is to find the number of special nodes.

HackerEarth Tree And Special node problem solution.

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;

vector<int> adj[N];
bool vis[N];
int arr[N];
int fre[N];
int ans;

void fill()
{
    memset(vis,false,sizeof(vis));
    memset(fre,0,sizeof(fre));
    ans=0;
}
void dfs(int s)
{
    vis[s]=true;
    
    if(fre[arr[s]])
    {
        return;
    }
    fre[arr[s]]++;
    ans++;
    for(auto x: adj[s])
    {
        if(!vis[x])
        {
            dfs(x);
        }
    }
    fre[arr[s]]--;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
    }
    int u,v;
    for(int i=1;i<n;i++)
    {
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    fill();
    dfs(1);
    cout<<ans<<"n";
    return 0;
}

coding problems solutions