← 返回题目列表

Codeforces · 2002/D2

D2. DFS 检查器(硬版)

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

这是问题的困难版本。在此版本中,您将获得一棵通用树,并且对 $$$n$$$ 和 $$$q$$$ 的约束更高。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。

给你一棵由 $$$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 顺序 $$$^\dagger$$$ 。

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

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

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

输入

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

每个测试用例的第一行包含两个整数 $$$n$$$, $$$q$$$ ($$$2\le n\le 3\cdot 10^5$$$, $$$2\le q\le 10^5$$$) - 树中的顶点数和查询数。

下一行包含 $$$n-1$$$ 整数 $$$a_2,a_3,\ldots,a_n$$$ ($$$1\le a_i<i$$$) - 给定树中每个顶点的父节点。

下一行包含 $$$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$$$的总和不超过$$$3\cdot 10^5$$$,所有$$$q$$$的总和不超过$$$10^5$$$。

输出

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

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

示例

输入 #1

3
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
5 4
1 1 3 4
2 3 4 5 1
5 1
4 5
3 4
2 3

输出 #1

YES
YES
NO
YES
NO
NO
YES
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]$$$,分别。