CF825G Tree Queries

给定一棵包含 $n$ 个顶点的树（顶点编号为 $1$ 到 $n$），初始时所有顶点都是白色。你需要处理 $q$ 个操作，操作有两种类型： 1. $1$ $x$ — 将顶点 $x$ 的颜色变为黑色。保证第一个操作必定为该类型。 2. $2$ $x$ — 对于顶点 $x$，找到某条从 $x$ 到某个黑色顶点的简单路径上编号最小的顶点 $y$（简单路径指路径上每个顶点不重复出现）。 对于每个类型为 $2$ 的操作，输出答案。 注意：这里的查询输入方式经过了修改。

第一行包含两个整数 $n$ 和 $q$（$3\le n, q\le 10^6$）。 接下来的 $n-1$ 行，每行两个整数 $x_i$ 和 $y_i$（$1\le x_i, y_i\le n$），表示在顶点 $x_i$ 与 $y_i$ 之间有一条无向边。这些边保证构成一棵树。 接下来的 $q$ 行，每行两个整数 $t_i$ 和 $z_i$，其中 $t_i$ 表示第 $i$ 次操作的类型，$z_i$ 用于恢复该操作中的顶点 $x_i$，具体方式如下：你需要记录上一次类型为 $2$ 的操作的答案（记为 $last$，初始 $last=0$），然后 $x_i=(z_i+last)\bmod n+1$。 保证第一个操作是类型 $1$，且至少存在一个类型为 $2$ 的操作。

对每个类型为 $2$ 的操作，输出其答案。

由 ChatGPT 5 翻译