CF2002D2 DFS Checker (Hard Version)

这是该问题的困难版本。在本版本中，给定的是一棵通用树，且 $n$ 和 $q$ 的约束更高。只有在两个版本都被解决的情况下，你才能进行 hack。 给定一棵有 $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$ DFS 序是通过对给定树调用如下 $\texttt{dfs}$ 函数得到的。 ``` dfs_order = [] function dfs(v): append v to the back of dfs_order pick an arbitrary permutation s of children of v for child in s: dfs(child) dfs(1) ``` 注意，DFS 序不是唯一的。

每组测试包含多组测试用例。第一行包含测试用例数 $t$（$1\le t\le 10^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

对于每组测试用例的每个询问，输出一行。如果当前排列是该树的某个合法 DFS 序，输出 $\texttt{YES}$，否则输出 $\texttt{NO}$。 你可以以任意大小写输出 $\texttt{Yes}$ 和 $\texttt{No}$（例如，$\texttt{yEs}$、$\texttt{yes}$、$\texttt{Yes}$ 和 $\texttt{YES}$ 都会被识别为正面回答）。

在第一个测试用例中，每次修改后的排列 $p_1, p_2, \ldots, p_n$ 分别为 $[1,3,2]$、$[1,2,3]$、$[3,2,1]$。前两个排列是合法的 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]$。 由 ChatGPT 4.1 翻译