概要

与えられた有向グラフが、ノード \(1\) を根とする「正しい二分決定木」の条件をすべて満たすか判定します。

各辺・各ノードについて必要な条件を一度ずつ確認し、最後にノード \(1\) から全ノードへ到達できるかを調べます。

考察

判定すべき条件は大きく分けて次の通りです。

1. ノード \(1\) を根とする根付き木である
2. 各ノードからラベル \(0\), \(1\) の辺がそれぞれ高々 \(1\) 本である
3. 各辺について、子の区間が親の区間に厳密に含まれる
4. 各辺について、\(P_v = Q_u\) が成り立つ
5. ラベル \(0\) の子がラベル \(1\) の子より左にある

これらはすべて、辺やノードを順に見れば確認できます。

特に根付き木の条件については、次のように分解できます。

• ノード \(1\) の入次数が \(0\)
• ノード \(2,3,\dots,N\) の入次数がすべて \(1\)
• ノード \(1\) からすべてのノードに到達できる

この \(3\) つを満たせば、ノード \(1\) を根とする根付き木構造になっています。

また、同じ辺が複数回与えられる場合もありますが、問題文ではそれぞれ別の辺として扱います。
そのため、例えば同じ \((U,V,B)\) が \(2\) 回出てきた場合、ラベル \(B\) の出辺が \(2\) 本あることになり、出次数制約に違反します。

素朴に「すべてのノードの親子関係を何度も探索する」ような方法を取ると、最悪で \(O(NM)\) になり、\(N+M \leq 2 \times 10^5\) では間に合いません。

そこで、入力を読みながら必要な情報を記録し、各条件を \(O(N+M)\) で一度ずつ確認します。

アルゴリズム

まず、各ノードについて以下を管理します。

• indeg[i]：ノード \(i\) の入次数
• outcnt[i][0]：ノード \(i\) から出るラベル \(0\) の辺の本数
• outcnt[i][1]：ノード \(i\) から出るラベル \(1\) の辺の本数
• child[i][0]：ノード \(i\) から出るラベル \(0\) の辺の行き先
• child[i][1]：ノード \(i\) から出るラベル \(1\) の辺の行き先
• adj[i]：到達可能性判定用の隣接リスト

辺 \(U \to V\)、ラベル \(B\) を読み込むたびに、次を行います。

1. 隣接リストに追加する

   • adj[U].push_back(V)

2. 入次数を増やす

   • indeg[V]++

3. ラベルごとの出次数を数える

   • outcnt[U][B]++
   • もし \(2\) 本以上になったら不正

4. 最初のラベル \(B\) の子を記録する

   • child[U][B] = V

5. 区間包含条件を確認する

   • \(L_U < L_V\) かつ \(R_V < R_U\)

6. 位置の整合性を確認する

   • \(P_V = Q_U\)

次に、根付き木の入次数条件を確認します。

• indeg[1] == 0
• \(i = 2,3,\dots,N\) について indeg[i] == 1

その後、左右の順序条件を確認します。

あるノード \(u\) について、ラベル \(0\) の子とラベル \(1\) の子が両方存在するなら、それぞれを \(x\), \(y\) として、

\[ R_x < L_y \]

が成り立つ必要があります。

最後に、ここまでで不正でなければ、ノード \(1\) から DFS または BFS を行い、すべてのノードに到達できるかを調べます。

訪問できたノード数が \(N\) 個なら正しい二分決定木、そうでなければ不正です。

計算量

• 時間計算量: \(O(N+M)\)
• 空間計算量: \(O(N+M)\)

各辺を読み込み時に一度処理し、各ノードも高々一度ずつ確認します。
DFS でも各ノード・各辺を高々一度ずつ見るため、全体で \(O(N+M)\) です。

実装のポイント

• 条件違反を見つけたら ok = false にします。

• ただし、入力は最後まで読む必要があります。

• ラベルごとの出次数は outcnt[u][0], outcnt[u][1] のように分けて管理します。

• 左右の順序条件では、ラベル \(0\) の子とラベル \(1\) の子が両方ある場合だけ確認します。

• 到達可能性の確認は、入次数条件などの基本的な条件を満たしている場合に行えば十分です。

• \(L_i, R_i, P_i, Q_i\) は最大で \(10^9\)、最小で \(-10^9\) なので、long long で持っておくと安全です。

  ソースコード

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    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> indeg(N + 1, 0);
    vector<array<int, 2>> child(N + 1);
    vector<array<int, 2>> outcnt(N + 1);
    vector<vector<int>> adj(N + 1);

    for (int i = 1; i <= N; i++) {
        child[i] = {0, 0};
        outcnt[i] = {0, 0};
    }

    bool ok = true;

    for (int j = 0; j < M; j++) {
        int U, V, B;
        cin >> U >> V >> B;

        adj[U].push_back(V);
        indeg[V]++;

        outcnt[U][B]++;
        if (outcnt[U][B] == 1) {
            child[U][B] = V;
        } else {
            ok = false;
        }

        if (!(L[U] < L[V] && R[V] < R[U])) ok = false;
        if (P[V] != Q[U]) ok = false;
    }

    if (indeg[1] != 0) ok = false;
    for (int i = 2; i <= N; i++) {
        if (indeg[i] != 1) ok = false;
    }

    for (int u = 1; u <= N; u++) {
        if (outcnt[u][0] >= 1 && outcnt[u][1] >= 1) {
            int x = child[u][0];
            int y = child[u][1];
            if (!(R[x] < L[y])) ok = false;
        }
    }

    if (ok) {
        vector<char> visited(N + 1, false);
        stack<int> st;
        st.push(1);
        visited[1] = true;
        int cnt = 0;

        while (!st.empty()) {
            int u = st.top();
            st.pop();
            cnt++;

            for (int v : adj[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    st.push(v);
                }
            }
        }

        if (cnt != N) ok = false;
    }

    cout << (ok ? "YES" : "NO") << '\n';
    return 0;
}

---

この解説は gpt-5.5-xhigh によって生成されました。