题解：CF2002D1 DFS Checker (Easy Version)

MhxMa · 2024-08-28 14:18:24 · 题解

题意

给定一个根树和一系列查询，每次查询包括交换树的 dfs 序列中的两个元素，然后判断交换后的序列是否仍然是一个有效的 dfs 序列。

思路

先进行一遍 dfs，记录每个节点的访问顺序和子树大小。

判断 dfs 序列，对于每个查询，通过比较交换前后的时间戳和子树大小来判断是否仍然是有效的 dfs 序列。

为了提高效率，使用一个数组来记录每个节点在 dfs 序列中的有效区间，即第 i 项记录的区间应该是 [dfn_i,dfn_i + siz_i - 1] 。

简单搜索，用不着 LCA，不做过多解释，详见代码。

代码

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

const int N = 3e5 + 5;

int T;
int f[N], p[N]; // 分别存储树中每个节点的父节点和 dfs 序列中的值。
int blk[N], dfn[N]; // 分别存储每个节点在 dfs 序列中的有效区间和时间戳。
int tot, head[N], dis[N];
int dfstime, siz[N];
int ans;

struct Node {
    int from, to;
} edge[N];

void addedge(int u, int v) {
    edge[++tot] = (Node) {
        v, head[u]
    };
    head[u] = tot;
}

void dfs(int u) {
    siz[u] = 1;
    dfn[u] = ++dfstime;
    for (int i = head[u]; i; i = edge[i].to) {
        int v = edge[i].from;
        dfs(v);
        siz[u] += siz[v];
    }
    return;
}

int check(int x, int y) {
    if (!x || x == y) {
        return 1;
    }
    if (dfn[y] >= dfn[x] && dfn[y] < dfn[x] + siz[x] && siz[y] == 1) {
        return 1;
    }
    return 0;
}

void update(int x) {
    ans -= blk[p[x]];
    blk[p[x]] = check(f[p[x]], p[x - 1]);
    ans += blk[p[x]];
    return ;
}

int main() {
    scanf("%d", &T);
    for (int t = 1; t <= T; ++t) {
        int n, q;
        scanf("%d%d", &n, &q);
        dfstime = 0, ans = 0;

        for (int i = 1; i <= n; ++i) {
            head[i] = 0;
        }
        for (int i = 2; i <= n; ++i) {
            int x;
            scanf("%d", &x);
            addedge(x, i);
            f[i] = x;
        }

        dfs(1);

        for (int i = 1; i <= n; ++i) {
            scanf("%d", &p[i]);
            blk[i] = 0;
        }

        for (int i = 1; i <= n; ++i) {
            update(i);
        }
        for (int i = 1; i <= q; ++i) {
            int x, y;
            scanf("%d%d", &x, &y);
            swap(p[x], p[y]);
            update(x), update(y);
            if (x < n) {
                update(x + 1);
            }
            if (y < n) {
                update(y + 1);
            }
            if (ans == n) {
                printf("YES\n");
            } else {
                printf("NO\n");
            }
        }
    }
    return 0;
}