問題タブ [lowest-common-ancestor]

LCA アルゴリズムの O(nlog n) 前処理と O(log n) クエリを学習しようとしていました。Google翻訳の助けを借りてロシアのサイトから読んでいます。しかし、翻訳がうまくいかず、理解するのに苦労しています。 .誰でもこれで私を助けることができますか?

これは、そのWebサイトから取得した疑似コードです

私が理解したこと

• グラフをトラバースし、すべての頂点のインタイムとアウトタイムを保存していることはわかっています。

• 頂点up[i][j]の2^j祖先です。i

• 理由はわかりましたup[v][0]=p（2^0つまり、頂点の最初の祖先vはその父のみであるため）

• A上の関数が何をするのか理解できました.またはの前にどの頂点が発生したかを決定しBます.

• 私はアッパー(a,b)がLCAよりも真であることを理解してAおり、同様に2番目のステップです。

理解できないことは、疑似コードで私が言及しています。助けてください。すべてが正しいかどうかを理解したかどうかを確認してください。

PS->私の英語で申し訳ありません。これにはあまり慣れていません。

この親子階層があるとしましょう:

そのような階層で最も低い共通の祖先を見つける方法を実装するClojureのイディオムは何ですか? すなわち:

私の最初の考えには、各引数の組み合わせをトラバースする再帰関数の使用が含まれますparentsが、おそらくもっと良いアプローチがあると思います。

私の動機は、2 つの引数を取り、引数の型に基づいて最適な実装にディスパッチする multimethod のディスパッチ関数としてこれを使用することです。

ツリーが与えられた場合、「a」から「b」へのパスで「k」番目のノードを見つける必要があります。つまり、ノード「a」からノード「b」へのパスの「k 番目」の位置にあるノードを見つける必要があります。私は最低共通祖先および/または重軽分解の行で考えていましたが、それがそれを行う方法であるかどうかはわかりません。正しい方向へのガイダンスをいただければ幸いです。

詳細：

• ツリーは二分木ではありません。これは、n-1 個のエッジ、n 個の頂点を持ち、サイクルを持たない無向グラフです。ちょうどあなたの通常の木
• ツリーには、1 から n までの番号が付けられた頂点があります。これらの頂点の n-1 ペアを接続する n-1 個の無向辺があります
• 「a」と「b」は、ツリー内で 1 から n までの番号が付けられた任意の 2 つの頂点です。「a」から「b」へのパスで「k」番目のノードを見つけます。'k' の値が <= 'a' から 'b' へのパス内のノード数であることが保証されています

クエリの数が多いため、すべてのクエリ (「a」から「b」までの k 番目のノード) に適用される BFS はオプションではありません。

この問題は、最下位共通祖先の概念に基づいています。
ツリー内のノードのペア間のパスの最短エッジと最長エッジの長さを見つける必要があります。
問題へのリンクは次のとおりです: SPOJ DISQUERY