D - Yet Another Degree Sequence Problem Editorial /

Time Limit: 8 sec / Memory Limit: 1024 MiB

配点 : 1900 点

問題文

次の判定問題 X を考えます．

  • 頂点集合が V=\{1,2,\ldots,N\} である単純無向グラフ G と，長さ N の正整数列 D=(D_1,D_2,\ldots,D_N) が与えられる．ここで，G における頂点 i の次数を \deg_G(i) とすると，D_i\leq \deg_G(i) がすべての頂点 i について成り立つ．また，\sum_{i=1}^N D_i は偶数である．
  • G の辺を 0 本以上削除し，すべての頂点 i の次数を D_i にできるか判定する．できる場合の答えを Possible，できない場合の答えを Impossible とする．

S\subseteq V に対して，次のように定義します．

  • e_G(S)：両端がともに S に含まれる G の辺の本数．
  • e_G(i,S)：頂点 i\notin S と S 内の頂点を結ぶ G の辺の本数．

すぬけ君は，問題 X について次の予想 Y を考えました．

「V の任意の部分集合 S に対して \left(\sum_{i\in S}D_i\right)-2e_G(S)\leq \sum_{i\notin S}\min(D_i,e_G(i,S)) が成り立つ」ことと，「問題 X の答えが Possible である」ことは同値である．

直感的に言えば，「S から外へ出るべき辺の数」が「S 以外の頂点から S へ向かって張れる辺の個数の最大値の和」を超えてはならない，という条件です．

しかし，この予想は正しくありません．

長さ N の正整数列 D が与えられます．\sum_{i=1}^N D_i は偶数です． 頂点集合が V であり，すべての頂点 i について D_i\leq\deg_G(i) を満たす単純無向グラフ G のうち，(G,D) が予想 Y の反例となるものが存在するか判定してください．

1 つの入力につき，T ケースを解いてください．

制約

  • 1\leq T\leq 125000
  • 2\leq N\leq 250000
  • 1\leq D_i\leq N-1 (1\leq i\leq N)
  • \sum_{i=1}^N D_i は偶数である．
  • T ケースにわたる N の総和は 250000 以下である．
  • 入力される数値はすべて整数である．

入力

入力は標準入力から以下の形式で与えられる．

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各テストケースは以下の形式で与えられる．

N
D_1 D_2 \ldots D_N

出力

各テストケースについて，予想 Y の反例となるグラフ G が存在する場合は Yes，存在しない場合は No を出力せよ．

入力例 1

8
6
1 1 1 1 1 1
6
2 2 2 2 2 2
2
1 1
7
1 1 1 1 1 1 2
7
2 2 2 2 2 2 6
8
2 2 2 2 2 2 2 2
9
2 2 2 2 2 2 2 2 2
10
2 2 3 3 3 3 3 3 9 9

出力例 1

Yes
No
No
Yes
Yes
No
Yes
Yes

1 番目のテストケースでは，頂点 1,2,3 からなるサイクルと頂点 4,5,6 からなるサイクルを合わせたグラフを G とすればよいです． このとき，例えば S=\{1,2,4\} とすると，

  • 左辺: \left(\sum_{i\in S}D_i\right)-2e_G(S) = (D_1+D_2+D_4)-2 \times 1 = 1
  • 右辺: \sum_{i\notin S}\min(D_i,e_G(i,S)) = \min(D_3,2)+\min(D_5,1)+\min(D_6,1)=3

であり，予想 Y の不等式は満たされています． 同様にして，任意の部分集合 S について条件の成立が確認できます．

一方，G の辺をどのように消したとしても，すべての頂点の次数を 1 にすることはできません．したがってこの G は反例であり，答えは Yes です．

Score : 1900 points

Problem Statement

Consider the following decision problem X.

  • You are given a simple undirected graph G with vertex set V=\{1,2,\ldots,N\} and a length-N sequence of positive integers D=(D_1,D_2,\ldots,D_N). Here, letting \deg_G(i) denote the degree of vertex i in G, the inequality D_i\leq \deg_G(i) holds for every vertex i. Also, \sum_{i=1}^N D_i is even.
  • Determine whether it is possible to delete zero or more edges of G so that the degree of every vertex i becomes D_i. The answer is Possible if this can be done, and Impossible otherwise.

For S\subseteq V, define the following.

  • e_G(S): The number of edges of G with both endpoints in S.
  • e_G(i,S): The number of edges of G connecting vertex i\notin S to a vertex in S.

Snuke came up with the following conjecture Y about problem X.

The statement "for every subset S of V, \left(\sum_{i\in S}D_i\right)-2e_G(S)\leq \sum_{i\notin S}\min(D_i,e_G(i,S)) holds" is equivalent to the statement "the answer to problem X is Possible".

Intuitively, the condition says that "the number of edges that must leave S" must not exceed "the sum, over the vertices outside S, of the maximum number of edges that each of them can have toward S".

However, this conjecture is false.

You are given a length-N sequence of positive integers D, where \sum_{i=1}^N D_i is even. Determine whether there exists a simple undirected graph G with vertex set V satisfying D_i\leq\deg_G(i) for every vertex i such that (G,D) is a counterexample to conjecture Y.

You are given T test cases; solve each of them.

Constraints

  • 1\leq T\leq 125000
  • 2\leq N\leq 250000
  • 1\leq D_i\leq N-1 (1\leq i\leq N)
  • \sum_{i=1}^N D_i is even.
  • The sum of N over all test cases in a single input is at most 250000.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

N
D_1 D_2 \ldots D_N

Output

For each test case, output Yes if there exists a graph G that is a counterexample to conjecture Y, and No otherwise.

Sample Input 1

8
6
1 1 1 1 1 1
6
2 2 2 2 2 2
2
1 1
7
1 1 1 1 1 1 2
7
2 2 2 2 2 2 6
8
2 2 2 2 2 2 2 2
9
2 2 2 2 2 2 2 2 2
10
2 2 3 3 3 3 3 3 9 9

Sample Output 1

Yes
No
No
Yes
Yes
No
Yes
Yes

In the first test case, you can take G to be the graph consisting of a cycle on vertices 1,2,3 and a cycle on vertices 4,5,6. In this case, for example, for S=\{1,2,4\}:

  • Left-hand side: \left(\sum_{i\in S}D_i\right)-2e_G(S) = (D_1+D_2+D_4)-2 \times 1 = 1
  • Right-hand side: \sum_{i\notin S}\min(D_i,e_G(i,S)) = \min(D_3,2)+\min(D_5,1)+\min(D_6,1)=3

Thus, the inequality in conjecture Y holds. Similarly, the condition can be verified for every subset S.

On the other hand, no matter how the edges of G are deleted, it is impossible to make every vertex have degree 1. Therefore, this G is a counterexample, and the answer is Yes.