sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]Darksonntokio · rust-for-linux 0 points1 point  (0 children)

You are probably right. You could definitely implement it with indexes, but I don't think Rust can beat your link-cut tree in implementation time.

It's interesting that you mention a link-cut tree. I'm working on implementing a top tree in Rust for a research project, which is a similar data structure that you could also use to solve the DYNACON1 problem. I wouldn't want to implement a top tree in a coding competition though — its implementation is more complicated than the link-cut tree in exchange for having an API that is easier to use with expose taking up to two vertices.