pratheekrai2002's blog

By pratheekrai2002, history, 5 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!

Full text and comments »

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

By pratheekrai2002, history, 6 months ago, In English

Sorry if the question had been asked before, but I needed help in the following problem, any hints or topics from which it is based on would be helpful : given a tree with n nodes with each node containing a value a[i] associated with node i, also you have q queires containing of 2 nodes u and v, and a value t, you need to find the no of nodes in the simple path between u and v that have a value of atmost t? n<=1e5 q<=1e5 1<=u,v<=n t<=1e9

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it