CF342E Xenia and Tree

程序员 Xenia 有一棵包含 $n$ 个节点的树。我们假设这些树节点从 $1$ 到 $n$ 编号。最初，第一个节点被涂成红色，其余节点都被涂成蓝色。 两棵树上节点 $v$ 和 $u$ 之间的距离，指的是它们之间最短路径上经过的边的数量。 Xenia 需要快速地执行两种类型的操作： 1. 将指定的蓝色节点染成红色； 2. 查询给定节点距离最近的红色节点，并输出最短距离。 你的任务是编写一个程序，执行上述操作。

第一行包含两个整数 $n$ 和 $m$ $(2 \leq n \leq 10^{5},\ 1 \leq m \leq 10^{5})$ —— 树的节点数和操作数。接下来 $n-1$ 行每行两个整数 $a_i, b_i$ $(1 \leq a_i, b_i \leq n, a_i \ne b_i)$，表示树中的一条边。 接下来的 $m$ 行，每行描述一个操作。每个操作包含两个整数 $t_i, v_i$ $(1 \leq t_i \leq 2, 1 \leq v_i \leq n)$。如果 $t_i = 1$，则表示将编号 $v_i$ 的蓝色节点染成红色。如果 $t_i = 2$，则需要输出编号 $v_i$ 的节点到距离它最近的红色节点的最短距离。 保证给定的图是树，且所有的操作都是合法的。

对于每个第二类型的操作，输出一行，表示最近红色节点到 $v_i$ 的最短距离。

由 ChatGPT 5 翻译