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! :)
For subtree queries, check this blog: Memphis's Blog
Thanks!
I think you can only do path queries with LC-T, for subtree queries use Euler tree.
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!!!
But then how to answer path queries (I was curious if it was possible to do both subtree and path queries)?
So I really misunderstood something, sorry :/
A hard problem
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=229&page=show_problem&problem=3149
wow u 've got the post #60000 :O