Overview

We determine whether the given directed graph satisfies all conditions of a “valid binary decision tree” rooted at node \(1\).

We check the necessary conditions for each edge and each node once, and finally verify whether all nodes are reachable from node \(1\).

Analysis

The conditions to verify can be broadly categorized as follows:

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. For each edge, the child’s interval is strictly contained within the parent’s interval
4. For each edge, \(P_v = Q_u\) holds
5. The child with label \(0\) is to the left of the child with label \(1\)

All of these can be verified by examining edges and nodes sequentially.

In particular, the rooted tree condition can be decomposed as follows:

• The in-degree of node \(1\) is \(0\)
• The in-degree of nodes \(2, 3, \dots, N\) is exactly \(1\)
• All nodes are reachable from node \(1\)

If these \(3\) conditions are satisfied, it forms a rooted tree structure with node \(1\) as the root.

Also, the same edge may be given multiple times, but the problem treats each as a separate edge. Therefore, for example, if the same \((U, V, B)\) appears \(2\) times, there are \(2\) outgoing edges with label \(B\), which violates the out-degree constraint.

A naive approach that “repeatedly searches parent-child relationships for all nodes” would be \(O(NM)\) in the worst case, which is too slow for \(N + M \leq 2 \times 10^5\).

Instead, we record necessary information while reading the input and verify each condition once in \(O(N+M)\).

Algorithm

First, we maintain the following for each node:

• indeg[i]: in-degree of node \(i\)
• outcnt[i][0]: number of outgoing edges with label \(0\) from node \(i\)
• outcnt[i][1]: number of outgoing edges with label \(1\) from node \(i\)
• child[i][0]: destination of the label \(0\) edge from node \(i\)
• child[i][1]: destination of the label \(1\) edge from node \(i\)
• adj[i]: adjacency list for reachability check

Each time we read an edge \(U \to V\) with label \(B\), we do the following:

1. Add to the adjacency list

   • adj[U].push_back(V)

2. Increment the in-degree

   • indeg[V]++

3. Count the out-degree per label

   • outcnt[U][B]++
   • If it becomes \(2\) or more, it is invalid

4. Record the first child with label \(B\)

   • child[U][B] = V

5. Check the interval containment condition

   • \(L_U < L_V\) and \(R_V < R_U\)

6. Check the position consistency condition

   • \(P_V = Q_U\)

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

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

Then, we check the left-right ordering condition.

For a node \(u\), if both a child with label \(0\) and a child with label \(1\) exist, let them be \(x\) and \(y\) respectively. Then,

\[ R_x < L_y \]

must hold.

Finally, if no violation has been found so far, we perform DFS or BFS from node \(1\) to check whether all nodes are reachable.

If the number of visited nodes is \(N\), it is a valid binary decision tree; otherwise, it is invalid.

Complexity

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

Each edge is processed once when read, and each node is checked at most once. Since DFS also visits each node and each edge at most once, the overall complexity is \(O(N+M)\).

Implementation Notes

• When a condition violation is found, set ok = false.

• However, the input must be read completely.

• The out-degree per label is managed separately as outcnt[u][0], outcnt[u][1].

• The left-right ordering condition is only checked when both a child with label \(0\) and a child with label \(1\) exist.

• The reachability check only needs to be performed if basic conditions such as the in-degree conditions are satisfied.

• \(L_i, R_i, P_i, Q_i\) can be as large as \(10^9\) and as small as \(-10^9\), so it is safe to store them as long long.

  Source Code

#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;
}

---

This editorial was generated by gpt-5.5-xhigh.