题解：CF2002D2 DFS Checker (Hard Version)

· · 题解

前面转自我的 D1 题解。

题目分析

题解记号说明：

这场做起来最顺手的题目就是 D 了。

每次 O(n) 暴力判断 p 是否合法显然不可取。那么我们就需要对于每次操作维护一些东西，使得查询合法情况可以 O(1)/O(\log n)。

我们知道，若 p 是一个合法的 DFS 序，等价于 p 满足这个性质：

注意，这是充分必要条件。下面我们对这个性质进行证明。

充分性证明

即：若 p 是一个合法的 DFS 序，则 \forall i\in[1,n-1]\cap\Z,f_{p_{i+1}}\in a_{p_i}。

我们按照 p_i 号节点在树中的位置进行分类讨论：

它是一个非叶子节点

若 p_i 号节点是一个非叶子节点，那么在 DFS 函数中的下一步操作肯定是访问它的一个子节点，也就是 p_{i+1} 号节点。那么 f_{p_{i+1}} 就是 p_i，满足这条性质。

它是一个叶子节点

若 p_i 号节点是一个叶子节点，那么在 DFS 函数中的下一步操作肯定是回溯，也就是跳回到 p_i 号节点的某个祖先节点，然后访问这个祖先节点的另一个没被访问过的子节点 p_{i+1}。那么根据定义 f_{p_{i+1}} 是 p_i 的某个祖先节点，满足这条性质。

充分性证明完毕。

必要性证明

即：若 p 满足 \forall i\in[1,n-1]\cap\Z,f_{p_{i+1}}\in a_{p_i}，则 p 是一个合法的 DFS 序。

我们任取一个编号为 u 的节点，记以 u 号节点为根的子树为 U，并取任何一对 p_i,p_{i+1} 满足 p_i\notin U,p_{i+1}\in U。因为 f_u 有不属于 U 的节点（例如 f_u 本身就不属于 U），所以有 p_{i+1}=u。

这样，我们知道每一个子树至多被访问一次，且肯定在一个合法 DFS 序中的一个连续的子序列中，并且第一个访问到的节点肯定是这个子树的根节点。这足以说明 p 是一个合法的 DFS 序了。

题目做法

我们有了这条性质，那我们就可以对于每一个 i\in[1,n-1]\cap\Z，记录是否有 vp_i=f_{p_{i+1}}\in a_{p_i}。同时记录满足此性质的 i 的数量 vc。

每次操作时，更新 x,y 所对应的 vp_x,vp_y 以及 vc，判断是否有 vc=n-1。若满足，则合法；否则不合法。

那么现在的重点就在于：给定 i，判断是否有 f_{p_{i+1}}\in a_{p_i}。我们有很多的方法来解决这个问题。

转 LCA

D1 题解中的暴力跳解法本质上就是判祖先转成 LCA。根据如下性质：

x\in a_{y}\iff \operatorname{lca}(x,y)=x

我们可以采取任何的技术来高效求解 \operatorname{lca}(x,y)，比如你可以用欧拉序搭配 Four Russian RMQ 做到 O(n) 预处理 O(1) 查询。

size 搭配 dfn

利用 size 搭配 dfn 求解。根据如下性质：

x\in a_y\iff[dfn_y,dfn_y+size_y)\subseteq[dfn_x,dfn_x+size_x)

证明：根据前面的证明，我们知道每一个子树肯定在一个合法 DFS 序中的一个连续的子序列中，并且第一个访问到的节点肯定是这个子树的根节点。

那么根据定义，u 号节点为根的子树所对应的连续子序列的左端点就是 dfn_u，长度是 size_u，则这个连续子序列就是 [dfn_u,dfn_u+size_u)。

祖先节点为根的子树肯定包含后辈节点为根的子树，所以它们对应的连续子序列应当也满足这个包含关系。

此解法可以 O(n) 预处理 O(1) 回答询问且常数比 LCA 解法小很多，是本题最优解法。

代码

以 size 搭配 dfn 为例。

#include <bits/stdc++.h>
using namespace std;

const int MaxN = 300000 + 5;
int T, N, Q, dfsTime, validCount;
int dfsOrder[MaxN], dfn[MaxN], parent[MaxN], treeSize[MaxN];
bitset<MaxN> validPosition;
vector<vector<int>> tree;

bool isAncestor(int ancestor, int descendant) {
    return dfn[ancestor] <= dfn[descendant] && dfn[ancestor] + treeSize[ancestor] >= dfn[descendant] + treeSize[descendant];
}

bool initialize() {
    function<int(int)> dfs = [&](int current) {
        treeSize[current] = 1;
        dfn[current] = ++dfsTime;
        for (int i : tree[current])
            treeSize[current] += dfs(i);
        return treeSize[current];
    };
    cin >> N >> Q;
    validCount = 0;
    validPosition.reset();
    tree.assign(N + 1, vector<int>());
    for (int i = 2; i <= N; i++) {
        cin >> parent[i];
        tree[parent[i]].push_back(i);
    }
    for (int i = 1; i <= N; cin >> dfsOrder[i++]);
    dfs(1);
    for (int i = 1; i < N; i++) 
        validCount += validPosition[i] = isAncestor(parent[dfsOrder[i + 1]], dfsOrder[i]);
    return true;
}

bool updateAnswer(int x, int y) {
    function<void(int)> updateValidPosition = [&](int position) {
        if (position != 0 && position != N && isAncestor(parent[dfsOrder[position + 1]], dfsOrder[position]) ^ validPosition[position]) {
            validPosition[position] = isAncestor(parent[dfsOrder[position + 1]], dfsOrder[position]);
            validCount += validPosition[position] ? 1 : -1;
        }
    };
    swap(dfsOrder[x], dfsOrder[y]);
    updateValidPosition(x); updateValidPosition(x - 1);
    updateValidPosition(y); updateValidPosition(y - 1);
    return validCount == N - 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for (cin >> T; T-- && initialize(); )
        for (int x, y; Q--; cout << (updateAnswer(x, y) ? "Yes\n" : "No\n"))
            cin >> x >> y;
    return 0;
}