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

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

Hello!

Recently I relearned link cut trees and now I'm curious how to do subtree updates/queries as I have seen comments in the past that it's possible. So can someone share how to do it and also can we perform both subtree and path queries/updates simultaneously?

Also can someone share some interesting (and hard) problems with link cut trees which you have encountered and liked.

Thanks in advance! :)

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

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

For subtree queries, check this blog: Memphis's Blog

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

I think you can only do path queries with LC-T, for subtree queries use Euler tree.

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

If I didn't misunderstood anything, it seems like a simple modification of euler tour technique — If you imagine an euler tour sequence of length 2N-2, subtree queries are subsegment queries, and link / cut operations corresponds to a subsegment splicing / merging. Thus everything can be done with a splay tree.

There is an awesome practice problem here, where you have 12 kind of queries, yay!!!

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

wow u 've got the post #60000 :O