Hi guys! Can you help me with this problem?

Revision en1, by I_Blade_of_Ranni, 2022-06-28 12:05:07

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?

Tags #dsu, #dsu on tree, tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English I_Blade_of_Ranni 2022-06-28 12:05:59 10
en1 English I_Blade_of_Ranni 2022-06-28 12:05:07 620 Initial revision (published)