algorithm - ツリー内のノードのすべてのペア間の距離

Question

与えられた木。サイズ n*n の 2D 行列を使用せずに、ツリー内のノードのすべてのペア間の距離を見つける方法。私は O(n^2) 複雑さの解を知っています。

Answer 1

distance(u, v)高速な前処理でフォームのクエリに十分に速く応答できるようにしたい場合は、 LCAを使用できます。根付きツリーの 2 つの頂点の LCA (最小共通祖先) は、それらの両方の祖先であり、すべての共通祖先の中で最も低い頂点です。前処理時間LCA(u, v)で対数時間で見つけるためのそれほど複雑ではないアルゴリズムがあります。n log n必要に応じて説明できます。

したがって、問題は次のように解決される場合があります。まず、ツリーのルートを修正します。次に、LCAを見つけることができるように、上記の前処理を行います。h[v]次に、が からルートまでの距離であると仮定しvます (すべての頂点について線形時間で事前計算できます) distance(u, v) = h[u] + h[v] - 2 * h[LCA(u, v)]。