Блог пользователя _Enginor_

Help needed for a problem based on Subtree Queries on tree
Автор _Enginor_, история, 3 года назад, По-английски

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

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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)

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    can you elaborate a little?

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится 
      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

      → Ответить
      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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

        → Ответить