I_Blade_of_Ranni's blog

By I_Blade_of_Ranni, history, 11 months ago, In English

I came up with this problem myself just now, but I don't know how to solve it besides brutal implement. Here's the thing.

Assume there're n vertexes, they form a number of trees,(initially n). Then process three kinds of operations q+c+m times.

Operation 1: query x: print the current root of the tree which contains vertex x.

Operation 2: cut x: cut subtree x from it's original tree, keep its structure and make it become a new tree.

Operation 3: merge x y: let tree x become a subtree under vertex y.

Let's say n<2e5 and q+c+m<2e5, what's the best solution can you get?

  • Vote: I like it
  • -10
  • Vote: I do not like it

11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

just link cut tree $$$O(N*log^2N)$$$