_Enginor_'s blog

Help needed for a problem based on Subtree Queries on tree
By _Enginor_, history, 3 years ago, In English

Link To Problem

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 !.

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

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

    can you elaborate a little?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it 
      int pos[200005]; // this will store the index of node i in array i
int curr;
int size_s[200005]; // this will store the size of subarray
vector<int> a;
void dfs(int i,int p){
    size_s[i]++;
    pos[i] = curr++;
    a.pb(i);
    for(int j : adj[i]){
        if(j==p)continue;
        dfs(j,i);
        size_s[i] += size_s[j];
    }
}

      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

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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

        → Reply