radoslav11's blog

Link cut tree question.
By radoslav11, history, 7 years ago, In English

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! :)

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

»
7 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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!!!

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But then how to answer path queries (I was curious if it was possible to do both subtree and path queries)?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      So I really misunderstood something, sorry :/

      → Reply
»
7 years ago, # |
  Vote: I like it -10 Vote: I do not like it

A hard problem

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=229&page=show_problem&problem=3149

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

wow u 've got the post #60000 :O

→ Reply