-synx-'s blog

Problem on Mo's Algorithm on Trees?
By -synx-, history, 7 years ago, In English

So the problem goes like, we have colors designated to vertices of tree and we need to find distinct values in subtree of a vertex (queries).
Can anyone share/remember such a problem?
Thanks.

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

Comments Comments (1)
| Write comment?
»
7 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

At first linearize the tree by Euler Tour. Then you can represent each subtree by a contiguous sub-array. Now the task is just counting number of distinct integers in a range of array. You can do that by normal MO's algo. Or you can use persistent segment trees to get per query solution.

There are other solution too, like you can do DSU on tree and solve the problem offline in .

→ Reply