Overview

We determine whether it is possible to select some computers such that all ports of the selected computers are fully used and the selected vertices form a tree.
In conclusion, the answer is Yes if there exists a computer with \(A_i=0\), or if there are \(2\) or more computers with \(A_i=1\).

Analysis

First, we consider cases based on the number of computers selected.

Selecting only 1 computer

If we select only \(1\) computer, there are \(0\) cables.

Since all ports must be fully used, the selected computer must have \(0\) ports.

In other words, if there exists a computer with \(A_i=0\), we can satisfy the condition by selecting only that one computer.

Selecting 2 or more computers

When \(k \geq 2\) computers are selected, the network is a tree.

Trees have an important property:

• A tree with \(2\) or more vertices has at least \(2\) vertices of degree \(1\), i.e., at least \(2\) leaves.

Here, the degree of each computer equals the number of cables it uses.
Also, since all ports must be fully used, the degree of a selected computer \(i\) is exactly \(A_i\).

Therefore, to form a tree by selecting \(k \geq 2\) computers, at least \(2\) of the selected computers must have \(A_i=1\).

Conversely, if there are \(2\) or more computers with \(A_i=1\), we can select just those \(2\) and connect them with a single cable.

In this case:

• The number of vertices is \(2\)
• The number of edges is \(1\)
• Both vertices have degree \(1\)

So it forms a tree that satisfies the conditions.

Why a brute-force approach is unnecessary

Trying all subsets of computers would require up to \(2^N\) cases, which is far too slow for \(N \leq 10^6\).

However, from the analysis above, we only need to check:

• Whether \(A_i=0\) exists
• Whether there are \(2\) or more \(A_i=1\)

Therefore, we can determine the answer by scanning the array just once.

Algorithm

Perform the following steps in order:

1. Set has_zero to false
2. Set count_one to \(0\)
3. For each \(A_i\):
   • If \(A_i=0\), set has_zero = true
   • If \(A_i=1\), increment count_one by \(1\)
4. Finally:
   • If has_zero is true
   • or count_one >= 2

then output Yes; otherwise output No

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\)

Implementation Notes

Since \(N\) can be up to \(10^6\), there is no need to store the entire array.
It is sufficient to simply count whether there is a \(0\) and how many \(1\)s there are while reading the input.

Also, since \(A_i\) can be up to \(10^9\), it fits in int, but in the code we safely read it as long long.

Source Code

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

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

    int N;
    cin >> N;

    bool has_zero = false;
    int count_one = 0;

    for (int i = 0; i < N; ++i) {
        long long A;
        cin >> A;
        if (A == 0) has_zero = true;
        if (A == 1) ++count_one;
    }

    cout << (has_zero || count_one >= 2 ? "Yes" : "No") << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.