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<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$），表示要交换排列中第 $x$ 和第 $y$ 个元素。

保证所有测试用例中 $n$ 的总和不超过 $3\cdot 10^5$，所有 $q$ 的总和不超过 $10^5$。

对于每组测试用例的每个询问，输出一行。如果当前排列是该树的某个合法 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 翻译