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

Автор terserah, история, 7 лет назад, По-английски

Hello, can anybody give me hints for this problem? I think heavy light decomposition could handle the type-1 query, but how about the type-2 query?

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

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

My (author's) solution uses the fact that there are not many nodes having many children and nodes with not so many children are easy to handle.

Of course, as an author I don't want to reveal the full solution but I think this hint is enough for you to get it. I am happy to see many different approaches that didn't occur to me, including a good portion of HLD solutions.

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

I solved this using this technique e.e in $$$O(n \log^2 n)$$$, I can optimize it to $$$O(n \log n)$$$ using this blog.