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

Problem on Mo's Algorithm on Trees?
Автор -synx-, история, 7 лет назад, По-английски

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.

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

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

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 .

→ Ответить