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 lines: 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, X <= 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
Auto comment: topic has been updated by Naithani (previous revision, new revision, compare).
Suppose that for every color you rewrite the vertices in the order a DFS would visit them. After doing this, every node's subtree will consist of a contiguous segment. This means that, for every query, you have to "activate" a subsegment of an array. This can be done in many ways, since you can iterate over all inactive positions.
Thanks bro, you are the best I have created the AC solution https://ideone.com/dL7Qhm
This is the 3rd question from the practice round of Hackwithinfy. I did it with the Euler tour and a map of set.