概要

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

各辺について局所的な条件を確認しつつ、最後に「根付き木になっているか」「左右の子の順序が正しいか」「全ノードに到達できるか」を調べます。

考察

この問題で確認すべき条件は、大きく分けると以下の \(5\) つです。

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

重要なのは、ほとんどの条件は「各辺」または「各ノード」だけを見れば確認できるという点です。

例えば、辺 \(u \to v\) については、

• \(L_u < L_v\)
• \(R_v < R_u\)
• \(P_v = Q_u\)

をその場で確認できます。

また、各ノードからラベル \(0\) の辺が高々 \(1\) 本、ラベル \(1\) の辺が高々 \(1\) 本という条件も、ノードごとにラベルごとの子を記録しておけば確認できます。

一方で、根付き木であることは少し注意が必要です。

根付き木であるためには、

• ノード \(1\) の入次数が \(0\)
• それ以外のノードの入次数がちょうど \(1\)
• ノード \(1\) からすべてのノードに到達できる

必要があります。

入次数の条件だけでは、例えばノード \(1\) から到達できない場所に閉じた構造がある場合を検出できません。そのため、最後にノード \(1\) から DFS または BFS を行い、全ノードに到達できるか確認します。

素朴にすべてのノード対を調べたり、各ノードについて毎回辺を探したりすると \(O(NM)\) になり、\(N, M \leq 2 \times 10^5\) では間に合いません。

そこで、辺を一度だけ走査して必要な情報を配列に記録し、最後に DFS を \(1\) 回行うことで、全体を \(O(N+M)\) で処理します。

アルゴリズム

以下の情報を配列で管理します。

• indeg[v]: ノード \(v\) の入次数
• child0[u]: ノード \(u\) からラベル \(0\) で出る辺の行き先
• child1[u]: ノード \(u\) からラベル \(1\) で出る辺の行き先

存在しない場合は \(0\) としておきます。

まず、すべての辺 \(u \to v\) を読みながら次を行います。

1. indeg[v] を \(1\) 増やす
2. ラベル \(b\) に応じて child0[u] または child1[u] を確認する
   • すでに子が記録されていれば、同じラベルの出る辺が複数あるので不正
   • そうでなければ行き先を記録する
3. 辺ごとの条件を確認する
   • \(L_u < L_v\)
   • \(R_v < R_u\)
   • \(P_v = Q_u\)

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

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

続いて、左右の順序を確認します。

各ノード \(u\) について、ラベル \(0\) の子 \(a\) とラベル \(1\) の子 \(b\) が両方存在するなら、

\[ R_a < L_b \]

を満たす必要があります。

最後に、ノード \(1\) から DFS を行います。

child0 と child1 をたどって到達できるノード数を数え、到達数が \(N\) ならすべてのノードに到達可能です。

すべての条件を満たせば YES、そうでなければ NO を出力します。

計算量

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

実装のポイント

同じ \((U_j, V_j, B_j)\) の組が複数回現れる場合も、それぞれ別の辺として扱う点に注意が必要です。

例えば同じ辺が \(2\) 回与えられた場合でも、ラベル \(B_j\) の出る辺が \(2\) 本あることになるため、出次数の制約に違反します。

そのため、child0[u] や child1[u] にすでに値が入っている状態で、同じラベルの辺がさらに出てきたら不正と判定します。

また、根付き木の判定では入次数だけでなく、必ずノード \(1\) からの到達確認も行う必要があります。入次数条件を満たしていても、ノード \(1\) から到達できない成分が存在する可能性があるためです。

ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline

    N, M = map(int, input().split())

    L = [0] * (N + 1)
    R = [0] * (N + 1)
    P = [0] * (N + 1)
    Q = [0] * (N + 1)

    for i in range(1, N + 1):
        L[i], R[i], P[i], Q[i] = map(int, input().split())

    indeg = [0] * (N + 1)
    child0 = [0] * (N + 1)
    child1 = [0] * (N + 1)

    ok = True

    for _ in range(M):
        u, v, b = map(int, input().split())

        indeg[v] += 1

        if b == 0:
            if child0[u] != 0:
                ok = False
            else:
                child0[u] = v
        else:
            if child1[u] != 0:
                ok = False
            else:
                child1[u] = v

        if not (L[u] < L[v] and R[v] < R[u] and P[v] == Q[u]):
            ok = False

    if ok:
        if indeg[1] != 0:
            ok = False
        else:
            for i in range(2, N + 1):
                if indeg[i] != 1:
                    ok = False
                    break

    if ok:
        for u in range(1, N + 1):
            a = child0[u]
            b = child1[u]
            if a and b and not (R[a] < L[b]):
                ok = False
                break

    if ok:
        seen = [False] * (N + 1)
        stack = [1]
        seen[1] = True
        cnt = 0

        while stack:
            u = stack.pop()
            cnt += 1

            a = child0[u]
            if a and not seen[a]:
                seen[a] = True
                stack.append(a)

            b = child1[u]
            if b and not seen[b]:
                seen[b] = True
                stack.append(b)

        if cnt != N:
            ok = False

    print("YES" if ok else "NO")


if __name__ == "__main__":
    main()

---

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