Help needed in a question!

Revision en1, by pratheekrai2002, 2023-09-27 19:19:14

I'm sorry if this question has already been posted before but I needed help with the following problem: given a tree with N nodes rooted at 1 and each node initially deactivated at the beginning, you have to process Q queries of 3 types with each query containing an index x: Query 1: update and activate all the nodes in the subtree with index x including node x, Query 2: deactivate all the nodes in the simple path from root 1 to index x, Query 3:print the mode for the given index x (whether it is activated our not)? Input constraints: N<=1e5, Q<=1e5, Queries of types with Input Ind and type, 1<=Ind<=N, 1<=Type<=3, my approach for the given problem was creating an Euler tour of the tree and updating values in the subtree using segment tree/lazy propagation range updates, however, I was facing issues in deselecting the nodes in the path from root to index for Query 2? Any hints or topics from which the question could be solved would be helpful. Thanks in advance!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English pratheekrai2002 2023-09-27 19:19:14 1001 Initial revision (published)