Overview

This is a problem where we determine whether the port numbers of the selected computers can be realized as the degrees of each vertex in a tree.

In conclusion, the answer is Yes only in one of the following cases:

• There is at least \(1\) computer with \(A_i = 0\)
• There are at least \(2\) computers with \(A_i = 1\)

Analysis

The “degree” in a tree is the number of edges connected to that vertex.
In this problem, the degree of each selected computer \(i\) must be exactly \(A_i\).

Selecting only 1 computer

If we select only \(1\) computer, the number of cables is \(0\).

Therefore, the condition is satisfied if that computer’s port number is \(0\).

In other words, if there exists any \(A_i = 0\), the answer is always Yes.

Selecting 2 or more computers

When selecting \(2\) or more computers, the constructed network is a tree.

Trees have an important property:

A tree with \(2\) or more vertices has at least \(2\) vertices of degree \(1\).

Vertices of degree \(1\) are called “leaves.”

In this problem, since the degree is exactly \(A_i\), there must be at least \(2\) computers with \(A_i = 1\) among the selected computers.

Conversely, if there are \(2\) computers with \(A_i = 1\), we can simply select those \(2\) and connect them with \(1\) cable.

In this case, both computers have degree \(1\), satisfying both the tree structure condition and the port usage condition.

For example,

A = [3, 1, 5, 1]

Since there are \(2\) computers with \(A_i = 1\), we can select just those \(2\) and connect them, giving Yes.

On the other hand,

A = [2, 3, 1]

There is no \(A_i = 0\), and there is only \(1\) computer with \(A_i = 1\).
Since a tree with \(2\) or more vertices requires at least \(2\) leaves, this is impossible.

Why a brute-force approach is unnecessary

There is no need to try all subsets or determine whether a degree sequence can be realized as a tree.

This is because the following conditions are necessary and sufficient:

• There exists \(A_i = 0\)
• There are at least \(2\) occurrences of \(A_i = 1\)

Therefore, the problem can be solved by scanning the entire array just once.

Algorithm

We determine the answer as follows:

1. If \(A_i = 0\) is found, immediately output Yes
2. Count the number of \(A_i = 1\)
3. If the count of \(A_i = 1\) reaches \(2\) or more, immediately output Yes
4. If neither condition is met after scanning everything, output No

Summarizing the conditions:

If 0 exists OR there are 2 or more 1's

then Yes, otherwise No.

Complexity

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

Implementation Notes

Since the input size can be as large as \(N = 10^6\), fast input is used.

This implementation reads the entire input with sys.stdin.buffer.read() and scans the numbers as strings.

For the determination, we only need to check whether each \(A_i\) is \(0\) or \(1\).
Therefore, instead of converting to integers, we only check whether the token is "0" or "1".

if c == 48:  # '0'
    print("Yes")
if c == 49:  # '1'
    ones += 1

Additionally, by terminating immediately once Yes is confirmed, unnecessary processing is avoided.

Source Code

import sys

def main():
    data = sys.stdin.buffer.read()
    n = len(data)
    i = 0

    while i < n and data[i] > 32:
        i += 1

    ones = 0

    while i < n:
        while i < n and data[i] <= 32:
            i += 1
        if i >= n:
            break

        start = i
        while i < n and data[i] > 32:
            i += 1

        if i - start == 1:
            c = data[start]
            if c == 48:
                sys.stdout.write("Yes\n")
                return
            if c == 49:
                ones += 1
                if ones >= 2:
                    sys.stdout.write("Yes\n")
                    return

    sys.stdout.write("No\n")

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.