#P17525. [ECUSTPC 2026 Fall] 魔女审判
[ECUSTPC 2026 Fall] 魔女审判
题目描述
你拿着的三叉戟再次击中了村民,但这一次,当审判结束,你却发现自己已经找不到它了。
据你所知,你的三叉戟落在一棵有 个结点以 号结点为根的有根树 。每个结点都有一个权值 ,并且任意时刻所有结点的权值都恰好构成 的一个排列。对于树上的两个结点 ,记它们之间的简单路径为 ,注意此处 。
定义一个树上结点集合 为一个三叉,当且仅当存在三个结点 ,,(可以相同),满足:
- 是 的祖先或 ;
- 是 的祖先或 ;
- ;
你需要按顺序处理 次操作,操作共有三种:
操作 1:引雷,给定两个结点 和 ,交换它们当前的权值。
操作 2:审判,给定两个不同的权值 ,翻转 区间内的权值。
形式化地,对所有的权值进行如下的变化,设操作前结点 的权值为 ,操作后为 ,定义
$$a'_x= \begin{cases} l+r-a_x, & l\le a_x\le r,\\ a_x, & \text{otherwise}. \end{cases}$$随后对所有 的整数 ,同时令 ,可以证明操作前后序列始终是 的一个排列。
操作 3:寻戟,给定 ,判断 $S=\{x \in \mathbb{N}, 1\le x \le n \mid l\le a_x\le r\}$ 是否是一个三叉。
请依次回答所有操作 3:寻戟所提出的问题。
输入格式
第一行输入一个整数 (),表示测试数据的数量。
每组测试数据第一行输入两个整数 和 (),表示树上的结点数量和操作的数量。
随后 行每行输入两个整数 和 (, ),表示树上存在一条连接 和 的边。
随后一行输入 个整数 (),表示每个结点的权值。
随后 行每行表示一次操作,第 行首先输入一个整数 (),表示操作类型,随后格式如下:
- 若 ,随后输入两个整数 和 (),表示进行一次操作 1:引雷,交换 和 的权值。
- 若 ,随后输入两个整数 和 (),表示进行一次操作 2:审判,翻转权值在 的点的权值。
- 若 ,随后输入两个整数 和 (),表示进行一次操作 3:寻戟,查询权值在 之间的点是否构成一个三叉。
保证单组测试数据内,所有结点的权值构成 的一个排列,给定的边形成一棵 个结点的树。
保证所有测试数据的 ,。
输出格式
对于每组测试数据中指令类型为操作 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
7 6
1 2
1 3
2 4
2 5
3 6
3 7
4 2 6 1 3 5 7
3 1 3
3 1 5
2 1 7
3 4 7
1 4 5
3 5 7
YES
NO
YES
YES
提示

对于第 组测试数据的第三次寻戟,经过前一次审判操作后, 当前各结点的权值为
此时权值 分别位于结点 ,因此 。
取 ,,,依次验证条件:
- 结点 是结点 的祖先。
- 结点 是结点 的祖先。
- 。
因此 是一个三叉。