pratheekrai2002's blog

Help needed in a question!
By pratheekrai2002, history, 15 months ago, In English

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!

  • Vote: I like it
  • +7
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
15 months ago, # |
  Vote: I like it +2 Vote: I do not like it

In segment tree with lazy propogation add 0 to node if subtree needs to be deactivaed and 1 if subtree needs to be activated. Apart from that store priority of each 0's and 1's(priority here can simply index in the query list). now for 3rd type of query start from root of segment tree and update the status of all nodes in the path of root to node x. Simply A higher priority(one which occurs later in query senquence) will override the lower priority.

It's explained in very simple terms. Please feel free to ask for additional clarification if needed.

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you for your reply, but I'm not sure I get your complete solution, for queries of type one you are telling me to update the subtree in the Eulers tour to activate the whole subtree, then for queries of type 2 you are saying to update the root of tree (1) ? so as to deactivate the whole subtree? Now for type 2, I still didn't get how you are able to deactivate the whole path from this, along with this you are telling to maintain a variable for asserting priority. Now for query 3, we have to get the max priority in the indices from 1 to in_time[ind] in the Eulers tour using a segment tree? but wouldn't this lead to a time complexity of O(Q*N)? I'm sorry if I'm asking a lot but could you provide it with a dry run for the following tree: N=6, Root = 1 Edges: 1-2, 1-3, 2-4, 2-5, 3-6 Queires: 5 {type, index} 1: type =1; index= 2 2: type =3, index =3? 3: type =2; index =1 4: type =1, index =5 5: type =3, index =4?

    → Reply
    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      If you need it, I wrote a code for tree heavy path decomposition:

      Spoiler
      → Reply