IOI 2019

split

解法（というかwriter）が天才すぎる。

問題概要

N頂点の無向連結グラフが与えられる

整数 a,b,c も与えられる（a+b+c=N）

頂点を３グループに分けて下さい

それぞれのサイズが a, b, c になるように

２つ以上のグループが連結になっているように

制約は適当

解法

a ≦ b ≦ c として、a, bのグループを連結にすればいい

例えば a, c が連結なら c から何点か削除すれば a, b にできるため

適当に全域木を取って場合分け

辺を１本切って、両方のサイズを a 以上にできる

小さい方 ≧ a かつ 大きい方 ≧ N/2 ≧ b なので自明にできる

そうでない場合

重心を v とすると、v にサイズ a 未満の部分木がいくつかくっついた形になる

v を取り除いたときにサイズ a 以上の連結成分ができるなら可能

部分木たちを全域木外の辺でくっつけていき、サイズが a 以上になったらやめる、をする

これでできる連結成分から a を取る

残った部分木たち+v の木から b を取る

残り物のサイズ ≧ b を示したい

a を取る連結成分のサイズは a 以上 2a 未満になる

つまり残った頂点は N - 2a 以上

b は (N - a)/2 以下

示したい式： N - 2a ≧ (N - a)/2

→ 2N - 4a ≧ N - a

→ N ≧ 3a　となり、a≦b≦cよりこの式は正しい

できないなら不可能

v を含まないグループではサイズ a 以上の連結成分が作れないため