完美二叉树 DFS 序合法性判断 题解

问题重述

给定一棵完美二叉树（$n = 2^k - 1$ 个节点，根为 $1$，节点 $i$ 的父节点为 $\lfloor i/2 \rfloor$），以及一个排列 $p[1..n]$ 表示某个 DFS 遍历顺序。需要回答 $q$ 个查询，每个查询交换 $p$ 中的两个位置，并判断当前排列是否可能是某个合法的 DFS 顺序。

DFS 规则：先访问当前节点，然后以任意顺序递归访问子节点。

---

核心观察

在 DFS 过程中，对于任意节点 $v$：

1. 节点 $v$ 必须出现在其所有后代节点之前。
2. 节点 $v$ 的子节点在遍历顺序中必须连续出现，并且它们所覆盖的区间恰好填满 $v$ 的整个子树区间（除去 $v$ 自身）。

设 $pos[u]$ 表示节点 $u$ 在排列中的位置（即 $p[pos[u]] = u$），$siz[u]$ 表示以 $u$ 为根的子树大小。

对于节点 $v$ 及其子节点集合 $son[v]$（完美二叉树中 $|son[v]| = 0$ 或 $2$），将子节点按 $pos$ 值从小到大排序得到 $c_1, c_2, \dots, c_m$，则合法 DFS 序必须满足：

$$pos[c_1] = pos[v] + 1$$ $$pos[c_{i+1}] = pos[c_i] + siz[c_i], \quad 1 \le i < m $$$$pos[c_m] + siz[c_m] = pos[v] + siz[v]$$

如果 $v$ 是叶子节点（$son[v]$ 为空），则自动满足条件。

---

判定条件的等价形式

上述三个条件可以合并为一个简洁的判定：

设 $first = \min\{pos[c] \mid c \in son[v]\}$，$last = \max\{pos[c] \mid c \in son[v]\}$，$lastNode = p[last]$（即最后一个子节点的编号）。

那么条件等价于：

$$pos[v] < first$$

且

$$last + siz[lastNode] \le pos[v] + siz[v]$$

在合法情况下，第二个不等式实际上取等号。用 $\le$ 足以判断：若 $last + siz[lastNode] > pos[v] + siz[v]$，则最后一个子节点的子树超出了 $v$ 的子树范围，非法。

---

数据结构设计

为了高效处理交换操作，维护以下信息：

• $p[i]$：排列中第 $i$ 个位置上的节点编号。
• $q[x]$：节点 $x$ 在排列中的位置，即 $q[x] = pos[x]$。
• $siz[x]$：节点 $x$ 的子树大小，可以通过一次自底向上遍历计算得到。
• $son[x]$：一个有序集合（如 C++ 中的 set），存储节点 $x$ 的子节点在排列中的位置，即 $son[x] = \{ pos[c] \mid c \in \text{children}(x) \}$。

使用有序集合是为了快速获取子节点位置的最小值和最大值。

---

初始化的计算

1. 读入 $n, q$ 和父节点信息。
2. 初始化 $siz[x] = 1$，然后从 $n$ 到 $2$ 倒序累加：$siz[fa[i]] \text{ += } siz[i]$。
3. 读入初始排列 $p$，同时建立逆映射 $q[p[i]] = i$。
4. 对于每个节点 $x$，将其子节点的位置插入 $son[fa[x]]$ 中。
5. 计算每个节点是否合法，得到初始合法节点总数 $cnt$。

---

处理交换操作

每次交换 $p[i]$ 和 $p[j]$，记 $x = p[i]$，$y = p[j]$。

受影响节点

交换会影响以下节点的合法性：

• 节点 $x$ 本身（因为它的位置改变了）
• 节点 $y$ 本身
• 节点 $x$ 的父节点 $fa[x]$（因为子节点集合变化了）
• 节点 $y$ 的父节点 $fa[y]$

注意 $fa[x]$ 和 $fa[y]$ 可能相同，需要去重。

更新步骤

1. 将 $x, y, fa[x], fa[y]$ 加入一个集合 $S$。
2. 对于 $S$ 中的每个节点 $u$，从全局计数 $cnt$ 中减去 $chk(u)$。
3. 从父节点的子节点集合中删除旧位置：
   • $son[fa[x]].erase(i)$
   • $son[fa[y]].erase(j)$
4. 交换 $p[i]$ 与 $p[j]$，同时交换 $q[x]$ 与 $q[y]$。
5. 将新位置插入父节点的子节点集合：
   • $son[fa[x]].insert(j)$
   • $son[fa[y]].insert(i)$
6. 对于 $S$ 中的每个节点 $u$，重新计算 $chk(u)$ 并加回 $cnt$。
7. 如果 $cnt = n$，则所有节点都合法，输出 "YES"，否则输出 "NO"。

---

复杂度分析

• 每个节点只需要 $O(1)$ 时间判断合法性。
• 对有序集合的插入、删除、查找最小值和最大值操作都是 $O(\log n)$。
• 每次交换只更新常数个节点（最多 $4$ 个）。
• 总时间复杂度：$O((n + q) \log n)$。
• 空间复杂度：$O(n)$。

题目约束 $\sum n \le 65535$，$\sum q \le 5 \times 10^4$，完全可行。

---

正确性说明

该算法的正确性基于以下事实：

• DFS 序的合法性可以分解为每个节点的子树是否合法，并且这些条件相互独立。
• 每个节点的合法性只依赖于其子节点在排列中的位置关系，以及子树大小。
• 交换操作只会影响被交换的两个节点及其父节点，因此只需要局部更新。
• 通过维护所有节点合法性的计数，可以在 $O(1)$ 时间内回答每个查询。