Tree And Special node | Editorial by aksingh007

This problem is solved by simple DFS traversal along with keeping additional information and additional decision. Lets say while moving from vertex a to b we 
found repetition of values, then, their children will also contain repetition of values as because it is a tree.Hence,here we will start DFS from root vertex 1 and keep 
on counting the frequency of values found till now.If there is no repetition we keep on counting, but as soon as any repetition id found we will not count that node and 
will not explore its children too.

Time Complexity: O(|V|+|E|)

```
import java.util.*;
import java.io.*;
class Node{
	int next,weight;boolean ispresent;
	Node(int x,int y,boolean p){next=x;weight=y;ispresent=p;}
	Node(int x,int y){next=x;weight=y;ispresent=true;}
}
class Edge implements Comparable<Edge>{
	int u,v,weight;
	Edge(int x,int y,int w){u=x;v=y;weight=w;}
	public int compareTo(Edge obj){
		return this.weight-obj.weight;
	}
}
@SuppressWarnings("unchecked")
class Graph{
	int N;
	ArrayList<Node> adj[];
	ArrayList<Edge> edgeList;
	Graph(int n){
		N=n+1;
		adj=new ArrayList[n+1];
		for(int i=0;i<=n;adj[i++]=new ArrayList<Node>());
		edgeList=new ArrayList<Edge>();
	}
	void push_edge(int x,int y,int w){
		adj[x].add(0,new Node(y,w));
		adj[y].add(0,new Node(x,w));
	}
	void dfsCall(int v,boolean visited[],int value[],int arr[],int count[]){
	    visited[v]=true;
	    if(arr[value[v]]>0){
	        return;
	    }
	    arr[value[v]]++;
	    count[0]++;
		for(int i=0;i<adj[v].size();i++)
			if(!visited[adj[v].get(i).next])
				dfsCall(adj[v].get(i).next,visited,value,arr,count);
		arr[value[v]]--;
		return;
	}
	int dfs(int src,int value[]){
	    int arr[]=new int[1000001];
	    int count[]=new int[1];
		boolean visited[]=new boolean[N+1];
		dfsCall(src,visited,value,arr,count);
		return count[0];
	}
}
	
	
class GraphAlgos{
	public static void main(String args[]) throws Exception{
		Scanner sc=new Scanner(System.in);
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int n=Integer.parseInt(br.readLine());
		Graph graph=new Graph(n+1);
	StringTokenizer tk = new StringTokenizer(br.readLine());
		int[] value = new int[n+1];
		boolean res=true;int counter[]=new int[1000001];
		for(int i=1;i<=n;i++) {
			value[i] = Integer.parseInt(tk.nextToken());
			counter[value[i]]++;
			if(counter[value[i]]>1)
			    res=false;
		}
		for(int i=0;i<n-1;i++){
			String uv[]=br.readLine().split(" ");
			graph.push_edge(Integer.parseInt(uv[0]),Integer.parseInt(uv[1]),0);
		}
		if(res)
		    System.out.println(n);
		    else
		System.out.println(graph.dfs(1,value));
	}
}

```

Tree And Special node | Editorial by aksingh007

Download submission

All caught up!

View submission

Is your resume even shortlisted?