Overview

This problem asks you to determine whether a given directed graph with \(N\) nodes and \(M\) edges is a “valid binary decision tree” that satisfies 5 specific conditions. The conditions range from the graph’s structure (being a tree) to the consistency of intervals and values assigned to each node.

Analysis

Although it appears complex at first glance, organizing the conditions reveals that the problem can be divided into two stages: “graph structure verification” and “attribute checks between parent-child/sibling nodes.”

1. Graph Structure Verification (Conditions 1, 2):

   • For the graph to be a tree rooted at node 1, the total number of edges \(M\) must be \(N-1\).
   • Check the in-degree of each node: node 1 must have in-degree 0, and all other nodes must have in-degree 1.
   • Verify that each node has at most one outgoing edge with label 0 and at most one with label 1.
   • Finally, determine whether all nodes are reachable from the root (node 1), confirming the graph is acyclic and connected.

2. Attribute Consistency Verification (Conditions 3, 4, 5):

   • These conditions only require checking relationships between “parent and child” or “children sharing the same parent (siblings).”
   • Condition 3 (Interval containment): For parent \(u\) and child \(v\), \(L_u < L_v\) and \(R_v < R_u\).
   • Condition 4 (Position consistency): For parent \(u\) and child \(v\), \(Q_u = P_v\).
   • Condition 5 (Left-right ordering): For children \(x\) (label 0) and \(y\) (label 1) sharing the same parent \(u\), \(R_x < L_y\).

These conditions can all be checked at once by traversing the graph (using BFS or DFS) and examining each node and its adjacent nodes.

Algorithm

The determination is performed through the following steps:

1. Input and Basic Checks:

   • Store information for each node in arrays.
   • While reading edge information, record the in-degree of each node and the child number corresponding to each label (0, 1). If multiple edges with the same label exist from a node, immediately output NO.
   • If the number of edges \(M\) is not \(N-1\), or if the in-degree of node 1 is not 0, or if any other node’s in-degree is not 1, output NO.

2. Detailed Checks via Traversal:

   • Perform BFS (breadth-first search) starting from node 1.
   • For each node \(u\), check the following for each existing child \(v\) (label 0 or 1):
     • If \(v\) has already been visited (meaning it’s not a tree), output NO.
     • If the interval containment relationship (Condition 3) is not satisfied, output NO.
     • If the position consistency (Condition 4) is not satisfied, output NO.
   • If node \(u\) has both a label-0 child \(v_0\) and a label-1 child \(v_1\):
     • If the left-right ordering (Condition 5) is not satisfied, output NO.

3. Final Determination:

   • After traversal, if the total number of visited nodes equals \(N\), all conditions are satisfied and output YES. Otherwise (if there are isolated nodes or cycles), output NO.

Complexity

• Time Complexity: \(O(N + M)\)
  • Reading edge information takes \(O(M)\), and the BFS that traverses each node and edge once takes \(O(N + M)\). This is sufficiently fast for the constraints \(N, M \le 2 \times 10^5\).
• Space Complexity: \(O(N)\)
  • Arrays storing node information, in-degrees, and child information use \(O(N)\) memory.

Implementation Notes

• 1-based indexing: Since node numbers start from 1, allocating arrays with size \(N+1\) makes implementation smoother.

• Early termination: By immediately outputting NO and terminating as soon as a condition is violated, unnecessary computation is avoided.

• Fast I/O: Following standard competitive programming practice, use ios_base::sync_with_stdio(false); cin.tie(NULL); to speed up input/output.

  Source Code

#include <iostream>
#include <vector>

using namespace std;

/**
 * Problem: Verifying a Binary Decision Tree
 * 
 * We need to check if a given directed graph with N nodes and M edges
 * represents a "correct binary decision tree" based on five specific conditions:
 * 1. Rooted tree structure starting from node 1.
 * 2. Each node has at most one outgoing edge for label 0 and at most one for label 1.
 * 3. Child's interval [L_v, R_v] must be strictly contained in parent's [L_u, R_u].
 * 4. Arrival position P_v of a child must match departure position Q_u of its parent.
 * 5. If a node has both label-0 and label-1 children, the label-0 child's interval 
 *    must be strictly to the left of the label-1 child's interval (R_child0 < L_child1).
 */

