概要

与えられた有向グラフが、問題文の 5 条件をすべて満たす「正しい二分決定木」かを判定する問題です。
各条件は辺を読むとき・全体を1回走査するときにチェックできるため、全体を線形時間で判定できます。

考察

この問題のポイントは、「木らしさ」と「ラベル付き二分分岐らしさ」と「各ノード情報の整合性」を同時に満たすかを漏れなく確認することです。

1. 条件を分解して見る

問題文の条件は次のように分けて処理できます。

• 辺ごとに判定できる条件

  • 条件2: 同じノードから同じラベルの辺は高々1本
  • 条件3: 親区間が子区間を厳密包含
  • 条件4: \(P_v = Q_u\)

• 全体を見て判定する条件

  • 条件1: 根付き木構造（入次数制約 + 根から全到達）
  • 条件5: 0枝と1枝が両方あるときの左右順序

こう分けると、入力を読みながら多くを検査でき、追加計算が軽くなります。

2. 素朴にやると何がまずいか

例えば毎回「同じラベルの辺があるか」を辺リスト全探索で確認すると \(O(M^2)\) になり得ます。
また、到達性を各ノードから毎回探索すると \(O(N(N+M))\) で制約に間に合いません。

制約は \(N+M \le 2\times10^5\) なので、各辺・各ノードを高々定数回ずつ触る \(O(N+M)\) が必要です。

3. どう解決するか

• child0[u], child1[u] を持ち、ラベルごとの子を1つだけ保存する
  → 条件2を \(O(1)\) で判定可能
• 辺入力時に indegree/outdegree と隣接リストを作る
  → 木条件チェックと BFS 到達性チェックに使える
• 最後に
  • indeg[1] == 0
  • indeg[i] == 1 (i>=2)
  • 根1から BFS して訪問数が \(N\) を確認
    → 条件1を確実に検証
• child0[u], child1[u] が両方あるときだけ \(R[child0[u]] < L[child1[u]]\) を確認
  → 条件5を検証

アルゴリズム

1. 入力で各ノードの \(L_i,R_i,P_i,Q_i\) を受け取る。
2. 配列を用意:
   • indeg, outdeg
   • child0, child1（初期値 -1）
   • 隣接リスト g
   • 判定フラグ ok = true
3. 各辺 \((u,v,b)\) を読むたびに:
   • b==0 なら child0[u]、b==1 なら child1[u] を使って重複ラベル辺を検出（条件2）
   • indeg[v]++, outdeg[u]++, g[u].push_back(v)
   • \(L_u < L_v\) かつ \(R_v < R_u\) を確認（条件3）
   • \(P_v = Q_u\) を確認（条件4）
4. 全辺入力後:
   • indeg[1] == 0 を確認
   • i=2..N で indeg[i] == 1 を確認（条件1の一部）
5. ノード1から BFS して到達数 cnt を数える。cnt==N であることを確認（条件1の到達性）。
6. 全ノード u について、child0[u] と child1[u] が両方あるなら
   • \(R_{child0[u]} < L_{child1[u]}\) を確認（条件5）
7. 1つでも違反があれば NO、すべて満たせば YES。

計算量

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

実装のポイント

• ok は途中で false になっても最後まで入力を読み切る（競技実装として安全）。

• 座標や位置は最大 \(10^9\) なので long long で保持。

• 条件1の「木」は、
  

  • 根の入次数0
    
  • 他ノード入次数1
    
  • 根から全到達
    の3点で十分判定できる（このとき辺数は自動的に \(N-1\) 相当になり、閉路も排除される）。

• 多重辺が来る可能性があるため、ラベルごと1本制約は child0/child1 で必ず検出する。

  ソースコード

#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), outdeg(N + 1, 0);
    vector<int> child0(N + 1, -1), child1(N + 1, -1);
    vector<vector<int>> g(N + 1);

    bool ok = true;

    for (int j = 0; j < M; j++) {
        int u, v, b;
        cin >> u >> v >> b;

        // condition 2: at most one outgoing edge per label
        if (b == 0) {
            if (child0[u] != -1) ok = false;
            else child0[u] = v;
        } else {
            if (child1[u] != -1) ok = false;
            else child1[u] = v;
        }

        indeg[v]++;
        outdeg[u]++;
        g[u].push_back(v);

        // condition 3
        if (!(L[u] < L[v] && R[v] < R[u])) ok = false;
        // condition 4
        if (P[v] != Q[u]) ok = false;
    }

    // condition 1 (in-degree constraints)
    if (indeg[1] != 0) ok = false;
    for (int i = 2; i <= N; i++) {
        if (indeg[i] != 1) ok = false;
    }

    // condition 1 (reachability from root 1)
    vector<char> vis(N + 1, 0);
    queue<int> q;
    vis[1] = 1;
    q.push(1);
    int cnt = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        cnt++;
        for (int v : g[u]) {
            if (!vis[v]) {
                vis[v] = 1;
                q.push(v);
            }
        }
    }
    if (cnt != N) ok = false;

    // condition 5
    for (int u = 1; u <= N; u++) {
        if (child0[u] != -1 && child1[u] != -1) {
            int x = child0[u], y = child1[u];
            if (!(R[x] < L[y])) ok = false;
        }
    }

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

---

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