SRM 716 DIV1 450: JumpDistancesOnTree

まず与えられた木の全点対の距離を計算しておく。

これを

d[u][v]: (u, v)間の距離

としておく。

d[u][v] ∈ Sかつu!=v であるような辺(u, v)をすべて持つようなグラフをHとする。このグラフでスタート地点の頂点0から探索して到達可能な頂点の集合をVとする。H上でv∈Vに到達できるということは、与えられた木の上での移動距離d[i]がすべてSに属することと同じ。ただし、Sの元うちどれを使っていて、どれを使っていないかは不明。ここで頂点w∈Vを

d[w][v] = Sの最大値

であるような頂点vが存在するような頂点とする。

もしそのような頂点が存在するならば、Sの元をすべて使うことができる。逆に、そうでなければ駄目なのは自明。

S[i]<S[i+1]

が成り立つのであった。

よってS[i+1]の移動ができると仮定すると、その移動とは逆方向にS[i]だけ移動することができる。したがってSの最大値の移動ができるならば、Sに属する距離になるようなすべての移動ができる。