WalidMasri's blog

By WalidMasri, history, 6 years ago,

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!

• +1

 » 6 years ago, # |   0 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 :)
•  » » 6 years ago, # ^ |   0 Here's a tutorial that explains how this approach works. It's about LCA, but the tree->array step is the same.
 » 6 years ago, # | ← Rev. 2 →   0 http://codeforces.com/contest/620/problem/E read the editorial of this problem and check this submission http://codeforces.com/contest/620/submission/15473382 by touristfor transforming teh tree to array you only need the dfs part from that code.
 » 6 years ago, # |   +2 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.
•  » » 3 years ago, # ^ |   0 thanx..really helpful editorial.Well explained.
 » 3 years ago, # |   +3 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.