概要

\(N\) 個のノードと \(M\) 本の有向辺からなるグラフが、5つの条件をすべて満たす「正しい二分決定木」であるかを判定する問題です。各条件を一つずつ愚直に検証すれば十分です。

考察

この問題は本質的に「与えられた条件を正確に実装できるか」を問う検証問題です。5つの条件それぞれについて、以下のように整理できます。

• 条件1（根付き木）: ノード1への入次数が0、他ノードへの入次数がちょうど1、辺数が \(N-1\)、そしてノード1から全ノードへ到達可能であること。
• 条件2（出次数制約）: 各ノードからラベル0の辺は高々1本、ラベル1の辺も高々1本。
• 条件3（区間包含）: 辺 \(u \to v\) について \(L_u < L_v\) かつ \(R_v < R_u\)。
• 条件4（位置整合性）: 辺 \(u \to v\) について \(P_v = Q_u\)。
• 条件5（左右順序）: 両ラベルの子が存在する場合、ラベル0側の右端がラベル1側の左端より小さい。

各条件はグラフの辺やノードを1回ずつ走査すれば \(O(N + M)\) で検証できるため、特別なアルゴリズムは不要です。ただし、条件の見落としや順序の間違いに注意が必要です。

アルゴリズム

1. 入力を読み込み、各ノードの入次数・各ノードからの出辺（ラベル別）を記録する。
2. 条件2を検証: 各ノードについてラベル0、1それぞれの出辺本数が2本以上なら NO。
3. 条件1を検証:
   • ノード1の入次数が0でなければ NO。
   • ノード \(2, \dots, N\) の入次数がちょうど1でなければ NO。
   • 辺数 \(M\) が \(N-1\) でなければ NO。
   • BFS/DFS でノード1から全ノードに到達可能か確認。到達できなければ NO。
4. 条件3を検証: 各辺 \(u \to v\) について \(L_u < L_v\) かつ \(R_v < R_u\) を確認。
5. 条件4を検証: 各辺 \(u \to v\) について \(P_v = Q_u\) を確認。
6. 条件5を検証: 両ラベルの子 \(x, y\) を持つノードについて \(R_x < L_y\) を確認。
7. すべて通過したら YES を出力。

計算量

• 時間計算量: \(O(N + M)\)（各条件の検証がノード数・辺数に対して線形）
• 空間計算量: \(O(N + M)\)（グラフの隣接情報や各種配列の保持）

実装のポイント

• 条件2を先に検証する: 条件2が満たされることを確認した後なら、各ノードのラベル0・1の子を out[u][0], out[u][1] に安全に1つだけ格納できる。これにより以降の条件検証が簡潔になる。

• 辺数の確認: 入次数条件だけでは木であることは保証されない（例えば自己ループのない閉路＋孤立ノードの場合）。辺数 \(M = N - 1\) の確認と BFS による到達性確認を組み合わせる。

• 座標値のオーバーフロー: 座標が \(-10^9 \sim 10^9\) の範囲なので long long を使用して安全に処理する（この問題では比較のみなので int でも可だが念のため）。

• 同一辺の重複: 同じ \((U_j, V_j, B_j)\) が複数回出現しうるため、out_count で辺の本数を数えて条件2を正しく判定する必要がある。

  ソースコード

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, M;
    cin >> N >> M;
    
    vector<long long> L(N+1), R(N+1), P(N+1), Q(N+1);
    for (int i = 1; i <= N; i++) {
        cin >> L[i] >> R[i] >> P[i] >> Q[i];
    }
    
    vector<int> in_degree(N+1, 0);
    // out[u][b] stores the child of u via label b, -1 if none
    vector<array<int,2>> out(N+1, {-1, -1});
    vector<array<int,2>> out_count(N+1, {0, 0});
    
    for (int j = 0; j < M; j++) {
        int u, v, b;
        cin >> u >> v >> b;
        in_degree[v]++;
        out_count[u][b]++;
        out[u][b] = v;
    }
    
    // Condition 2: at most 1 outgoing edge per label per node
    for (int i = 1; i <= N; i++) {
        if (out_count[i][0] > 1 || out_count[i][1] > 1) {
            cout << "NO" << endl;
            return 0;
        }
    }
    
    // Condition 1: Node 1 has no incoming edges
    if (in_degree[1] != 0) {
        cout << "NO" << endl;
        return 0;
    }
    
    // Condition 1: Nodes 2..N each have exactly 1 incoming edge
    for (int i = 2; i <= N; i++) {
        if (in_degree[i] != 1) {
            cout << "NO" << endl;
            return 0;
        }
    }
    
    // Condition 1: M must be N-1 for a tree
    if (M != N - 1) {
        cout << "NO" << endl;
        return 0;
    }
    
    // Condition 1: All nodes reachable from node 1
    vector<bool> visited(N+1, false);
    queue<int> q;
    q.push(1);
    visited[1] = true;
    int cnt = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int b = 0; b < 2; b++) {
            if (out[u][b] != -1) {
                int v = out[u][b];
                if (!visited[v]) {
                    visited[v] = true;
                    cnt++;
                    q.push(v);
                }
            }
        }
    }
    if (cnt != N) {
        cout << "NO" << endl;
        return 0;
    }
    
    // Condition 3: For each edge u→v, L_u < L_v and R_v < R_u
    for (int u = 1; u <= N; u++) {
        for (int b = 0; b < 2; b++) {
            if (out[u][b] != -1) {
                int v = out[u][b];
                if (!(L[u] < L[v] && R[v] < R[u])) {
                    cout << "NO" << endl;
                    return 0;
                }
            }
        }
    }
    
    // Condition 4: For each edge u→v, P_v = Q_u
    for (int u = 1; u <= N; u++) {
        for (int b = 0; b < 2; b++) {
            if (out[u][b] != -1) {
                int v = out[u][b];
                if (P[v] != Q[u]) {
                    cout << "NO" << endl;
                    return 0;
                }
            }
        }
    }
    
    // Condition 5: If node u has both label-0 (to x) and label-1 (to y), then R_x < L_y
    for (int u = 1; u <= N; u++) {
        if (out[u][0] != -1 && out[u][1] != -1) {
            int x = out[u][0];
            int y = out[u][1];
            if (!(R[x] < L[y])) {
                cout << "NO" << endl;
                return 0;
            }
        }
    }
    
    cout << "YES" << endl;
    return 0;
}

この解説は claude4.6opus-thinking によって生成されました。