概要

この問題は、与えられた \(N\) ノード \(M\) 辺の有向グラフが、5つの特定の条件を満たす「正しい二分決定木」であるかどうかを判定する問題です。条件はグラフの構造（木であること）から、各ノードに割り当てられた区間や値の整合性まで多岐にわたります。

考察

一見複雑に見えますが、条件を整理すると「グラフ構造の検証」と「親子・兄弟間の属性チェック」の2段階に分けられます。

1. グラフ構造の検証（条件1, 2）:

   • ノード 1 を根とする木であるためには、辺の総数 \(M\) が \(N-1\) 本である必要があります。
   • 各ノードの入次数を確認し、ノード 1 が 0、それ以外が 1 であることをチェックします。
   • 各ノードから出るラベル 0, 1 の辺がそれぞれ高々 1 本であることを確認します。
   • 最後に、根（ノード 1）からすべてのノードに到達可能かを判定します（閉路がなく、連結であることの確認）。

2. 属性の整合性検証（条件3, 4, 5）:

   • これらは「親と子」、あるいは「同じ親を持つ子同士（兄弟）」の関係性のみをチェックすればよい条件です。
   • 条件3（区間の包含）: 親 \(u\) と子 \(v\) について、\(L_u < L_v\) かつ \(R_v < R_u\)。
   • 条件4（位置の整合性）: 親 \(u\) と子 \(v\) について、\(Q_u = P_v\)。
   • 条件5（左右の順序）: 同じ親 \(u\) を持つラベル 0 の子 \(x\) とラベル 1 の子 \(y\) について、\(R_x < L_y\)。

これらの条件は、グラフを走査（BFSやDFS）しながら各ノードとその隣接ノードを調べることで、一度に判定可能です。

アルゴリズム

以下の手順で判定を行います。

1. 入力と基本チェック:

   • 各ノードの情報を配列に格納します。
   • 辺の情報を読み込みながら、各ノードの入次数と、各ラベル（0, 1）に対応する子の番号を記録します。このとき、同じラベルの辺が複数あれば即座に NO と判定します。
   • 辺の数 \(M\) が \(N-1\) でない場合、またはノード 1 の入次数が 0 でない場合、他のノードの入次数が 1 でない場合は NO です。

2. 走査による詳細チェック:

   • ノード 1 を開始点として BFS（幅優先探索）を行います。
   • 各ノード \(u\) について、存在する子 \(v\)（ラベル 0 または 1）に対し、以下のチェックを行います：
     • \(v\) が既に訪問済みなら（木ではないため）NO。
     • 区間の包含関係（条件3）を満たさないなら NO。
     • 位置の整合性（条件4）を満たさないなら NO。
   • ノード \(u\) にラベル 0 の子 \(v_0\) とラベル 1 の子 \(v_1\) の両方が存在する場合：
     • 左右の順序（条件5）を満たさないなら NO。

3. 最終判定:

   • 走査が終わった後、訪問したノードの総数が \(N\) であれば、すべての条件を満たしたことになり YES を出力します。そうでなければ（孤立したノードや閉路がある場合） NO を出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • 辺の情報の読み込みに \(O(M)\)、各ノードと辺を一度ずつ走査する BFS に \(O(N + M)\) かかります。制約 \(N, M \le 2 \times 10^5\) に対して十分に高速です。
• 空間計算量: \(O(N)\)
  • ノード情報、入次数、子の情報を格納する配列に \(O(N)\) のメモリを使用します。

実装のポイント

• 1-based indexing: ノード番号が 1 から始まるため、配列のサイズを \(N+1\) で確保すると実装がスムーズです。

• 早期終了: 条件に違反した時点で即座に NO を出力して終了することで、無駄な計算を省けます。

• 高速な入出力: 競技プログラミングの定石通り、ios_base::sync_with_stdio(false); cin.tie(NULL); を使用して入出力を高速化します。

  ソースコード

#include <iostream>
#include <vector>

using namespace std;

