Codeforces Round #628 (Div. 2) - F. Ehab's Last Theorem
類題 と聞いてたのに、こっちのほうがかなり難しいじゃないですか( ;∀;)
解説
とします。
全域木をとってきて、根つき木としてかんがえましょう!
根から順にみていって、全域木に使っていない辺を1つつかって、サイクル長が以上のサイクルを作ることができたらそこで終了です。
それが作れない場合、この全域木においては、以上離れている祖先と直接繋いでいる辺がないことがいえます。(もし以上離れていて、直接つながっているならそれと結べば、サイクル長が以上のサイクルが作れることから示せます)
あとは貪欲に根から独立集合をとっていけば大丈夫です。
よってこの問題を解くことができました!