Overview

Determine whether the given directed graph satisfies all conditions of a binary decision tree rooted at node \(1\).

While checking local conditions for each edge, we also verify whether the graph “forms a rooted tree,” “the left-right ordering of children is correct,” and “all nodes are reachable.”

Analysis

The conditions to verify in this problem can be broadly divided into the following \(5\):

1. It is a rooted tree with node \(1\) as the root
2. Each node has at most \(1\) outgoing edge with label \(0\) and at most \(1\) outgoing edge with label \(1\)
3. The interval of a child is strictly contained within the interval of its parent
4. For edge \(u \to v\), \(P_v = Q_u\) holds
5. The child with label \(0\) is to the left of the child with label \(1\)

The key point is that most conditions can be verified by looking at only “each edge” or “each node.”

For example, for edge \(u \to v\), we can immediately check:

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

Also, the condition that each node has at most one outgoing edge with label \(0\) and at most one with label \(1\) can be verified by recording the child for each label at each node.

On the other hand, verifying that the graph forms a rooted tree requires some care.

For it to be a rooted tree:

• Node \(1\) must have in-degree \(0\)
• All other nodes must have in-degree exactly \(1\)
• All nodes must be reachable from node \(1\)

The in-degree condition alone cannot detect, for example, a closed structure in a part unreachable from node \(1\). Therefore, we perform DFS or BFS from node \(1\) at the end to confirm that all nodes are reachable.

Naively checking all pairs of nodes or searching for edges for each node would result in \(O(NM)\), which is too slow for \(N, M \leq 2 \times 10^5\).

Instead, we scan the edges once to record necessary information in arrays, then perform a single DFS, processing everything in \(O(N+M)\).

Algorithm

We manage the following information using arrays:

• indeg[v]: in-degree of node \(v\)
• child0[u]: destination of the edge with label \(0\) from node \(u\)
• child1[u]: destination of the edge with label \(1\) from node \(u\)

We set them to \(0\) if they don’t exist.

First, while reading all edges \(u \to v\), we do the following:

1. Increment indeg[v] by \(1\)
2. Check child0[u] or child1[u] depending on label \(b\)
   • If a child is already recorded, there are multiple outgoing edges with the same label, which is invalid
   • Otherwise, record the destination
3. Check the per-edge conditions
   • \(L_u < L_v\)
   • \(R_v < R_u\)
   • \(P_v = Q_u\)

Next, check the in-degree conditions for a rooted tree:

• indeg[1] == 0
• For \(i = 2, 3, \dots, N\): indeg[i] == 1

Then, check the left-right ordering.

For each node \(u\), if both the child \(a\) with label \(0\) and the child \(b\) with label \(1\) exist, the following must hold:

\[ R_a < L_b \]

Finally, perform DFS from node \(1\).

Follow child0 and child1 to count the number of reachable nodes. If the count equals \(N\), all nodes are reachable.

If all conditions are satisfied, output YES; otherwise, output NO.

Complexity

• Time complexity: \(O(N+M)\)
• Space complexity: \(O(N)\)

Implementation Notes

Note that even if the same tuple \((U_j, V_j, B_j)\) appears multiple times, each occurrence is treated as a separate edge.

For example, even if the same edge is given twice, it means there are \(2\) outgoing edges with label \(B_j\), which violates the out-degree constraint.

Therefore, if child0[u] or child1[u] already has a value stored and another edge with the same label appears, we judge it as invalid.

Also, when determining whether the graph is a rooted tree, we must always verify reachability from node \(1\), not just check in-degrees. This is because even if the in-degree conditions are satisfied, there may exist components unreachable from node \(1\).

Source Code

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()

---

This editorial was generated by gpt-5.5-high.