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


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;
}