B - Network Construction Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 333 点

問題文

高橋君は N 台のコンピュータを管理しています。各コンピュータには番号 1 から N が付けられており、コンピュータ i にはネットワークポートがちょうど A_i 個あります。

高橋君はこれらのコンピュータの中から 1 台以上を選び（同じコンピュータを複数回選ぶことはできません）、選んだコンピュータ同士をケーブルで接続してネットワークを構築したいと考えています。ケーブルによる接続は、以下のルールに従います。

  • ケーブル 1 本は、選んだコンピュータのうち異なる 2 台のポートを 1 つずつ使って接続する。
  • 同じ 2 台のコンピュータ間に複数本のケーブルを接続することはできない。

次の条件をすべて満たすようにネットワークを構築できるか判定してください。

  • 木構造条件： 選んだコンピュータ全体が木構造をなす。すなわち、選んだコンピュータが k 台（k \geq 2）の場合、ケーブルがちょうど k - 1 本あり、選んだ任意の 2 台のコンピュータ間にケーブルをたどる経路がちょうど 1 通り存在する。選んだコンピュータが 1 台のみの場合は、ケーブルが 0 本でこの条件を満たすとみなす。
  • ポート使い切り条件： 選んだ各コンピュータについて、そのすべてのポートが使われている。すなわち、選んだコンピュータ i に接続されるケーブルの本数がちょうど A_i 本である（A_i = 0 のコンピュータを 1 台だけ選んだ場合、ケーブル 0 本で条件を満たす）。

条件を満たすネットワークを構築できるなら Yes を、できないなら No を出力してください。

制約

  • 1 \leq N \leq 10^6
  • 0 \leq A_i \leq 10^9
  • 入力はすべて整数である

入力

N
A_1 A_2 \ldots A_N
  • 1 行目には、コンピュータの台数を表す整数 N が与えられる。
  • 2 行目には、各コンピュータのポート数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。

出力

条件を満たすネットワークを構築できるなら Yes を、できないなら No を 1 行に出力せよ。

入力例 1

3
1 2 1

出力例 1

Yes

入力例 2

2
2 2

出力例 2

No

入力例 3

10
3 1 1 1 7 4 2 2 5 9

出力例 3

Yes

入力例 4

40
20 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

出力例 4

Yes

入力例 5

1
0

出力例 5

Yes

Score : 333 pts

Problem Statement

Takahashi manages N computers. Each computer is numbered from 1 to N, and computer i has exactly A_i network ports.

Takahashi wants to select one or more of these computers (each computer can be selected at most once) and connect the selected computers with cables to build a network. The cable connections must follow these rules:

  • One cable connects two distinct selected computers, using one port from each.
  • Multiple cables cannot be connected between the same pair of computers.

Determine whether it is possible to build a network satisfying all of the following conditions:

  • Tree structure condition: The selected computers form a tree structure. That is, if k computers are selected (k \geq 2), there are exactly k - 1 cables, and between any two selected computers there exists exactly one path following cables. If only one computer is selected, this condition is considered satisfied with 0 cables.
  • Port exhaustion condition: For each selected computer, all of its ports are used. That is, the number of cables connected to selected computer i is exactly A_i (if only one computer with A_i = 0 is selected, the condition is satisfied with 0 cables).

If a network satisfying the conditions can be constructed, output Yes; otherwise, output No.

Constraints

  • 1 \leq N \leq 10^6
  • 0 \leq A_i \leq 10^9
  • All inputs are integers

Input

N
A_1 A_2 \ldots A_N
  • The first line contains an integer N representing the number of computers.
  • The second line contains the number of ports for each computer A_1, A_2, \ldots, A_N, separated by spaces.

Output

If a network satisfying the conditions can be constructed, output Yes; otherwise, output No on a single line.

Sample Input 1

3
1 2 1

Sample Output 1

Yes

Sample Input 2

2
2 2

Sample Output 2

No

Sample Input 3

10
3 1 1 1 7 4 2 2 5 9

Sample Output 3

Yes

Sample Input 4

40
20 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output 4

Yes

Sample Input 5

1
0

Sample Output 5

Yes