2n与えられたグラフは連結グラフなので全域木が存在する。与えられたグラフのある全域木Tについて考える。TでDFSした時、頂点を見る順番は頂点v(初めて訪れた)=>頂点vの子w=>...=>頂点v(wから戻ってきた)のようになる。このとき、順番が隣り合う場合は必ず2頂点はある辺で結ばれていることがわかる。よって、DFSの探索順で頂点を訪れればすべての頂点を訪れることができる。この頂点の探索順を配列Aで表すとする。|A|<=Sであれば、Aの順に頂点を訪れていけばよい。全域木の辺の数はn-1であり、各辺は2回ずつ訪れてその度に訪れた頂点の数は増えていく。AtCoder月別アーカイブはてなブログをはじめよう!parukiiさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。