根付き重み付きツリーで、各ノードから特定の距離内にあるノードの数をどのように見つけることができますか? ルートから下に行くノードなど、ダウン エッジのみを考慮する必要があります。各エッジには重みがあることに注意してください。
O(N^2)各ノードから DFS を使用して移動距離を追跡することで、時間内にこれを行うことができますがN >= 100000、少し時間がかかります。DP を使用した重み付けされていないエッジで簡単に解決できると確信していますが、これをすばやく解決する方法を知っている人はいますか? (未満N^2)
次の観察を利用することで、O(nlog d) 時間と O(n) 空間に対する以前の回答を改善することができます。
特定のノード v での十分に近いノードの数は、その子のそれぞれの十分に近いノードの数の合計から、不十分に近いノードの数を差し引いたものです。
距離のしきい値を m と呼び、隣接する 2 つのノード間のエッジ上の距離を u と vd(u, v) と呼びましょう。
各ノード v に対して、最初は 0 であるカウント c(v) を維持します。
任意のノード v について、v の親からルートまでの祖先のチェーンを考えます。このチェーンの i 番目のノードを a(v, i) と呼びます。v は、このチェーンの最初のノードのいくつかの i >= 0 で十分に近いものとしてカウントされる必要があり、他のノードではカウントされないことに注意してください。i をすばやく見つけることができれば、単純にc(a(v, i+1)) を減らすことができます ( 0よりも (おそらくさらに) 小さくすることができます)。したがって、a(v, i+1) のカウントがの子は後のパスでそれに追加され、 v はカウントから正しく除外されます。c(v) にノード v を追加する前に、ノード v のすべての子の完全に正確なカウントを計算すると、そのような除外は親カウントに正しく「伝播」されます。
トリッキーな部分は、 i を効率的に見つけることです。v からルート s(v, j) までのパス上の最初の j >= 0 エッジの距離の合計を呼び出し、昇順でリストされたこれらのパスの長さのすべての depth(v)+1 のリストを呼び出します。 、s(v)。やりたいことは、パスの長さ s(v) のリストをバイナリ検索して、しきい値 m より大きい最初のエントリを見つけることです。これにより、log(d) 時間で i+1 が見つかります。問題は s(v) の構築です。v からルートまでの現在の合計を使用して簡単に構築できますが、それにはノードごとに O(d) の時間が必要であり、時間の改善が無効になります。一定時間で s(parent(v)) から s(v) を構築する方法が必要ですが、問題は、ノード v からその子 u に再帰すると、パスの長さが「間違った方法」で増加することです。パスの長さ x は x + d(u, v) になる必要があります。また、最初に新しいパスの長さ 0 を追加する必要があります。これには O(d) 更新が必要なようですが、トリックで問題を回避できます...
解決策は、各ノード v で、v からルートまでのパス上のすべてのエッジの合計パス長 t(v) を計算することです。これは、ノードごとに一定の時間で簡単に実行できます: t(v) = t(parent(v)) + d(v, parent(v))。次に、s(parent(v)) の先頭に -t を追加して s(v) を形成できます。二分探索を実行するときは、各要素 s(v, j) が s(v, j) + t を表すと見なします。 (または同等に、m の代わりに m - t のバイナリ検索)。開始時の -t の挿入は、ノード v の子 u に v のパス長配列を共有させ、s(u) を s(v) の 1 つ前のメモリ位置から開始すると見なすことにより、O(1) 時間で実現できます。すべてのパス長配列は、サイズ d+1 の単一メモリ バッファ内で「右詰め」されます。具体的には、深さ k のノードは、そのパス長配列がバッファ内のオフセット dk から始まるようにして、子孫ノードがエントリを先頭に追加できるようにします。配列の共有は、兄弟ノードが互いのパスの長さを上書きすることを意味しますが、これは問題ではありません。v と v の子孫が preorder DFS で処理されている間、s(v) の値だけが有効なままである必要があります。
このようにして、O(1) 時間で O(d) パス長が増加する効果が得られます。したがって、特定のノードで i を見つけるのに必要な合計時間は、O(1) (s(v) を構築するため) と O(log d) (修正二分探索を使用して i を見つけるため) = O(log d) です。1 つの事前注文 DFS パスを使用して、各ノードの適切な祖先の数を見つけてデクリメントします。ポストオーダー DFS パスは、子の数を親の数に合計します。これらの 2 つのパスは、再帰の前後の両方で操作を実行するノード上の 1 つのパスに組み合わせることができます。
[編集:さらに効率的な O(nlog d) ソリューションについては、私の他の回答を参照してください:)]
これは単純な O(nd) 時間、O(n) 空間のアルゴリズムです。ここで、d はツリー内の任意のノードの最大深度です。n 個のノードを持つ完全なツリー (すべてのノードが同じ数の子を持つツリー) の深さは d = O(log n) であるため、ほとんどの場合、O(n^2) DFS ベースのアプローチよりもはるかに高速です。ただし、ノードごとの十分に近い子孫の数が少ない場合 (つまり、DFS が少数のレベルのみをトラバースする場合)、アルゴリズムも悪くないはずです。
任意のノード v について、v の親からルートまでの祖先のチェーンを考えます。v は、このチェーンの最初のノードのいくつかの i >= 0 で十分に近いものとしてカウントされる必要があり、他のノードではカウントされないことに注意してください。したがって、必要なことは、ノードごとに、パスの合計の長さがしきい値の距離 m を超えるまでルートに向かって上に登り、進むにつれて各祖先のカウントをインクリメントすることだけです。 n 個のノードがあり、各ノードには最大で d 個の祖先があるため、このアルゴリズムは自明に O(nd) です。