algorithm - これらの長さの乗算が最大になるような、ツリー内の 2 つのノード分離パス

Question

この 2 つのパスに共通のノードがなく、この 2 つのパスの長さの乗算が最大になるように、n ノードを持つツリーで 2 つのパスを見つけたいと考えています。誰でもこの問題を解決する方法を教えてくれますか?

Answer 1

まず、再帰的な手順を使用して、考えられるすべての一意のパスのリストを生成します。

最終的にはm個の可能なパスになります。

次に、mxm要素の配列を設定します。

m個のパスのすべてを他のすべてのm-1パスと一緒にチェックし、それぞれの長さの乗算を配列に格納します。その際、2つのパスに共通のノードがあるかどうかを確認してください。もしそうなら、0を保存します。

3番目に、最大値を持つ要素のmxm配列を確認します。

他に何ができますか？これは非常に力強いものですが、ツリーのプロパティに関する情報がこれ以上わからない場合は、これが唯一の方法です。

Answer 2

いくつかの考え。合計がnになる2つの値aとbがある場合、a*bの最大値はa==bのときです（簡単にするために、nは偶数であると仮定します）。n個のノードすべてを通過するパスがある場合は、それを2つのほぼ等しい部分に分割します。偶数nのこのようなグラフの場合、答えは（n ^ 2）/ 4になり、奇数nの場合、答えは（n-1）/ 2 *（n + 1）/ 2 =（n ^ 2 --1）/4になります。 n個のノードすべてを通過するパスがない場合は、他の手法を使用する必要があります。ただし、上限は上記のとおりです。