「TOCO Round 1」History
题目描述
这里有一棵 $n$ 个结点根为 $1$ 号结点的树,每个结点上都有一盏灯,初始状态都是关闭。现在有 $m$ 次事件发生,有以下几种情况:
`1 x` 将 $x$ 位置上的灯打开或关闭(原来如果打开就关闭,否则打开)。
`2 x y` 询问树上与 $x$ 相同深度的点中与 $x$ 结点距离为 $y$ 的点中开着的灯的个数。
`3 x` 回到第 $x$ 次事件发生之后的状态。
对于每个 $2$ 询问请给出回答。
输入输出格式
输入格式
第一行一个数 $n$ 。
接下来 $n-1$ 行每行两个数 $u,v$ 表示 $u$ 与 $v$ 之间一条边。接下来一个数 $m$,下面的 $m$ 行每行二或三个数表示事件的发生。
输出格式
对于每次 $2$ 询问,给出答案。
输入输出样例
输入样例 #1
3
1 2
1 3
6
1 3
2 2 2
1 2
2 2 2
1 3
2 2 2
输出样例 #1
1
1
0
说明
**本题采用打包测评。**
* Subtask 1(10 pts):满足所有询问中 $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$。
对于 $100\%$ 的数据,$1\leq n,m\leq 10^5$,$3$ 操作保证 $0 \leq x$。