- Practice
- Data Structures
- Advanced
- Coloring Tree

# Coloring Tree

# Coloring Tree

You are given a tree with **N** nodes with every node being colored. A color is represented by an integer ranging from 1 to 10^{9}. Can you find the number of distinct colors available in a subtree rooted at the node **s**?

**Input Format**

The first line contains three space separated integers representing the number of nodes in the tree (**N**), number of queries to answer (**M**) and the root of the tree.

In each of the next N-1 lines, there are two space separated integers(a b) representing an edge from node a to Node b and vice-versa.

N lines follow: N+i^{th} line contains the color of the i^{th} node.

M lines follow: Each line containg a single integer s.

**Output Format**

Output exactly M lines, each line containing the output of the i_{th} query.

**Constraints**

0 <= M <= 10^{5}

1 <= N <= 10^{5}

1 <= root <= N

1 <= color of the Node <= 10^{9}

**Example**

**Sample Input**

```
4 2 1
1 2
2 4
2 3
10
20
20
30
1
2
```

**Sample Output**

```
3
2
```

**Explanation**

Query 1-Subtree rooted at 1 is the entire tree and colors used are 10 20 20 30 , so the answer is 3(10,20 and 30)

Query 2-Subtree rooted at 2 contains color 20 20 30, so the answer is 2(20 and 30)