Back Ground

I managed to solve CF707D and at that time I didn't know this trick. After thinking for a while, I had a really good idea about solving it. After I read the tutorial I saw that this solution is mentioned in Solution No.1. But I really learned I good way of solving data structure problems including the following operations.

$$$1.$$$ Modify based on version x and the result is assigned version x

$$$2.$$$ return ... in a state they were after applying $$$k$$$-th operation.

For these questions, we could build a tree and solve the queries by DFS if off-line solutions are allowed.

Construction

The construction is quite easy. If version $$$v$$$ is modified based on version $$$x$$$, we add an edge from version $$$x$$$ to version $$$v$$$.

Because every version only has exact one father so obviously, the graph formed a tree.

Query

The answer of a query is affected by the modifications on the path from the root to this version, so what we need is to calculate it, and the way is to maintain a structure mentioned in the task without modifications based on other versions. In other words, we only need to maintain the latest version of the structure.

When we are staying at one version, we added the modifications the version contains and move to the children of the version. After visiting all of its children, we would revoke the modifications if necessary.