Codeforces #408 (Div. 2) D: Police Stations

1個の町に複数の警察署がある場合もありうるが、明らかに無意味なので1個の町にはたかだか1個の警察署しか無いとする。

道路で結ばれた町は、全体で木になっている。

ある頂点が複数の警察署でカバーされているとする。そのうち最も近い頂点をu,二番目に近い頂点をvとする。グラフは木なのでu,v間の単純道はただ1個であって、その単純道には必ず複数の警察署でカバーされる頂点が存在する。なので、u,v間の単純道で真ん中あたりの辺は1個取り除くことができる。

この操作を可能な限り繰り返すと、警察署と同じ数の部分木に分割されることがわかる。ただし、各部分木はちょうど1個の警察署を含み、しかも部分木のすべての頂点はその警察署から距離d以内にある。

このような部分木に分割して取り除いた辺(使用しなかった辺)をすべて求めたい。

そのためには、すべての警察署を始点としてBFSすればいい。