AtCoder AGC010 C - Cleaning

エディトリアルの判定

L>=min(max(c[i]), Σ(c[i])/2)
がよくわからなかった。

以下、条件判定の考察のみ
変数名はエディトリアルのものを踏襲

葉ではない頂点をv、
m = max(c[i])
とする。

T >= 0 (1)
は自明。

A[v]が最大になるのは
子供=>v=>親　を含む経路がすべてで
子供x=>v=>子供y (x!=y) を含む経路が１つもない場合であり、
A[v] <= Σ(c[i]) (2)
が成り立つ。

m = c[u] を満たす頂点uについて
u=>v=>x (xはvの親またはuでないvの子供)
を含む経路がc[u]個あるので
vを含む経路の数A[v]は
m<=A[v] (3)
を満たす。

逆に(1)～(3)が成り立つと仮定する。
T + (Σc[i]-T)/2 = A[v]
を整理すると
T = 2A[v] - Σc[i]
よって
L
= (Σc[i]-T)/2
= (Σc[i]-(2A[v]-Σc[i]))/2
= (2Σc[i]-2A[v])/2
= Σc[i]-A[v]
L個以上のペアが作れるかどうか判定したいのだった。
これは
ペアとならないものがH=Σc[i]-2L　個以下である
ことと同値。
H
= Σc[i]-2L
= Σc[i]-2*(Σc[i]-A[v])
= 2A[v]-Σc[i]
ここで
(2),(3)より
m<=Σ(c[i])
なので
H<=2A[v]-m (4)

ペアとならないものは
H' = m
個以下にすることができる。
vの子をc[i]の昇順に見ていく。
簡単のためi<jならばc[i]<=c[j]とする。
l個まで子を見たとき、子i<=lについてペアとならないものがc[l]個以下となるようにペアを作れる
これは帰納法で示せる。
よってすべての(k個の)子供を全部見たとき
ペアとならないものをH'個以下にできている。

H'<=H
を示す。
H-H'
= (2A[v]-m) - m
= 2(A[v]-m)
>= 2(m-m) // (3)より
= 0
∴ H>=H'
ペアとならないものをH個以下にできた。

以上から、条件判定は(1)～(3)だけでよい。

解法まとめ

根付き木にして各頂点とその親をつなぐ辺を頂点ごとに処理する。根の処理だけ特殊なので注意。