You are given a tree of n nodes rooted at 1. Each node of the tree has a color associated with it. Now you are given q queries. In each query, you are given a node number X and for each query, you have to mark the node X as special and all the other nodes in its subtree with the same color also as special. If a node is marked as special in the query then for all the other subsequent queries, it remains marked as special. For each query, you need to print the total number of special nodes in the tree after you perform the marking operation in the query.

input format: first-line: N, next N-1: edges, next line with N integers: the color of the ith node, next line query: Q, next Q lines for jth query: X.

constraints: N, Q <= 1e5.

Sample input:

                    5              
                    3 1
                    3 2
                    2 4
                    2 5
                    1 1 2 2 1
                    4
                    2
                    4
                    5
                    1

sample output:

                 2 
                 3 
                 3 
                 4

my solution, but inefficient:https://ideone.com/whqXRa