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から戻ってきた)

のようになる。

このとき、順番が隣り合う場合は必ず２頂点はある辺で結ばれていることがわかる。よって、DFSの探索順で頂点を訪れればすべての頂点を訪れることができる。この頂点の探索順を配列Aで表すとする。

|A|<=S

であれば、Aの順に頂点を訪れていけばよい。

全域木の辺の数は

n-1であり、各辺は2回ずつ訪れてその度に訪れた頂点の数は増えていく。また最初の1頂点(根)も考慮すれば

|A| = 2(n-1)+1=2n-1

であり|A|<S

連結グラフ→全域木

k人が訪れることのできる頂点数の合計は?→2n