← 返回题目列表

Codeforces · 2002/D1

D1. DFS 检查器(简易版)

中文机器翻译题面 查看原题

这是问题的简单版本。在此版本中,给定的树是完美二叉树,并且对 $$$n$$$ 和 $$$q$$$ 的约束较低。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。

给你一个完美的二叉树$$$^\dagger$$$,由$$$n$$$个顶点组成。顶点编号从$$$1$$$到$$$n$$$,根是顶点$$$1$$$。您还获得了 $$$[1,2,\ldots,n]$$$ 的排列 $$$p_1, p_2, \ldots, p_n$$$。

您需要回答 $$$q$$$ 查询。对于每个查询,都会给出两个整数 $$$x$$$、$$$y$$$;您需要交换 $$$p_x$$$ 和 $$$p_y$$$ 并确定 $$$p_1, p_2, \ldots, p_n$$$ 是否是给定树的有效 DFS 顺序 $$$^\ddagger$$$。

请注意,交换通过查询是持久的。

$$$^\dagger$$$ 完美二叉树是以顶点 $$$1$$$ 作为根的树,大小为 $$$n=2^k-1$$$ 为正整数 $$$k$$$,其中每个顶点 $$$i$$$ ($$$1<i\le n$$$) 的父节点为$$$\left\lfloor\frac{i}{2}\right\rfloor$$$。因此,这棵树的所有叶子与根的距离为 $$$k - 1$$$。

$$$^\ddagger$$$ 通过在给定树上调用以下 $$$\texttt{dfs}$$$ 函数来找到 DFS 顺序。

请注意,DFS 顺序不是唯一的。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1\le t\le10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$, $$$q$$$ ($$$3\le n\le 65\,535$$$, $$$2\le q\le 5 \cdot 10^4$$$) - 树中的顶点数和查询数。对于正整数 $$$k$$$,保证 $$$n=2^k-1$$$。

下一行包含 $$$n-1$$$ 整数 $$$a_2,a_3,\ldots,a_n$$$ ($$$1\le a_i<i$$$) - 给定树中每个顶点的父节点。保证$$$a_i=\left\lfloor\frac{i}{2}\right\rfloor$$$。

下一行包含 $$$n$$$ 整数 $$$p_1,p_2,\ldots,p_n$$$($$$1\le p_i\le n$$$,所有 $$$p_i$$$ 都是不同的)— 初始排列 $$$p$$$。

接下来的 $$$q$$$ 行每行包含两个整数 $$$x$$$、$$$y$$$ ($$$1\le x,y\le n,x\neq y$$$) — 排列中要交换的元素的位置。

保证所有$$$n$$$的总和不超过$$$65\,535$$$,所有$$$q$$$的总和不超过$$$5 \cdot 10^4$$$。

输出

对于每个测试用例,打印与 $$$q$$$ 查询相对应的 $$$q$$$ 行。对于每个查询,如果存在完全等于当前排列的 DFS 顺序,则输出 $$$\texttt{YES}$$$,否则输出 $$$\texttt{NO}$$$。

您可以在任何情况下输出 $$$\texttt{Yes}$$$ 和 $$$\texttt{No}$$$(例如,字符串 $$$\texttt{yEs}$$$、$$$\texttt{yes}$$$、$$$\texttt{Yes}$$$ 和 $$$\texttt{YES}$$$ 将被识别为肯定响应)。

示例

输入 #1

2
3 3
1 1
1 2 3
2 3
3 2
1 3
7 4
1 1 2 2 3 3
1 2 3 4 5 6 7
3 5
2 5
3 7
4 6

输出 #1

YES
YES
NO
YES
NO
NO
YES

注意

在第一个测试用例中,每次修改后的排列 $$$p_1, p_2, \ldots, p_n$$$ 分别为 $$$[1,3,2],[1,2,3],[3,2,1]$$$。前两个排列是有效的 DFS 订单;第三个不是DFS订单。

在第二个测试用例中,每次修改后的排列 $$$p_1, p_2, \ldots, p_n$$$ 为 $$$[1,2,5,4,3,6,7],[1,3,5,4,2,6,7],[1,3,7,4,2,6,5],[1,3,7,6,2,4,5]$$$,分别。