P12562 [UTS 2024] Two Trees

给定两棵相同的无向树 $G$ 和 $H$，每棵树包含 $n$ 个顶点。两棵树被称为相同，当且仅当对于所有顶点对 $(u,v)$，$G$ 中存在边 $(G_u,G_v)$ 当且仅当 $H$ 中存在边 $(H_u,H_v)$。 某些顶点可以通过无向边连接到另一棵树中的对应顶点。特别地，叶子顶点 $G_v$ 可以直接连接到顶点 $H_v$。如果叶子顶点 $G_v$ 直接连接到 $H_v$，则称顶点 $v$ 为**启用**状态，否则为**禁用**状态。 初始时，所有叶子顶点均为**禁用**状态。需要处理以下两种查询： 1. $1$ $v$ —— 切换顶点 $v$ 的状态（若当前为禁用则改为启用，反之亦然）； 2. $2$ $u$ $v$ —— 输出从顶点 $G_u$ 到顶点 $H_v$ 的最短路径长度。

第一行包含两个整数 $n$ 和 $q$ ($3 \le n \le 2 \cdot 10^5$; $1 \le q \le 2 \cdot 10^5$) —— 分别表示顶点数和查询数。 接下来 $n-1$ 行，每行包含两个整数 $u$, $v$ $(1 \le u,v \le n)$ —— 描述树的边 $(G_u,G_v)$ 和 $(H_u,H_v)$。 接下来 $q$ 行，每行描述一个查询。查询有两种形式： - $1$ $v$ $(1 \le v \le n)$ —— 切换顶点 $v$ 的状态； - $2$ $u$ $v$ $(1 \le u,v \le n)$ —— 查询从 $G_u$ 到 $H_v$ 的最短路径长度。

对于每个第二类查询，输出一个整数表示最短路径长度。若路径不存在，输出 $\texttt{-1}$。

设 $k$ 为第二类查询的数量。 - （$3$ 分）：$n \le 16$，$q \le 16$； - （$3$ 分）：$n \le 16$，$q \le 2 \cdot 10^5$； - （$2$ 分）：$n \le 2000$，$q \le 2 \cdot 10^5$，$k \le 5$； - （$8$ 分）：$n \le 2000$，$q \le 2000$； - （$9$ 分）：$n \le 2 \cdot 10^5$，$q \le 2 \cdot 10^5$，$k \le 5$； - （$30$ 分）：$n \le 2 \cdot 10^5$，$q \le 2 \cdot 10^5$，且第二类查询后不会出现第一类查询； - （$45$ 分）：无额外限制。 翻译由 DeepSeek V3 完成