/**
 * Problem: Verifying a Binary Decision Tree
 * 
 * We need to check if a given directed graph with N nodes and M edges
 * represents a "correct binary decision tree" based on five specific conditions:
 * 1. Rooted tree structure starting from node 1.
 * 2. Each node has at most one outgoing edge for label 0 and at most one for label 1.
 * 3. Child's interval [L_v, R_v] must be strictly contained in parent's [L_u, R_u].
 * 4. Arrival position P_v of a child must match departure position Q_u of its parent.
 * 5. If a node has both label-0 and label-1 children, the label-0 child's interval 
 *    must be strictly to the left of the label-1 child's interval (R_child0 < L_child1).
 */

struct Node {
    long long l, r, p, q;
};

int main() {
    // Fast I/O setup
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    // Read node information: interval [L_i, R_i], arrival P_i, departure Q_i
    vector<Node> nodes(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> nodes[i].l >> nodes[i].r >> nodes[i].p >> nodes[i].q;
    }

    vector<int> in_degree(n + 1, 0);
    vector<int> child0(n + 1, 0);
    vector<int> child1(n + 1, 0);
    bool possible = true;

    // Process edges and check Condition 2 (out-degree constraints)
    for (int i = 0; i < m; ++i) {
        int u, v, b;
        cin >> u >> v >> b;
        // Basic range checks for safety
        if (u < 1 || u > n || v < 1 || v > n) {
            possible = false;
            continue;
        }
        
        in_degree[v]++;
        
        // Label-based child assignment
        if (b == 0) {
            if (child0[u] != 0) possible = false; // Violation: more than one label-0 edge
            child0[u] = v;
        } else if (b == 1) {
            if (child1[u] != 0) possible = false; // Violation: more than one label-1 edge
            child1[u] = v;
        } else {
            possible = false; // Label must be 0 or 1
        }
    }

    // Condition 1: Check basic tree structure requirements
    // For N nodes to form a tree, we must have M = N-1 edges.
    if (m != n - 1) possible = false;
    
    if (possible) {
        // Node 1 must have no incoming edges (root)
        if (in_degree[1] != 0) possible = false;
        // Every other node must have exactly one incoming edge
        for (int i = 2; i <= n; ++i) {
            if (in_degree[i] != 1) {
                possible = false;
                break;
            }
        }
    }

    // Early exit if basic structural conditions fail
    if (!possible) {
        cout << "NO" << endl;
        return 0;
    }

    // Use BFS to verify reachability and check conditions 3, 4, and 5
    vector<int> q;
    q.reserve(n);
    q.push_back(1);
    vector<bool> visited(n + 1, false);
    visited[1] = true;
    int head = 0;

    while (head < q.size()) {
        int u = q[head++];
        int v0 = child0[u];
        int v1 = child1[u];

        // Process label-0 child
        if (v0 != 0) {
            // Check reachability/cycle (though redundant given structural checks)
            if (visited[v0]) {
                cout << "NO" << endl;
                return 0;
            }
            // Condition 3: Strict containment (L_u < L_v and R_v < R_u)
            if (!(nodes[u].l < nodes[v0].l && nodes[v0].r < nodes[u].r)) {
                cout << "NO" << endl;
                return 0;
            }
            // Condition 4: Position consistency (P_v = Q_u)
            if (nodes[v0].p != nodes[u].q) {
                cout << "NO" << endl;
                return 0;
            }
            visited[v0] = true;
            q.push_back(v0);
        }

        // Process label-1 child
        if (v1 != 0) {
            if (visited[v1]) {
                cout << "NO" << endl;
                return 0;
            }
            // Condition 3: Strict containment
            if (!(nodes[u].l < nodes[v1].l && nodes[v1].r < nodes[u].r)) {
                cout << "NO" << endl;
                return 0;
            }
            // Condition 4: Position consistency
            if (nodes[v1].p != nodes[u].q) {
                cout << "NO" << endl;
                return 0;
            }
            visited[v1] = true;
            q.push_back(v1);
        }

        // Condition 5: Left-right order of children
        if (v0 != 0 && v1 != 0) {
            if (!(nodes[v0].r < nodes[v1].l)) {
                cout << "NO" << endl;
                return 0;
            }
        }
    }

    // Final reachability check: Did we visit all N nodes?
    if (q.size() == n) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }

    return 0;
}

この解説は gemini-3-flash-thinking によって生成されました。