Overview

This is a problem where you select some computers from \(N\) available ones and determine whether you can construct a “tree structure” network using all of them. Each computer \(i\) has \(A_i\) ports, and every selected computer must use all of its ports for connections.

Analysis

The key to this problem is organizing the conditions based on the number of selected computers \(k\).

1. Selecting only one computer (\(k=1\))

When selecting only one computer, the number of cables is 0. To satisfy the condition of using all ports, that computer’s port count \(A_i\) must be \(0\). Therefore, if at least one computer with \(A_i = 0\) exists, the answer is Yes.

2. Selecting two or more computers (\(k \geq 2\))

When selecting \(k\) computers to form a tree structure, the following conditions must be satisfied:

• Sum of degrees: By the properties of a tree, a tree with \(k\) nodes has \(k-1\) edges. Since each edge consumes 2 ports, the sum of port counts of the selected computers must be \(2(k-1)\).
• Degree of each node: Since every computer in the tree must be connected to at least one edge, all selected computers must have port counts \(A_i \geq 1\).
• Existence of leaves: A tree with 2 or more nodes must have at least 2 “leaves” (nodes with degree 1).

Key Insight

When determining “whether a tree with 2 or more nodes can be constructed,” it is actually sufficient to check only “whether there are at least 2 computers with port count 1.”

This is because if there are 2 computers with port count 1, selecting those 2 computers guarantees we can construct a tree with \(k=2\) (a structure connected by a single cable). In this case, the sum of port counts is \(1 + 1 = 2\), which satisfies the formula \(2(k-1) = 2(2-1) = 2\).

Conversely, if there are 0 or only 1 computer with port count 1, then no matter which combination of \(k \geq 2\) computers is chosen, there won’t be enough “leaves” for the tree structure (or the sum of degrees will exceed \(2k-2\)), making it impossible to construct a network that satisfies the conditions.

Algorithm

1. Check the input values \(A_1, A_2, \ldots, A_N\) in order.
2. Determine whether either of the following conditions is satisfied:
   • There exists at least 1 computer with \(A_i = 0\).
   • There exist at least 2 computers with \(A_i = 1\).
3. If a condition is satisfied, output Yes; otherwise, output No.

Complexity

• Time complexity: \(O(N)\)
  • The determination can be made with a single pass through \(N\) elements, making it very fast.
• Space complexity: \(O(1)\)
  • If the input values are processed on the spot, no additional arrays are needed (if storing the input, it becomes \(O(N)\)).

Implementation Notes

• Since \(N\) can be as large as \(10^6\), in C++ it is safe to speed up I/O using std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);.

• Although \(A_i\) values can be as large as \(10^9\), the only information needed for the determination is whether a value is \(0\), \(1\), or something else, so there is no need to worry about special types (such as long long).

  Source Code

#include <iostream>

/**
 * Problem: Network Construction
 * 
 * Logic:
 * 1. The problem asks if a subset of computers can be chosen to form a tree
 *    where each chosen computer $i$ uses exactly $A_i$ ports.
 * 2. If we choose a single computer ($k=1$), it must have $A_i = 0$ ports
 *    because a tree with 1 node has 0 edges.
 * 3. If we choose $k \ge 2$ computers, they must form a tree with $k-1$ edges.
 *    The sum of their degrees must be $2(k-1)$. Since it's a tree, every
 *    chosen computer must have at least one connection ($A_i \ge 1$).
 * 4. For a sequence $d_1, d_2, \dots, d_k$ to be the degree sequence of a simple tree,
 *    it must satisfy $d_i \ge 1$ and $\sum d_i = 2(k-1)$.
 * 5. The condition $\sum_{i \in S} A_i = 2|S| - 2$ with $A_i \ge 1$ implies that
 *    at least two of the chosen computers must have $A_i = 1$.
 *    Proof: Let $k = |S|$. $\sum (A_i - 1) = (2k-2) - k = k-2$.
 *    If we have $k_1$ computers with $A_i = 1$ (so $A_i - 1 = 0$), the remaining
 *    $k - k_1$ computers have $A_i - 1 \ge 1$. Thus, $\sum (A_i - 1) \ge k - k_1$.
 *    So $k - k_1 \le k - 2$, which means $k_1 \ge 2$.
 * 6. Therefore, a valid network can be built if and only if:
 *    - There exists at least one $A_i = 0$ (for the $k=1$ case).
 *    - There exist at least two computers with $A_i = 1$ (for the $k \ge 2$ case).
 *      If we have at least two $1$s, we can always form a tree with $k=2$ using them.
 */

int main() {
    // Optimize input and output performance
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int N;
    if (!(std::cin >> N)) return 0;

    bool has_zero = false;
    int count_ones = 0;

    for (int i = 0; i < N; ++i) {
        int a;
        std::cin >> a;
        if (a == 0) {
            has_zero = true;
        } else if (a == 1) {
            count_ones++;
        }
    }

    // If there is any computer with 0 ports, we can pick just that one (k=1).
    // If there are at least two computers with 1 port, we can pick them (k=2).
    // Any larger tree (k > 2) also requires at least two computers with 1 port.
    if (has_zero || count_ones >= 2) {
        std::cout << "Yes" << std::endl;
    } else {
        std::cout << "No" << std::endl;
    }

    return 0;
}

---

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