The characters in the film form a forest. The queries are to change the parent of a vertex and to find out if one vertex is an ancestor of another.
Consider the string printed by tree traversal. For example, traversing a tree of three vertexes where 2 and 3 are children of 1 would print “entering 1, entering 2, leaving 2, entering 3, leaving 3, leaving 1”. Strings like this are very useful for this problem.
If we could quickly find the position of a given entry in the string, we would be able to answer whether b is an ancestor of a by checking whether “entering a” is between “entering b” and “leaving b”.
And if we could quickly split and concatenate those strings, we could change the parent of a vertex by finding the substring from “entering a” to “leaving a” (inclusive), cutting it out of its current place, and inserting it into a new location.
We can do this with a balanced binary tree, such as a treap. Each node of the treap will be either “entering x” or “leaving x”, and their order will indirectly represent the structure of our original tree. By keeping a reference to every node and remembering the size of all subtrees of the treap, we can quickly find out the index of any treap node by counting how many nodes are to the left of it.
Note that we don’t use the treap as a binary search tree – the entries aren’t ordered by keys, but explicitly by split/merge calls.
In the hard subproblem, we just need to add support for cycles. We keep the above structure, but for every tree in the forest, we also remember an optional “phantom” edge from the root vertex to a vertex in the same tree. This edge won’t be stored in our special structure, but in a plain array.
For simplicity, instead of “changing the parent of vertex a to vertex b” let’s split the query into two parts: “removing the edge from a to its parent” and “adding a parent edge from a (which is currently a root) to b”.
To add an edge from a to b:
To remove an edge from a to its parent:
The amortized time complexity is O(n + q log n).
It’s always difficult to prepare input data for problems like this, where a $O(n \sqrt{n})$ solution also exists and is often much easier to write. In a normal contest, if the optimal solution takes 1 second and a suboptimal solution takes 30 seconds, it’s easy to distinguish them. But IPSC is an open data contest. If the optimal solution takes 1 minute and a suboptimal solution takes 30 minutes, it can still be worth it.
On one hand, we’d like to prevent $\sqrt{n}$ solutions, or at least make them slow enough to discourage most of them. On the other hand, making the input bigger also makes the optimal solution slower, and we don’t want to disadvantage teams with slower CPUs or smaller RAM.
With the inputs we’ve chosen, our optimal solution takes about 4 minutes and a $\sqrt{n}$ solution takes about 80 minutes. Maybe some teams will give up on their optimal program and kill it after it runs for ten minutes without success, and maybe some teams will find a fast-enough suboptimal solution and save some coding time, but on average we hope it’s a good compromise.