きままにものづくり

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

SRM591Div1Easy

問題

ルートからの距離がxであるノードを cnt_x個持つツリーを考える。この時のツリーの直径を求めよ。

解法

各ノードをルートとした時の子であるノードの中で深さが最大となる2つを選ぶ。これを全てのノードに対して行うことで答えが求まる。
最初に与えられたツリーのルートが、直径となるノードどうしのパスに含まれるとは限らない。しかし、必ずルートを通るという条件をつけると、その時の最大距離は子であるノードの長で深さが最大となる2つを足し合わせた値となる。

計算量

 O(N^2)

コード