Overview

This problem asks you to determine whether a given directed graph is a “valid binary decision tree” that satisfies all 5 conditions in the problem statement.
Each condition can be checked either when reading edges or during a single traversal of the entire graph, so the overall judgment can be made in linear time.

Analysis

The key point of this problem is to thoroughly verify that “tree-likeness,” “labeled binary branching,” and “consistency of node information” are all satisfied simultaneously.

1. Breaking Down the Conditions

The conditions in the problem statement can be processed as follows:

• Conditions that can be checked per edge

  • Condition 2: At most one edge with the same label from the same node
  • Condition 3: The parent’s interval strictly contains the child’s interval
  • Condition 4: \(P_v = Q_u\)

• Conditions that require examining the whole graph

  • Condition 1: Rooted tree structure (in-degree constraints + reachability from the root)
  • Condition 5: Left-right ordering when both 0-edges and 1-edges exist

With this decomposition, much can be verified while reading the input, and the additional computation becomes lightweight.

2. What Goes Wrong with a Naive Approach

For example, checking “is there an edge with the same label” by scanning the entire edge list each time could be \(O(M^2)\).
Also, checking reachability from each node with a search each time would be \(O(N(N+M))\), which won’t fit within the constraints.

The constraints are \(N+M \le 2\times10^5\), so we need \(O(N+M)\) where each edge and node is touched at most a constant number of times.

3. How to Solve It

• Maintain child0[u], child1[u] and store only one child per label
  → Condition 2 can be checked in \(O(1)\)
• Build indegree/outdegree and adjacency lists while reading edges
  → Can be used for tree condition checking and BFS reachability checking
• Finally verify:
  • indeg[1] == 0
  • indeg[i] == 1 (i>=2)
  • BFS from root 1 visits exactly \(N\) nodes → Reliably verifies Condition 1
• Only when both child0[u] and child1[u] exist, verify \(R[child0[u]] < L[child1[u]]\)
  → Verifies Condition 5

Algorithm

1. Read \(L_i, R_i, P_i, Q_i\) for each node from input.
2. Prepare arrays:
   • indeg, outdeg
   • child0, child1 (initialized to -1)
   • Adjacency list g
   • Judgment flag ok = true
3. For each edge \((u, v, b)\) read:
   • If b==0 use child0[u], if b==1 use child1[u] to detect duplicate labeled edges (Condition 2)
   • indeg[v]++, outdeg[u]++, g[u].push_back(v)
   • Verify \(L_u < L_v\) and \(R_v < R_u\) (Condition 3)
   • Verify \(P_v = Q_u\) (Condition 4)
4. After all edges are read:
   • Verify indeg[1] == 0
   • Verify indeg[i] == 1 for i=2..N (part of Condition 1)
5. BFS from node 1 and count reachable nodes cnt. Verify cnt==N (reachability part of Condition 1).
6. For every node u, if both child0[u] and child1[u] exist:
   • Verify \(R_{child0[u]} < L_{child1[u]}\) (Condition 5)
7. If any violation exists, output NO; if all conditions are satisfied, output YES.

Complexity

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

Implementation Notes

• Even if ok becomes false midway, continue reading all input to the end (safe practice for competitive programming).

• Coordinates and positions can be up to \(10^9\), so store them as long long.

• For Condition 1’s “tree” check:

  • Root has in-degree 0
  • All other nodes have in-degree 1
  • All nodes are reachable from the root These 3 points are sufficient for verification (in this case, the number of edges automatically equals \(N-1\), and cycles are also excluded).

• Since multiple edges may appear, the constraint of at most one edge per label must be detected using child0/child1.

  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), 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;
}

---

This editorial was generated by gpt-5.3-codex.