struct Node {
    long long l, r, p, q;
};

int main() {
    // Fast I/O setup
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    // Read node information: interval [L_i, R_i], arrival P_i, departure Q_i
    vector<Node> nodes(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> nodes[i].l >> nodes[i].r >> nodes[i].p >> nodes[i].q;
    }

    vector<int> in_degree(n + 1, 0);
    vector<int> child0(n + 1, 0);
    vector<int> child1(n + 1, 0);
    bool possible = true;

    // Process edges and check Condition 2 (out-degree constraints)
    for (int i = 0; i < m; ++i) {
        int u, v, b;
        cin >> u >> v >> b;
        // Basic range checks for safety
        if (u < 1 || u > n || v < 1 || v > n) {
            possible = false;
            continue;
        }
        
        in_degree[v]++;
        
        // Label-based child assignment
        if (b == 0) {
            if (child0[u] != 0) possible = false; // Violation: more than one label-0 edge
            child0[u] = v;
        } else if (b == 1) {
            if (child1[u] != 0) possible = false; // Violation: more than one label-1 edge
            child1[u] = v;
        } else {
            possible = false; // Label must be 0 or 1
        }
    }

    // Condition 1: Check basic tree structure requirements
    // For N nodes to form a tree, we must have M = N-1 edges.
    if (m != n - 1) possible = false;
    
    if (possible) {
        // Node 1 must have no incoming edges (root)
        if (in_degree[1] != 0) possible = false;
        // Every other node must have exactly one incoming edge
        for (int i = 2; i <= n; ++i) {
            if (in_degree[i] != 1) {
                possible = false;
                break;
            }
        }
    }

    // Early exit if basic structural conditions fail
    if (!possible) {
        cout << "NO" << endl;
        return 0;
    }

    // Use BFS to verify reachability and check conditions 3, 4, and 5
    vector<int> q;
    q.reserve(n);
    q.push_back(1);
    vector<bool> visited(n + 1, false);
    visited[1] = true;
    int head = 0;

    while (head < q.size()) {
        int u = q[head++];
        int v0 = child0[u];
        int v1 = child1[u];

        // Process label-0 child
        if (v0 != 0) {
            // Check reachability/cycle (though redundant given structural checks)
            if (visited[v0]) {
                cout << "NO" << endl;
                return 0;
            }
            // Condition 3: Strict containment (L_u < L_v and R_v < R_u)
            if (!(nodes[u].l < nodes[v0].l && nodes[v0].r < nodes[u].r)) {
                cout << "NO" << endl;
                return 0;
            }
            // Condition 4: Position consistency (P_v = Q_u)
            if (nodes[v0].p != nodes[u].q) {
                cout << "NO" << endl;
                return 0;
            }
            visited[v0] = true;
            q.push_back(v0);
        }

        // Process label-1 child
        if (v1 != 0) {
            if (visited[v1]) {
                cout << "NO" << endl;
                return 0;
            }
            // Condition 3: Strict containment
            if (!(nodes[u].l < nodes[v1].l && nodes[v1].r < nodes[u].r)) {
                cout << "NO" << endl;
                return 0;
            }
            // Condition 4: Position consistency
            if (nodes[v1].p != nodes[u].q) {
                cout << "NO" << endl;
                return 0;
            }
            visited[v1] = true;
            q.push_back(v1);
        }

        // Condition 5: Left-right order of children
        if (v0 != 0 && v1 != 0) {
            if (!(nodes[v0].r < nodes[v1].l)) {
                cout << "NO" << endl;
                return 0;
            }
        }
    }

    // Final reachability check: Did we visit all N nodes?
    if (q.size() == n) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }

    return 0;
}

This editorial was generated by gemini-3-flash-thinking.