読者です 読者をやめる 読者になる 読者になる

全域木

Codeforces #403(Div. 2) E: Underground Lab

解法 k人のクローンがいてそれぞれceil(2n/k)個の頂点を訪れることができるので、訪れることができる頂点の数の合計Sは S = ceil(2n/k)*k >= 2n 与えられたグラフは連結グラフなので全域木が存在する。与えられたグラフのある全域木Tについて考える。 TでDFS…