Overview

This is a problem where you determine whether a graph consisting of \(N\) nodes and \(M\) directed edges is a “valid binary decision tree” satisfying all five conditions. It is sufficient to straightforwardly verify each condition one by one.

Analysis

This problem is essentially a verification problem asking “can you accurately implement the given conditions?” Each of the five conditions can be organized as follows:

• Condition 1 (Rooted tree): The in-degree of node 1 is 0, the in-degree of all other nodes is exactly 1, the number of edges is \(N-1\), and all nodes are reachable from node 1.
• Condition 2 (Out-degree constraint): From each node, there is at most one edge with label 0 and at most one edge with label 1.
• Condition 3 (Interval containment): For an edge \(u \to v\), \(L_u < L_v\) and \(R_v < R_u\).
• Condition 4 (Position consistency): For an edge \(u \to v\), \(P_v = Q_u\).
• Condition 5 (Left-right ordering): When children of both labels exist, the right endpoint of the label-0 side is less than the left endpoint of the label-1 side.

Each condition can be verified in \(O(N + M)\) by scanning the edges or nodes once, so no special algorithm is needed. However, care must be taken not to overlook conditions or make ordering mistakes.

Algorithm

1. Read input and record the in-degree of each node and the outgoing edges (by label) from each node.
2. Verify Condition 2: For each node, if the number of outgoing edges with label 0 or label 1 is 2 or more, output NO.
3. Verify Condition 1:
   • If the in-degree of node 1 is not 0, output NO.
   • If the in-degree of nodes \(2, \dots, N\) is not exactly 1, output NO.
   • If the number of edges \(M\) is not \(N-1\), output NO.
   • Use BFS/DFS to check if all nodes are reachable from node 1. If not, output NO.
4. Verify Condition 3: For each edge \(u \to v\), check that \(L_u < L_v\) and \(R_v < R_u\).
5. Verify Condition 4: For each edge \(u \to v\), check that \(P_v = Q_u\).
6. Verify Condition 5: For each node that has children \(x, y\) of both labels, check that \(R_x < L_y\).
7. If all conditions pass, output YES.

Complexity

• Time complexity: \(O(N + M)\) (verification of each condition is linear with respect to the number of nodes and edges)
• Space complexity: \(O(N + M)\) (storing adjacency information and various arrays for the graph)

Implementation Notes

• Verify Condition 2 first: After confirming that Condition 2 is satisfied, you can safely store exactly one child for each label in out[u][0] and out[u][1] for each node. This makes the subsequent condition verification more concise.

• Checking the number of edges: The in-degree condition alone does not guarantee a tree (for example, a cycle without self-loops plus isolated nodes). Combine the check that \(M = N - 1\) with reachability verification via BFS.

• Overflow of coordinate values: Since coordinates range from \(-10^9\) to \(10^9\), use long long to handle them safely (in this problem only comparisons are performed so int would also work, but it’s safer to use long long).

• Duplicate edges: The same \((U_j, V_j, B_j)\) can appear multiple times, so you need to count the number of edges using out_count to correctly determine Condition 2.

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    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> in_degree(N+1, 0);
    // out[u][b] stores the child of u via label b, -1 if none
    vector<array<int,2>> out(N+1, {-1, -1});
    vector<array<int,2>> out_count(N+1, {0, 0});
    
    for (int j = 0; j < M; j++) {
        int u, v, b;
        cin >> u >> v >> b;
        in_degree[v]++;
        out_count[u][b]++;
        out[u][b] = v;
    }
    
    // Condition 2: at most 1 outgoing edge per label per node
    for (int i = 1; i <= N; i++) {
        if (out_count[i][0] > 1 || out_count[i][1] > 1) {
            cout << "NO" << endl;
            return 0;
        }
    }
    
    // Condition 1: Node 1 has no incoming edges
    if (in_degree[1] != 0) {
        cout << "NO" << endl;
        return 0;
    }
    
    // Condition 1: Nodes 2..N each have exactly 1 incoming edge
    for (int i = 2; i <= N; i++) {
        if (in_degree[i] != 1) {
            cout << "NO" << endl;
            return 0;
        }
    }
    
    // Condition 1: M must be N-1 for a tree
    if (M != N - 1) {
        cout << "NO" << endl;
        return 0;
    }
    
    // Condition 1: All nodes reachable from node 1
    vector<bool> visited(N+1, false);
    queue<int> q;
    q.push(1);
    visited[1] = true;
    int cnt = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int b = 0; b < 2; b++) {
            if (out[u][b] != -1) {
                int v = out[u][b];
                if (!visited[v]) {
                    visited[v] = true;
                    cnt++;
                    q.push(v);
                }
            }
        }
    }
    if (cnt != N) {
        cout << "NO" << endl;
        return 0;
    }
    
    // Condition 3: For each edge u→v, L_u < L_v and R_v < R_u
    for (int u = 1; u <= N; u++) {
        for (int b = 0; b < 2; b++) {
            if (out[u][b] != -1) {
                int v = out[u][b];
                if (!(L[u] < L[v] && R[v] < R[u])) {
                    cout << "NO" << endl;
                    return 0;
                }
            }
        }
    }
    
    // Condition 4: For each edge u→v, P_v = Q_u
    for (int u = 1; u <= N; u++) {
        for (int b = 0; b < 2; b++) {
            if (out[u][b] != -1) {
                int v = out[u][b];
                if (P[v] != Q[u]) {
                    cout << "NO" << endl;
                    return 0;
                }
            }
        }
    }
    
    // Condition 5: If node u has both label-0 (to x) and label-1 (to y), then R_x < L_y
    for (int u = 1; u <= N; u++) {
        if (out[u][0] != -1 && out[u][1] != -1) {
            int x = out[u][0];
            int y = out[u][1];
            if (!(R[x] < L[y])) {
                cout << "NO" << endl;
                return 0;
            }
        }
    }
    
    cout << "YES" << endl;
    return 0;
}

This editorial was generated by claude4.6opus-thinking.