Codeforces #403(Div. 2) E: Underground Lab
解法
k人のクローンがいてそれぞれceil(2n/k)個の頂点を訪れることができるので、訪れることができる頂点の数の合計Sは
S = ceil(2n/k)*k >= 2n
与えられたグラフは連結グラフなので全域木が存在する。与えられたグラフのある全域木Tについて考える。
TでDFSした時、頂点を見る順番は
頂点v(初めて訪れた)=>頂点vの子w=>...=>頂点v(wから戻ってきた)
のようになる。
このとき、順番が隣り合う場合は必ず2頂点はある辺で結ばれていることがわかる。よって、DFSの探索順で頂点を訪れればすべての頂点を訪れることができる。この頂点の探索順を配列Aで表すとする。
|A|<=S
であれば、Aの順に頂点を訪れていけばよい。
全域木の辺の数は
n-1であり、各辺は2回ずつ訪れてその度に訪れた頂点の数は増えていく。また最初の1頂点(根)も考慮すれば
|A| = 2(n-1)+1=2n-1
であり|A|<S
思いつき方
連結グラフ→全域木
k人が訪れることのできる頂点数の合計は?→2n