Subtask 1

For this subtask, there are only ~D~ operations.

Maintain a graph that represents the tree.

Iterate over the operations backwards, building up the graph as we go.

For each operation, if ~a_i~ or ~b_i~ doesn't exist, insert it into the graph, along with the edge between them.

• This ensures that when this operation is sequentially processed, exactly the node we inserted will be deleted by the operation.
• If at this point, both ~a_i~ and ~b_i~ have been inserted into the graph, the data is invalid and you should output -1. This is because it means both ~a_i~ and ~b_i~ were inserted - and therefore were supposed to be deleted - by another ~D~ operation. If this ~D~ operation doesn't delete any nodes, it will only break the edge in between them - disconnecting the graph.

Notice that because the input is guaranteed to be valid, the final graph is guaranteed to be a forest of trees. To output as a single graph, all the components have to be merged.

For every single component, arbitrarily select its "root node" as one of the two nodes that created the component when they were inserted into the graph as a new component. Identify the oldest root node, that was inserted in the first ~D~ operation processed, and merge all the other roots into this one.

You are left with a graph that is a tree that satisfies the problem constraints and uses only nodes mentioned in the input. Therefore, it is optimal.

Note that the invariant that every node is deleted by the operation that inserts it is broken by our merge. This is because a ~D~ operation is only capable of deleting an edge, and by extension node, that it represents. The edges we used to merge components cannot have been mentioned in any ~D~ operation, and so they will never be deleted along with those nodes. To make sure that following a ~D~ operation these undeleted nodes don't break into different components, the edges must form their own connected subgraph. Merging through the oldest root in the graph accomplishes this.

Subtask 2

For this subtask, ~L~ operations are also introduced.

Again, we will iterate backwards. Skip and count the number of initial ~L~ operations as a number ~E~, so that the first operation processed is of type ~D~.

If ~E = Q~, output a line graph of length ~2Q-1~ and terminate the algorithm.

~D~ operations will work the same as the last subtask.

For ~L~ operations, the goal when processing an operation is still to insert nodes into the graph that will be deleted when the operation is sequentially applied. Since the ~L~ operation essentially trims all leaves of the graph, a node should be inserted on top of each leaf. However, given that at this point the graph is only guaranteed to be a forest, not all leaves of components will actually be leaves when this operation is sequentially applied. So, the components should be merged before we process the ~L~ operation.

Notice that the number of new nodes introduced by the ~L~ operation is equivalent to the number of leaves. Also notice that the only way to "cover up" a leaf so that it cannot accrue a node from ~L~ operations is to merge another component on top of it. So, the merge should be optimized to cover up as many leaves as possible.

To execute a merge, identify the oldest component in the graph established by the first ~D~ operation. All other components will be merged into this one. This makes it so that when the operations are sequentially applied, the other components are completely deconstructed before the oldest component is destroyed, making it so that the tree is never disconnected. Once again, identify the root of every component in the graph. This time, a root that is a leaf should be preferred over one that is not to minimize the final number of leaves in the graph before the ~L~ operation is applied. There are two ways to merge each newer component into the older one:

1. Place an edge between the older component's root and the newer one's root. This works similarly to the method of merging components used in the previous subtask. However, this method doesn't save any nodes from being added, so the second method should be preferred if it is available:

2. "Replace" one of the nodes added during a previously processed ~L~ operation with the root of the newer component. Note that only the oldest component can have any nodes added due to ~L~ operations on it, because of the constraint that the graph must be merged down to a single component before every ~L~ operation. Thus, any newer components can only have been created between the last ~L~ operation and the current merge - meaning that they were never affected by ~L~ operations.

   By "replace", we mean merge the adjacencies of the two nodes. This makes it so that instead of deleting the node added for the ~L~ operation, the new component's root is instead deleted - saving a node.

   When choosing which nodes to replace, replaceable nodes that are leaves should be prioritized to "cover up" the leaf.

The final thing to consider is the ~E~ initially skipped ~L~ operation nodes. To satisfy them, we should attach a line graph of ~\max(2E-2, 1)~ replaceable nodes to the oldest component's root before the first merge operation. This will ensure that the algorithm creates a line graph of length ~2E-1~ that will outlast all other nodes and edges, and be consumed by the initially skipped ~L~ operations.

Before output, merge the graph into a single component in the same way.

This concludes the greedy solution to this problem.