Overview

This is a problem of determining whether the number of ports on the selected computers can be regarded as “the degrees of vertices in a tree.”
In conclusion, the answer is Yes if there is at least one computer with A_i=0, or if there are two or more computers with A_i=1; otherwise, the answer is No.

Analysis

This problem can be rephrased as: “Can we choose some subset such that its degree sequence can form a tree?”

A well-known property of trees states that if the number of vertices is \(k\) and the degree of each vertex is \(d_1,\dots,d_k\), then

\[ \sum_{j=1}^{k} d_j = 2(k-1) \]

holds (the number of edges is \(k-1\), and the sum of degrees is twice the number of edges).

---

First, consider the case \(k=1\) (selecting only one computer).
In this case, there are 0 cables, so to satisfy the condition of using all ports, that one computer must have 0 ports.
In other words, if there is even one A_i=0, the answer is immediately Yes.

---

Next, consider the case \(k\ge2\). Since the selected vertices are vertices of a tree, every vertex has degree at least 1.
Therefore, we cannot include any A_i=0 among the selected vertices.

Now let’s transform the equation.
Let \(w_i = A_i - 2\). Then the degree sum condition becomes

\[ \sum (A_i - 2) = -2 \]

The value of \(w_i\) for each value of A_i is:

• \(A_i=1 \Rightarrow w_i=-1\)
• \(A_i=2 \Rightarrow w_i=0\)
• \(A_i\ge3 \Rightarrow w_i\ge1\)

To make this sum equal to \(-2\), we need at least two negative values (\(-1\)).
In other words, if there are fewer than 2 instances of A_i=1, it is impossible.

Conversely, if there are 2 or more instances of A_i=1, we can select just those two computers to form a tree with degree sequence \((1,1)\) (a single edge), which satisfies the condition.
(Adding vertices with A_i=2 doesn’t change the sum, and we don’t need to include them if unnecessary.)

Therefore, the decision criteria become extremely simple:

1. If there is at least one A_i=0 → Yes
2. Otherwise, if there are two or more A_i=1 → Yes
3. Otherwise → No

---

A naive approach of trying “all subsets” would require \(2^N\) cases, which is infeasible for \(N\le10^6\).
By using the degree sum property above, we can determine the answer by scanning the array just once.

Algorithm

1. Count cnt0 (number of A_i=0) and cnt1 (number of A_i=1).
2. If cnt0 > 0, output Yes and terminate.
3. Otherwise, if cnt1 >= 2, output Yes; otherwise, output No.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\) (because the presented code stores the array A. If we only count, it can be reduced to \(O(1)\))

Implementation Notes

• Since \(N\) can be large, use fast I/O with ios::sync_with_stdio(false); cin.tie(nullptr);.

• Since only cnt0 and cnt1 are needed for the actual decision, theoretically it suffices to just count while reading the input.

• Although A_i can be up to \(10^9\), for this problem’s decision criteria, we only need to distinguish between 0/1/other.

  Source Code

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<long long> A(N);
    long long cnt0 = 0, cnt1 = 0;
    bool has_ge2 = false;

    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        if (A[i] == 0) cnt0++;
        else if (A[i] == 1) cnt1++;
        else has_ge2 = true;
    }

    // k=1 case: choose one computer with A_i=0
    if (cnt0 > 0) {
        cout << "Yes\n";
        return 0;
    }

    // For k>=2 tree using all ports:
    // degree sequence must satisfy:
    // 1) all chosen degrees >=1 (already true since no zero in chosen set)
    // 2) sum(deg) = 2(k-1)  <=> sum(deg-2) = -2
    // Let w_i = A_i - 2.
    // Need non-empty subset (k>=2) with sum w_i = -2.
    // Here A_i>=1 for all i. Then:
    // A_i=1 => w_i=-1, A_i=2 => 0, A_i>=3 => >=1.
    // To make sum -2, we must include exactly two -1's and no positive net excess,
    // which is always possible iff there are at least two A_i=1 (choose those two,
    // optionally any number of A_i=2).
    if (cnt1 >= 2) cout << "Yes\n";
    else cout << "No\n";

    return 0;
}

---

This editorial was generated by gpt-5.3-codex.