一般性を失わず，\(C_0=0\) とします． 便利のため，\(C_i=0\) となる \(2 \leq i \leq N\) について，\(C_i=2K+1\) と置き直しておきます．

頂点 \(1\) を削除したあと残るグラフを考え，その連結成分ごとに問題を分離できます．

\(1\) つの連結成分 \(X\) に対して問題を解きます． この連結成分 \(+\) スライム \(1\) から始めて，スライム \(1\) だけを残すことができる，と仮定し，必要条件を導きます．

問題設定を以下のように変形しておきます．

• まず，\(C_i\) に \(2K+1\) を足すという操作を最初に好きな回数行う． その後，スライムを消していく． ただしここで，\(u,v\) を選べる条件は，\(C_u+1 \leq C_v \leq C_u+K\) とする．

\(1 \leq C_i \leq K\) なる \(i\) は \(1\) つ以上存在するはずなので，その中で \(C_i\) の最大値を達成する \(i\) を \(r\) とおきます（同率の場合は任意の \(r\) をとる）． ここで，\(C_i > K\) を満たす \(i\) からなる任意の連結成分 \(Y\) について，以下の条件が成立するはずです．

• \(Y\) 内に，\(K+1 \leq C_i \leq C_r+K\) を満たす \(i\) が存在する．

この条件を，入力の \(C_i\) に関する条件として整理すると，以下のようにまとめられます．

• ある頂点 \(r\) が存在し，以下の条件を満たす．
• \(1 \leq C_r \leq K\)
• \(X\) から \(r\) を削除したあとのグラフの各連結成分 \(Z\) に対して，以下のいずれかが成立する．
  • \(Z\) に含まれるすべての \(i\) に対して，\(C_i \leq K\) である
  • \(Z\) に含まれる \(i\) であって，\(K+1 \leq C_i \leq C_r+K\) を満たすものが存在する．

これは必要条件ですが，これが十分条件であることを今から証明します．

上記の条件を満たす \(r\) をとり，各連結成分 \(Z\) に対し，以下の操作を行うことを考えます．

• \(C_i\leq K\) を満たすスライムをタイプP，\(K+1 \leq C_i \leq C_r+K\) を満たすスライムをタイプQ，\(C_r+K+1 \leq C_i\) を満たすスライムをタイプRと呼ぶことにする． 上記の条件が満たされているので，「タイプQが\(0\)匹かつタイプRが\(1\)匹以上」ではないことが保証されている． タイプRのスライムが存在するとき，タイプR以外のスライムも存在し，必然的に，隣接するスライム \(u,v\) であって，\(u\) がタイプR，\(v\) がタイプP or Q というものが存在する．ここで，\(u,v\) に対して操作を行う．\(C_u,C_v\) の値によってどちらがどちらを食うか変わるが，どのようなケースでも，タイプQのスライムが消えることはない． よってこの操作を繰り返すことで，タイプRのスライムが \(0\) 匹という状態に至ることができる． あとは，操作を可能な限り適当に行うことを考える． タイプPだけが生き残った場合，\(Z\)に対する処理はこれで終了する． タイプQだけが生き残った場合，生き残ったスライムをすべて \(r\) に食わせる． 結局，\(Z\)内にはタイプ\(P\)だけが残ることになる．

この操作のあと，\(X\) 内には \(1 \leq C_i \leq K\) を満たす \(i\) しか残っていません． よってこれらをすべてスライム \(1\) に食わせることができ，スライム \(1\) だけが残ります．

これで前述の条件の十分性が証明できました．

あとは，この条件をチェックすることを考えます． これは，グラフを関節点分解したあと木DPすればよいです． DPで各部分木に対して「\(C_i \geq K+1\) を満たす \(C_i\) の最小値」を求めておけば，条件のチェックが行えます．

計算量は \(O(N+M)\) です．

回答例(C++)