33OJ
登录 注册

#P17525. [ECUSTPC 2026 Fall] 魔女审判

    ID: 20253 远端评测题 6000ms 1024MiB 尝试: 0 已通过: 0 显示难度省选/NOI− 上传者: 标签>平衡树Special Judge2026高校校赛

[ECUSTPC 2026 Fall] 魔女审判

题目描述

你拿着的三叉戟再次击中了村民,但这一次,当审判结束,你却发现自己已经找不到它了。

据你所知,你的三叉戟落在一棵有 nn 个结点以 11 号结点为根的有根树 TT。每个结点都有一个权值 aia_i,并且任意时刻所有结点的权值都恰好构成 1∼n1 \sim n 的一个排列。对于树上的两个结点 u,vu,v,记它们之间的简单路径为 P(u,v)P(u,v),注意此处 u,v∈P(u,v)u , v \in P(u, v)。

定义一个树上结点集合 SS 为一个三叉,当且仅当存在三个结点 FF,xx,yy(可以相同),满足:

  • FF 是 xx 的祖先或 F=xF=x;
  • FF 是 yy 的祖先或 F=yF=y;
  • S=P(F,x)∪P(F,y)S = P(F,x)\cup P(F,y);

你需要按顺序处理 qq 次操作,操作共有三种:

操作 1:引雷,给定两个结点 xx 和 yy,交换它们当前的权值。

操作 2:审判,给定两个不同的权值 l<rl < r,翻转 [l,r][l, r] 区间内的权值。

形式化地,对所有的权值进行如下的变化,设操作前结点 xx 的权值为 axa_x,操作后为 ax′a_x',定义

$$a'_x= \begin{cases} l+r-a_x, & l\le a_x\le r,\\ a_x, & \text{otherwise}. \end{cases}$$

随后对所有 1≤x≤n1 \le x \le n 的整数 xx,同时令 ax←ax′a_x \leftarrow a'_x,可以证明操作前后序列始终是 1∼n1 \sim n 的一个排列。

操作 3:寻戟,给定 l≤rl \le r,判断 $S=\{x \in \mathbb{N}, 1\le x \le n \mid l\le a_x\le r\}$ 是否是一个三叉。

请依次回答所有操作 3:寻戟所提出的问题。

输入格式

第一行输入一个整数 TT (1≤T≤1031 \le T \le 10^3),表示测试数据的数量。

每组测试数据第一行输入两个整数 nn 和 qq (1≤n,q≤1051 \le n, q \le 10^5),表示树上的结点数量和操作的数量。

随后 n−1n - 1 行每行输入两个整数 uu 和 vv (1≤u,v≤n1 \le u, v \le n, u≠vu \ne v),表示树上存在一条连接 uu 和 vv 的边。

随后一行输入 nn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_n (1≤ai≤n1 \le a_i \le n),表示每个结点的权值。

随后 qq 行每行表示一次操作,第 ii 行首先输入一个整数 opi\text{op}_i (1≤opi≤31 \le op_i \le 3),表示操作类型,随后格式如下:

  • 若 opi=1\text{op}_i = 1,随后输入两个整数 xx 和 yy (1≤x,y≤n1 \le x, y \le n),表示进行一次操作 1:引雷,交换 xx 和 yy 的权值。
  • 若 opi=2\text{op}_i = 2,随后输入两个整数 ll 和 rr (1≤l<r≤n1 \le l < r \le n),表示进行一次操作 2:审判,翻转权值在 [l,r][l,r] 的点的权值。
  • 若 opi=3\text{op}_i = 3,随后输入两个整数 ll 和 rr (1≤l≤r≤n1 \le l \le r \le n),表示进行一次操作 3:寻戟,查询权值在 [l,r][l,r] 之间的点是否构成一个三叉。

保证单组测试数据内,所有结点的权值构成 1∼n1\sim n 的一个排列,给定的边形成一棵 nn 个结点的树。

保证所有测试数据的 ∑n≤3×105\sum n \le 3 \times 10^5,∑q≤3×105\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
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

提示

对于第 11 组测试数据的第三次寻戟,经过前一次审判操作后, 当前各结点的权值为

(a1,a2,…,a7)=(4,6,2,7,5,3,1).(a_1,a_2,\ldots,a_7)=(4,6,2,7,5,3,1).

此时权值 4,5,6,74,5,6,7 分别位于结点 1,5,2,41,5,2,4,因此 S={1,2,4,5}S=\{1,2,4,5\}。

取 F=1F=1,x=4x=4,y=5y=5,依次验证条件:

  • 结点 11 是结点 44 的祖先。
  • 结点 11 是结点 55 的祖先。
  • P(1,4)∪P(1,5)={1,2,4}∪{1,2,5}=SP(1,4)\cup P(1,5) =\{1,2,4\}\cup\{1,2,5\}=S。

因此 SS 是一个三叉。