WalidMasri's blog

How to use segment trees on rooted trees?
By WalidMasri, history, 9 years ago, In English

Hello CodeForces!

I have the following problem : Given a rooted tree, i have 2 types of queries: 1 q : Mark the Node q colored/uncolored. (Initially they are all uncolored). 2 p : Get the sum of the colored nodes in the p-subtree.

How can i solve this problem using segmentTrees? I couldn't figure out the part where i need to transform my rooted tree into an array, how to do that as well?

Thanks!

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

Comments Comments (4)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can easily do this by running a modified dfs:

void dfs(int node) {
    used[node]=true;
    pos[node]=++sz;
    from[node]=sz;
    to[node]=sz;
    int i;
    for(i=0;i<(int)(v[node].size());i++) {
        if(!used[v[node][i]]) dfs(v[node][i]),to[node]=max(to[node],to[v[node][i]]);
    }
}

Now pos[X] will be the index of X in the array and [ from[X];to[X] ] will be the subtree of X :)

→ Reply
»
9 years ago, # |
  Vote: I like it +2 Vote: I do not like it

My first dfs-order problem was this one. It has a really great editorial explaining how sub-tree can be converted into subarray using dfs, for update and query using segment/fenwick tree. You can easily understand and solve your problem after reading the editorial.

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

You can write pre-order traversal of the tree's nodes and note that subtrees now correspond to subsegments of that order. Now you have range sum query problem.

→ Reply