## 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↵
```↵
↵
## Examples↵
↵
1. [CF707D](https://codeforces.ml/contest/707/problem/D)↵
↵
Solution: we build a tree mentioned above and use a bitset to maintain the latest version and update the answers.↵
↵
2. GYM100431 G↵
↵
Solution: build a tree mentioned above and use vector to maintain thewholelatest 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 it.
↵
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↵
```↵
↵
## Examples↵
↵
1. [CF707D](https://codeforces.ml/contest/707/problem/D)↵
↵
Solution: we build a tree mentioned above and use a bitset to maintain the latest version and update the answers.↵
↵
2. GYM100431 G↵
↵
Solution: build a tree mentioned above and use vector to maintain the
↵
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 it.
