P17525 [ECUSTPC 2026 Fall] 魔女审判

你拿着的三叉戟再次击中了村民，但这一次，当审判结束，你却发现自己已经找不到它了。 据你所知，你的三叉戟落在一棵有 $n$ 个结点以 $1$ 号结点为根的有根树 $T$。每个结点都有一个权值 $a_i$，并且任意时刻所有结点的权值都恰好构成 $1 \sim n$ 的一个排列。对于树上的两个结点 $u,v$，记它们之间的简单路径为 $P(u,v)$，注意此处 $u , v \in P(u, v)$。 定义一个树上结点集合 $S$ 为一个**三叉**，当且仅当存在三个结点 $F$，$x$，$y$（可以相同），满足： - $F$ 是 $x$ 的祖先或 $F=x$； - $F$ 是 $y$ 的祖先或 $F=y$； - $S = P(F,x)\cup P(F,y)$； 你需要按顺序处理 $q$ 次操作，操作共有三种： **操作 1：引雷**，给定两个结点 $x$ 和 $y$，交换它们当前的权值。 **操作 2：审判**，给定两个不同的权值 $l < r$，翻转 $[l, r]$ 区间内的权值。 形式化地，对所有的权值进行如下的变化，设操作前结点 $x$ 的权值为 $a_x$，操作后为 $a_x'$，定义 $$ a'_x= \begin{cases} l+r-a_x, & l\le a_x\le r,\\ a_x, & \text{otherwise}. \end{cases} $$ 随后对所有 $1 \le x \le n$ 的整数 $x$，同时令 $a_x \leftarrow a'_x$，可以证明操作前后序列始终是 $1 \sim n$ 的一个排列。 **操作 3：寻戟**，给定 $l \le r$，判断 $S=\{x \in \mathbb{N}, 1\le x \le n \mid l\le a_x\le r\}$ 是否是一个**三叉**。 请依次回答所有**操作 3：寻戟**所提出的问题。

第一行输入一个整数 $T$ ($1 \le T \le 10^3$)，表示测试数据的数量。 每组测试数据第一行输入两个整数 $n$ 和 $q$ ($1 \le n, q \le 10^5$)，表示树上的结点数量和操作的数量。 随后 $n - 1$ 行每行输入两个整数 $u$ 和 $v$ ($1 \le u, v \le n$, $u \ne v$)，表示树上存在一条连接 $u$ 和 $v$ 的边。 随后一行输入 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$)，表示每个结点的权值。 随后 $q$ 行每行表示一次操作，第 $i$ 行首先输入一个整数 $\text{op}_i$ ($1 \le op_i \le 3$)，表示操作类型，随后格式如下： - 若 $\text{op}_i = 1$，随后输入两个整数 $x$ 和 $y$ ($1 \le x, y \le n$)，表示进行一次**操作 1：引雷**，交换 $x$ 和 $y$ 的权值。 - 若 $\text{op}_i = 2$，随后输入两个整数 $l$ 和 $r$ ($1 \le l < r \le n$)，表示进行一次**操作 2：审判**，翻转权值在 $[l,r]$ 的点的权值。 - 若 $\text{op}_i = 3$，随后输入两个整数 $l$ 和 $r$ ($1 \le l \le r \le n$)，表示进行一次**操作 3：寻戟**，查询权值在 $[l,r]$ 之间的点是否构成一个**三叉**。 保证单组测试数据内，所有结点的权值构成 $1\sim n$ 的一个排列，给定的边形成一棵 $n$ 个结点的树。 保证所有测试数据的 $\sum n \le 3 \times 10^5$，$\sum q \le 3 \times 10^5$。

对于每组测试数据中指令类型为**操作 3：寻戟**的指令输出一行一个字符串： - 若 $S=\{x \in \mathbb{N}, 1\le x \le n \mid l\le a_x\le r\}$ 是一个**三叉**，则输出 `YES`； - 反之则输出 `NO`。 注意评测时不会区分 `YES` 和 `NO` 的大小写，换言之当答案是肯定的时候输出 `yes`、`YES`、`Yes`、`YeS` 等都会被认为是正确的。

 对于第 $1$ 组测试数据的第三次寻戟，经过前一次审判操作后， 当前各结点的权值为 $$ (a_1,a_2,\ldots,a_7)=(4,6,2,7,5,3,1). $$ 此时权值 $4,5,6,7$ 分别位于结点 $1,5,2,4$，因此 $S=\{1,2,4,5\}$。 取 $F=1$，$x=4$，$y=5$，依次验证条件： - 结点 $1$ 是结点 $4$ 的祖先。 - 结点 $1$ 是结点 $5$ 的祖先。 - $P(1,4)\cup P(1,5) =\{1,2,4\}\cup\{1,2,5\}=S$。 因此 $S$ 是一个**三叉**。