## Back Ground↵
↵
I managed to solve [CF707D](https://codeforces.ml/contest/707/problem/D) 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, query for the answer and move to the children of the version.↵
↵
After visiting all of its children, we should revoke the modifications if necessary.↵
↵
The code goes like this:↵
↵
```cpp↵
void DFS(int u) {↵
add modifications of version u↵
query the ans at version u if there are queries.↵
visit the children of version u↵
revoke the modificationis of version u↵
```}↵
```cpp↵
↵
## Examples↵
↵
1. [CF707D](https://codeforces.ml/contest/707/problem/D)No.1 [problem:707D]↵
↵
Solution: we build a tree mentioned above and use a bitset to maintain the latest version and update the answers.↵
↵
2.No.2 GYM100431 G↵
↵
Solution: build a tree mentioned above and use vector to maintain the latest version and update the answers.↵
↵
There is a trick that we do not need to actually pop the first element, we only need to maintain the position of the first element and move it.↵
↵
Some times the graph may not form a tree, we may use something like $dp$ to solve that, but I could not find tasks about itNo.3 Found by [user:jonathanesmuyguapo,2020-12-23]↵
↵
[CSES.fi 1737](https://cses.fi/problemset/task/1737/)↵
↵
Solution: In this problem the modifications are not assigned a new version. So we try to record every history version. Use $lat[x]$ to record the index of the latest version of array $x$.↵
↵
If we have queries, just add it to the latest version of array $x$ at that moment.↵
↵
If we have modifications, just create a new version and add the modifications on the new version. Then update $lat[x]$.↵
↵
Therefore we could solve this by **DFS** a tree.
↵
I managed to solve [CF707D](https://codeforces.ml/contest/707/problem/D) 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, query for the answer and move to the children of the version.↵
↵
After visiting all of its children, we should revoke the modifications if necessary.↵
↵
The code goes like this:↵
↵
```cpp↵
void DFS(int u) {↵
add modifications of version u↵
query the ans at version u if there are queries.↵
visit the children of version u↵
revoke the modificationis of version u↵
```cpp↵
↵
## Examples↵
↵
↵
Solution: we build a tree mentioned above and use a bitset to maintain the latest version and update the answers.↵
↵
↵
Solution: build a tree mentioned above and use vector to maintain the latest version and update the answers.↵
↵
There is a trick that we do not need to actually pop the first element, we only need to maintain the position of the first element and move it.↵
↵
↵
[CSES.fi 1737](https://cses.fi/problemset/task/1737/)↵
↵
Solution: In this problem the modifications are not assigned a new version. So we try to record every history version. Use $lat[x]$ to record the index of the latest version of array $x$.↵
↵
If we have queries, just add it to the latest version of array $x$ at that moment.↵
↵
If we have modifications, just create a new version and add the modifications on the new version. Then update $lat[x]$.↵
↵
Therefore we could solve this by **DFS** a tree.
