きままにものづくり

日々の気付いたことなんかを書いてます。

SRM630Div1Easy

問題

ノード数がN( N \leq 50)の木(tree)が与えられる。各辺(edge)は双方向(bidirectional)であり、長さlength( length \leq 1000)が定義されている。互いに同じ距離となるノードの集合の最大要素数を答えよ。

解法

まずノードの数が1つである場合は1となり、2の場合は必ず2となる。
木構造であるため、互いに同じ距離となるノードの集合には必ず中心となるノードが存在する。今回見つけたい集合は中心ノードからの距離が同じノードの集合の部分集合になる。完全一致しない理由は、集合内のノード同士の最短パスで中心ノードを経由しないパスが存在する可能性があるからである。最短パスが中心ノードを通ることを確認することで、目的の集合を見つけることができる。

計算量

 O(N^3)
N: ノード数

コード