P7394 "TOCO Round 1" History

There is a tree with $n$ nodes, rooted at node $1$. Each node has a lamp, and all lamps are initially off. Now $m$ events occur, in the following forms: `1 x` Toggle the lamp at node $x$ (turn it off if it is on, otherwise turn it on). `2 x y` Query the number of nodes whose lamps are on among the nodes that are at the same depth as node $x$ and have distance $y$ from node $x$ in the tree. `3 x` Revert to the state right after the $x$-th event. For each query of type $2$, output the answer.

The first line contains an integer $n$. The next $n-1$ lines each contain two integers $u, v$, indicating an edge between $u$ and $v$. Then an integer $m$ follows. The next $m$ lines each contain two or three integers describing an event.

For each query of type $2$, output the answer.

**This problem uses bundled evaluation.** * Subtask 1 (10 pts): For all queries, $y \bmod 2 = 1$. * Subtask 2 (20 pts): $n, m \leq 10$. * Subtask 3 (30 pts): $n, m \leq 10^3$. * Subtask 4 (40 pts): $n, m \leq 10^5$. For $100\%$ of the testdata, $1 \leq n, m \leq 10^5$, and operations of type $3$ guarantee $0 \leq x$. Translated by ChatGPT 5