parukii https://blog.hatena.ne.jp/parukii/ parukiのブログ https://par.hateblo.jp/ 木 BFS 1個の町に複数の警察署がある場合もありうるが、明らかに無意味なので1個の町にはたかだか1個の警察署しか無いとする。 道路で結ばれた町は、全体で木になっている。 ある頂点が複数の警察署でカバーされているとする。そのうち最も近い頂点をu,二番目に近い頂点をvとする。グラフは木なのでu,v間の単純道はただ1個であって、その単純道には必ず複数の警察署でカバーされる頂点が存在する。なので、u,v間の単純道で真ん中あたりの辺は1個取り除くことができる。 この操作を可能な限り繰り返すと、警察署と同じ数の部分木に分割されることがわかる。ただし、各部分木はちょうど1個の警察署を含み、しかも部分木のすべての頂点は… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fpar.hateblo.jp%2Fentry%2F2017%2F04%2F11%2F131359" title=" Codeforces #408 (Div. 2) D: Police Stations - parukiのブログ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/p/parukii/20170411/20170411134038.jpg Hatena Blog https://hatena.blog 2017-04-11 13:13:59 rich https://par.hateblo.jp/entry/2017/04/11/131359 1.0 100%