LeetCodeを解き続けてトップ1%になる — 54日目

この問題は、各ノードに値を持つn個のノードからなるツリーから2つのエッジを削除した後に最小スコアを見つけることです。目標は、エッジを切断した後に形成される3つの別々のツリーの最大XOR値と最小XOR値の差を最小化することです。総当たりアプローチでは、すべての可能なエッジのペアを試すことになりますが、これはO(n³)の計算時間になります。より最適化された戦略は、隣接リストを使用してツリーを構築し、ルートからの深さ優先探索（DFS）を実行して、各ノードのサブツリーXORを計算し、どのノードが各ノードのサブツリーに属するかを追跡することです。次に、すべてのノードのペアを反復処理し、3つのXOR部分を計算してスコアを評価します。見つかった最小スコアが返されます。Pythonでのコード実装では、defaultdictを使用してグラフを構築し、DFS関数を使用してサブツリーXORと子孫を計算します。ソリューションの時間計算量と空間計算量はO(n²)です。この問題から得られる重要な教訓は、XORとツリーDPの使用、および問題の要件を理解することの重要性です。著者は、この問題を解決した経験を振り返り、助けが必要であり、最初はソリューションを完全に理解していなかったことを認めています。