2

ツリーが与えられた場合、「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 はオプションではありません。

4

1 に答える 1

2

最も低い共通祖先を実行し、すべてのノードの深さ (ルートまでの距離) を維持します。

次に、k 番目のノードが a から lca または lca から b の部分にあるかどうかを調べます。深さの違いはそれらの間のノードの数であるためdepth[a] - depth[lca] > k、ノードが lca-b 部分にある場合。

ノードが a から lca の部分にある場合は、a の k 番目の祖先を見つけます。事前に計算した LCA データを使用して log(N) にする必要があります。

ノードが b から lca の部分にある場合、b から k 番目のノードまでの距離である k' を計算し ( k' = 1 + depth[a] + depth[b] - 2*depth[lca] - k))、b の祖先 k' を取得できます (これも LCA データを使用すると簡単です)。

全体として、すべてのルックアップは logN であり、他のステップは一定であるため、クエリごとに O(LogN) を実行します。

于 2016-01-25T15:45:09.450 に答える