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