这是一道有向无环图(DAG)上的公平博弈 + 动态状态更新问题，核心是反向拓扑更新 + 状态传播，最终通过 $O(n+m+q)$ 复杂度解决。

一、题意回顾（精简版）

给定有向无环图，节点初始为蓝色。 两人轮流移动棋子，Cry 先手：

1. 到达无出边节点 $\rightarrow$ Cry 胜
2. 到达红色节点 $\rightarrow$ River 胜
3. 既是红点又无出边 $\rightarrow$ River 胜

两种询问：

1. 1 u：把 $u$ 染红
2. 2 u：问从 $u$ 出发，Cry 是否必胜

二、核心博弈结论（标程灵魂）

我们定义 $A[u] = 1$ 表示 Cry 必胜，$0$ 必败。

必胜 / 必败规则

1. 若 $u$ 是红点：$A[u] = 0$（River 直接赢）
2. 若 $u$ 无出边：$A[u] = 1$（Cry 直接赢）
3. 当前是 Cry 回合： 只要存在一个后继 $v$ 满足 $A[v]=1$，则 $A[u]=1$
4. 当前是 River 回合： 只有所有后继 $v$ 都满足 $A[v]=1$，$A[u]=1$

因为是 DAG，状态只从后往前传播，所以我们反向建图。

三、标程中三个数组的意义

四、算法整体流程

1. 建图

• 反向建图：$G[v].push\_back(u)$（方便从后继向前驱传播状态）
• 统计每个点的出度存入 $C[u]$

2. 处理询问

• 查询操作：直接输出 $A[u]$
• 染红操作：启动 BFS 状态传播，分两种类型更新：
  1. 类型 1（出度更新）：$C[u]--$，出度为 $0$ 时触发状态
  2. 类型 0（状态失效）：$A[u]=0$，并向前传播必败态

3. 状态传播规则（标程核心）

• 染红会让起点直接变成必败态
• 必败态会沿着反向边传播给前驱
• 出度归零会让节点变成必胜态
• 所有传播都用 BFS 完成，保证每个点只处理一次

五、C++ 标程逐段超详细注释

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T;
    cin >> T;
    while (T--) {
        int n, m, q;
        cin >> n >> m >> q;
        
        vector<vector<int>> G(n + 1);  // 反向前驱图
        vector<int> A(n + 1, 1);       // 最终答案：1=YES, 0=NO
        vector<int> B(n + 1, 0);       // 访问标记，防止重复处理
        vector<int> C(n + 1, 0);       // 节点出度
        
        // 建图：反向边 + 统计出度
        for (int i = 0; i < m; ++i) {
            int a, b;
            cin >> a >> b;
            G[b].push_back(a);    // 反向建边，v -> u
            C[a]++;              // 记录出度
        }
        
        while (q--) {
            int op, u;
            cin >> op >> u;
            
            // ======================
            // 查询操作：直接输出答案
            // ======================
            if (op == 2) {
                if (A[u]) cout << "YES\n";
                else cout << "NO\n";
            }
            
            // ======================
            // 染红操作：BFS 传播状态
            // ======================
            else {
                queue<pair<int, int>> qu;
                
                // 两种初始状态入队
                if (A[u] == 1) qu.emplace(u, 0);      // 类型0：状态更新
                if (B[u] == 0) {
                    qu.emplace(u, 1);                // 类型1：出度更新
                    B[u] = 1;
                }
                
                while (!qu.empty()) {
                    auto [x, t] = qu.front();
                    qu.pop();
                    
                    // ============================
                    // 类型 1：更新出度 C
                    // 出度减到 0 → 变成必胜态
                    // ============================
                    if (t == 1) {
                        for (int c : G[x]) {
                            C[c]--;
                            if (C[c] == 0) {
                                qu.emplace(c, 0);
                            }
                        }
                    }
                    
                    // ============================
                    // 类型 0：更新必胜态 A
                    // 染红 → A[x] = 0（必败）
                    // 必败态向前传播
                    // ============================
                    else {
                        if (A[x] == 0) continue;
                        A[x] = 0;  // 染红 → 必败
                        
                        for (int c : G[x]) {
                            if (B[c]) continue;
                            B[c] = 1;
                            qu.emplace(c, 1);
                        }
                    }
                }
            }
        }
    }
    return 0;
}

六、复杂度证明（完美通过 $2\times10^5$）

• 每个点、每条边最多入队一次
• 每个询问均摊 $O(1)$
• 总复杂度：

完全符合题目限制。

七、一句话总结解法

反向建图 + BFS 状态传播 染红触发必败态，出度为0触发必胜态，动态维护每个点的博弈状态，直接回答查询。