Can Link Cut Trees handle subtree aggregates?

Revision en1, by SecondThread, 2020-03-18 04:26:14

I'm somewhat familiar with how Link Cut Trees work. I have watched Erik Demaine's lecture on them from MIT Open Courseware, solved a couple problems that use them with my team's (very copy-pasteable) book code, and read about them a bit, so I have an idea of how they work in general.

The code I have used supports range path update, path query, link, cut, and checkConnected queries. I read on Wikipedia that Euler Tour Trees are better for subtree queries and link cut trees are better for path queries. However, I looked through ko_osaga's code for fully dynamic connectivity and it looks like he is using a splay tree or link-cut tree of some sort. Link-cut trees use splay trees to store preferred paths, so the size of a splay tree node's subtree doesn't really mean anything, right? But for the dynamic connectivity problem he was trying to solve, I'm pretty sure you need to check, after cutting an edge, which of the trees you created is smaller. That sure doesn't seem like a path operation to me.

So is it possible to do subtree-like operations on LCT's?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English SecondThread 2020-03-18 04:26:14 1170 Initial revision (published)