問題
ノード数がN()の木(tree)が与えられる。各辺(edge)は双方向(bidirectional)であり、長さlength(
)が定義されている。互いに同じ距離となるノードの集合の最大要素数を答えよ。
解法
まずノードの数が1つである場合は1となり、2の場合は必ず2となる。
木構造であるため、互いに同じ距離となるノードの集合には必ず中心となるノードが存在する。今回見つけたい集合は中心ノードからの距離が同じノードの集合の部分集合になる。完全一致しない理由は、集合内のノード同士の最短パスで中心ノードを経由しないパスが存在する可能性があるからである。最短パスが中心ノードを通ることを確認することで、目的の集合を見つけることができる。
計算量
N: ノード数