Need approach to solve this tree problem

Revision en1, by Naithani, 2020-03-14 23:06:37

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Naithani 2020-03-14 23:07:48 9 Tiny change: 'ints: N, Q <= 1e5.\n' -> 'ints: N, Q, X <= 1e5.\n' (published)
en1 English Naithani 2020-03-14 23:06:37 1322 Initial revision (saved to drafts)