2 つのツリーを結合した後の最小直径を求める

3203。 2 つのツリーを結合した後の最小直径を求める

難易度: 難しい

トピック: ツリー、深さ優先検索、幅優先検索、グラフ

n と m のノードを持つ 2 つの 無向 ツリーが存在し、それぞれ 0 から n - 1 と 0 から m - 1 の番号が付けられます。それぞれ長さが n - 1 および m - 1 の 2 つの 2D 整数配列edges1 とedges2 が与えられます。ここで、edges1[i] = [a_i, b_i] は、最初のツリーのノード a_i と b_i の間のエッジであり、 edges2[i] = [u_i, v_i] は、ノード u_i と v_i の間にエッジがあることを示します。 2 番目の木。

最初のツリーの 1 つのノードと 2 番目のツリーの別のノードをエッジで接続する必要があります。

結果として得られるツリーの最小可能な直径を返します。

ツリーの直径は、ツリー内の 2 つのノード間の最長パスの長さです。

例 1:

• 入力: エッジ 1 = [[0,1],[0,2],[0,3]]、エッジ 2 = [[0,1]]
• 出力: 3
• 説明: 最初のツリーのノード 0 を 2 番目のツリーの任意のノードと接続することで、直径 3 のツリーを取得できます。

例 2:

• 入力:edges1 = [[0,1],[0,2],[0,3],[2,4],[2,5],[3,6],[2, 7]]、エッジ 2 = [[0,1],[0,2],[0,3],[2,4],[2,5],[3,6],[2,7]]
• 出力: 5
• 説明: 最初の木の節点 0 を 2 番目の木の節点 0 と接続すると、直径 5 の木が得られます。

制約:

• 1 5
• edges1.length == n - 1
• edges2.length == m - 1
• edges1[i].length ==edges2[i].length == 2
• edges1[i] = [a_i, b_i]
• 0 i, b_i
• edges2[i] = [u_i, v_i]
• 0 i, v_i
• 入力は、edge1 とedge2 が有効なツリーを表すように生成されます。

ヒント:

1. tree1 のノード a とtree2 のノード b を接続したとします。結果として得られるツリーの直径の長さは、次の 3 つの値のうち最大のものになります。
   1. 木の直径 1.
   2. 木の直径 2.
   3. ノード a で始まり、完全にツリー 1 内にある最長パスの長さ ノード b で始まり、完全にツリー 2 内にある最長パスの長さ 1.
   4. 3 番目の値に追加されたものは、ツリー 1 と 2 の間に追加した追加のエッジによるものです。
2. 値 1 と 2 は、a と b の選択に関係なく定数です。したがって、値 3 を最小化する方法で a と b を選択する必要があります。
3. a と b を最適に選択すると、それらはそれぞれ Tree 1 と Tree 2 の直径になります。正確に直径のどのノードを選択すればよいでしょうか?
4. a は木 1 の直径の中心、b は木 2 の直径の中心です。

解決策:

木の直径を計算する方法と、2 本の木の接続が全体の直径にどのような影響を与えるかを理解することに重点を置き、段階的にアプローチする必要があります。

解決する手順:

1. 各木の直径を求めます:

   • 木の直径は、2 つのノード間の最長の経路です。それを見つけるには、次の 2 段階のプロセスを使用できます。
     1. 任意のノードから BFS (または DFS) を実行して、最も遠いノード (このノード A と呼びます) を見つけます。
     2. A から開始して別の BFS (または DFS) を実行して、A から最も遠いノード (このノードを B と呼びます) を見つけます。A から B までの距離がツリーの直径になります。

2. 接続する最適なノードを決定します:

   • 問題のヒントから、2 本の木を接続するときに追加直径を最小限に抑える最良の方法は、両方の木の直径の中心を接続することです。これにより、新しいエッジによって生じる最長パスが最小限に抑えられます。
   • ツリーの直径における最適なノードは通常、「中心」です。これは、直径の端点から BFS を実行し、最長のパスの中間を見つけることで見つけることができます。

3. 合計直径を最小化します:

   • 両方のツリーの中心が見つかったら、新しい直径は次の最大値になります。
     • ツリー 1 の直径。
     • ツリー 2 の直径。
     • ツリー 1 内の最長パス、ツリー 2 内の最長パス、および新しい接続エッジの 1 の合計。

このソリューションを PHP で実装してみましょう: 3203。 2 つのツリーを結合した後の最小直径を求める

<?php /**
 * @param Integer[][] $edges1
 * @param Integer[][] $edges2
 * @return Integer
 */
function minimumDiameterAfterMerge($edges1, $edges2) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Helper function to find the diameter of a tree and the farthest node from a start node
 *
 * @param $n
 * @param $edges
 * @param $start
 * @return array
 */
function bfs($n, $edges, $start) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Helper function to find the diameter of a tree and its center
 *
 * @param $n
 * @param $edges
 * @return array
 */
function getDiameterAndCenter($n, $edges) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
$edges1 = [[0,1],[0,2],[0,3]];
$edges2 = [[0,1]];
echo minimumDiameterAfterMerge($edges1, $edges2);  // Output: 3

// Example 2
$edges1 = [[0,1],[0,2],[0,3],[2,4],[2,5],[3,6],[2,7]];
$edges2 = [[0,1],[0,2],[0,3],[2,4],[2,5],[3,6],[2,7]];
echo minimumDiameterAfterMerge($edges1, $edges2);  // Output: 5
?>

説明：

1. BFS ヘルパー関数: bfs 関数は、指定された開始ノードから最も遠いノードを計算し、距離配列と見つかった最も遠いノードを返します。これは木の直径を計算するために不可欠です。

2. 直径と中心の取得: getDiameterAndCenter 関数は、木の直径とその中心を見つけます。ツリーの中心は、2 つのツリーを結合するときに新しいツリーの直径を最小限に抑えるために重要です。

3. 主な解決策:

   • 最初に両方のツリーの隣接リストを構築します。
   • 両方の木の直径と中心を計算します。
   • 両方のツリーの中心から BFS を実行して、各ツリー内の最長のパスを取得します。
   • 最後に、3 つの値の最大値を計算して、結合されたツリーの最小直径を取得します。

時間計算量:

• 隣接リストの構築: O(n m)
• BFS トラバーサル: O(n m)
• 全体の時間計算量は O(n m) で、入力サイズ制限 10⁵ に対して効率的です。

このアプローチにより、2 つのツリーを結合するときに可能な最小直径が確実に見つかります。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上が2 つのツリーを結合した後の最小直径を求めるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。