题意

给定 $n$ 个点，$n - 1$ 条边的图，对于每一条边 $u, v$，表示 $u$ 是 $v$ 的父亲节点。

接下来有 $m$ 次操作，对于每一次操作 $u, v$，反转 $u,v$ 之间的父子关系（保证 $u,v$ 是父子关系）。

在第一次修改前，和每次修改后，输出这张图是否是一棵有根树。

思路

对于本题中的图是不是一棵有根树，有以下几个结论：

假设该图有 $n$ 个节点，$outDep_i$ 表示点 $i$ 的出度。

• 该图是一个具有 $n-1$ 条边的有向无环图。
• 仅存在一个点满足 $outDep_i$ 的值为 $0$，该点为根节点。

根据上面结论，不难得出第一次修改前的答案。

关于每一次修改，可以根据 $u, v$ 之间的父子关系，在线更新 $u, v$ 的出度，并维护根的数量。

关于 $u, v$ 之间的父子关系，可以用一个 $fa_i$ 数组表示 $i$ 的父亲为 $fa_i$，则对于每一次修改：

假设 $fa_i$ 的值为 $0$，则 $i$ 无父亲节点。

• 若 $fa_u = v$，则 $fa_v \leftarrow u$，$fa_u \leftarrow 0$，$outDep_u \leftarrow outDep_u - 1$，$outDep_v \leftarrow outDep_v + 1$。
• 若 $fa_v = u$，则 $fa_u \leftarrow v$，$fa_v \leftarrow 0$，$outDep_v \leftarrow outDep_v - 1$，$outDep_u \leftarrow outDep_u + 1$。

然后根据每一次修改后根的数量来判断该图是否是一棵有根树即可。

code

#include<bits/stdc++.h>

using namespace std;

const int N = 3e5 + 10;
int inDep[N], outDep[N], fa[N];

int main() {
    int n, cnt = 0;
    cin >> n;

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        fa[v] = u;
        inDep[u]++; outDep[v]++;
    }
    int rt = 0;
    for (int i = 1; i <= n; i++) {
        if (outDep[i] == 0) rt++;
    }

    if (rt == 1) cout << "DA\n";
    else cout << "NE\n";

    int m;
    cin >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        if (fa[v] == u) {
            fa[u] = v; fa[v] = 0;
            if (++outDep[u] == 1) rt--;
            if (--outDep[v] == 0) rt++;

        } else {
            fa[v] = u; fa[u] = 0;
            if (--outDep[u] == 0) rt++;
            if (++outDep[v] == 1) rt--;
        }
        if (rt == 1) cout << "DA\n";
        else cout << "NE\n";
    }
    return 0;
}