Can anyone give some ideas about how can this problem be solved using Segment Trees OR any other data structure.
I build an euler tour of the tree in which each node is pushed twice.Then the subtree of any node is a range in the euler tour array. Now I want an idea about what to store at each node in segment tree and how to perform merge operation.
I have already spent more than 3 hours on this problem but I could not figure out any approach. Also I am unable to understand the editorial given :(.
Any help is appreciated !.
I solved a similiar question question and face same problem .Just run dfs while entering dfs function add element to arr . This way all element will be once in array . While making query ( position_of_node_in_arr , position_of_node_in_arr + size_of_subree)
can you elaborate a little?
use segment tree on vector a
for update use update(pos[i]) //i is node that to be updated
for query use query(pos[i],pos[i]+size_s[i]-1)
as we know according to dfs structure is we visit the node it will visit all node that are in subtree of that node and after that visit other node
if you don't understand let me know
Your approach is for the question which asks for the number of turned ON nodes in the substree of node x but the above question is different here we need to find the number of nodes in the substree of x such that we can go from x to that node by going through only the nodes which are in ON state.
The above code which you have shown is for the euler tour of the tree but I'm asking for the idea how to use segment tree over the built euler tour array to solve the given problem.
correct me If I'm wrong
sorry,you are right