はじめに
ツリーは、 N個の頂点とN-1個のエッジの無向接続グラフです。 頂点から他の頂点まで、1つの単純なパスがあります。
ツリーのルートは、そのような頂点と呼ばれます。この頂点から、ツリーが移動するときに、ツリーに沿った移動方向が設定されます。
2つの頂点uとvの最小の共通の祖先は、ルートから頂点v 、頂点uまでのパス上にある頂点pと呼ばれます。
入力データ
ツリーに関する情報が入力に到着します。N-頂点の数、エッジで接続されたN-1組の頂点、およびM-リクエストの数。 次に、プログラムは、2つの頂点uとvの要求を受け取ります。これらの頂点では、最も一般的な祖先を見つける必要があります。
アルゴリズムのアイデア
各頂点について、ルートまでの距離と、そこに到達した元の頂点（祖先）を保存します。 次に、頂点uとvから木の根まで登ります。 各ステップで、ルートから最も遠い頂点uまたはvを選択し、最初のuおよびvから形成されたパスが1つの頂点（最も一般的な祖先）に至るまで、代わりにその祖先を検討します。 さまざまなツリーオプションを使用すると、このようなパスはN個のステップで構成され、多数の頂点とクエリを使用すると動作が遅くなります。 この実装では、各リクエストを完了するのにO（N）時間かかります。
次に、アルゴリズムを改善します。 各頂点について、 distツリーのルートまでの距離、その子の子の数、先祖（選択は下で決定されます）、 最後に来た先、および頂点がこの頂点ターンに向かう先祖からの頂点の数を保存します 。
必要な変数を宣言します。便宜上、これはグローバルメモリで行われます。
const int SIZE = 100050; vector<int> v[SIZE]; // bool vis[SIZE]; // int kids[SIZE]; // - int dist[SIZE]; // int last[SIZE]; // int turn[SIZE];
次に、各頂点について、再帰関数（ k_go（0）を呼び出す）を使用して、その子孫の数を計算します。
int k_go(int s) { int res = 0; vis[s] = true; for(int i = 0, maxi = v[s].size(); i < maxi; i++) { if(!vis[v[s][i]]) res += k_go(v[s][i]) + 1; } kids[s] = res; return res; }
そして、アルゴリズムの準備部分を終了し、各頂点に必要な情報を入力します。 関数l_go（0、0、0、1）を呼び出します ：
void l_go(int s, int d, int l, int r) { vis[s] = true; dist[s] = d; last[s] = l; turn[s] = r; int maxval = 0; int idx = -1; for(int i = 0, maxi = v[s].size(); i < maxi; i++) { if(!vis[v[s][i]]) { int k = kids[v[s][i]]; if(k > maxval) idx = v[s][i], maxval = k; } } for(int i = 0, maxi = v[s].size(); i < maxi; i++) { if(!vis[v[s][i]]) { if(idx == v[s][i]) l_go(v[s][i], d + 1, l, r); else l_go(v[s][i], d + 1, s, v[s][i]); } } }
ここで、頂点の子の数を見つけることは非常に一般的なタスクであるため、コードの最後の部分がどのように機能するかを説明します。
各頂点について、その子孫を見て、そこから子孫の最大数を持つ頂点を選択します。 彼女にとって、祖先に関するすべての情報は現在の情報から継承され、ルートまでの距離のみが変更されます。 この頂点の他のすべての子孫では、現在の頂点がlastの祖先になり、子孫自体がturnになります。
ここで、ツリー内の頂点aを取得し、そこからルートに到達するまで、 最後の祖先への遷移の数はツリー内の頂点の数の2進対数を超えないと主張します。
証明：子孫が1つある頂点vに移動します。 それから、そこから出る子孫が祖先への最後のリンクを変更しないことは明らかです。 2つ以上の頂点の場合、1つの子孫（現在の頂点のすべての子孫のうち、子孫の数が最も多い子孫）が取得されます。 現在の頂点の子孫の総数をNで示します。 次に、先祖へのリンクを更新するこの頂点の子孫から、 N / 2以下の子孫が存在します（そうでない場合、この数は最大になりますが、リンクの更新は必要ありません）。 したがって、 最後の祖先である各頂点には、そこから来るすべての子孫から、頂点の半分以下しか残っていません。 そのようなパスの全長は、 Nの 2進対数を超えません。
それでは、アルゴリズムの主な機能に移り、なぜ機能するのかを説明しましょう。
したがって、2つの頂点uとvがあり 、そのために要求に対する答えを見つける必要があります。 関数p = lca（u、v）を呼び出します。
int lca(int a, int b) { if(turn[a] == turn[b]) { if(dist[a] < dist[b]) return a; else return b; } if(dist[last[a]] > dist[last[b]]) return lca(last[a], b); return lca(last[b], a); }
関数は、ルート方向に再帰的に上昇します。 後続の各頂点aおよびbについて、最初に最後の回転が行われた頂点をチェックします。 一致する場合、これは、頂点aがルートから頂点bへのパス上にある、またはその逆であることを意味します。 どの頂点がルートに近いかに応じて、それが望ましい最小共通祖先です。
そうでない場合は、頂点aまたはbをルートに近づける必要があります。 祖先への遷移の場合、ルートからさらに遠いものに基づいて概算します（1つの頂点がルートへの途中で2番目のピークに追いつきます）。 したがって、遅かれ早かれ、頂点は1つの頂点に到達します。頂点はすぐに最小の共通祖先になるか、頂点の1つがルートから別の頂点へのパス上にあります（最初のステップで説明します）。
アルゴリズムの評価
アルゴリズムを実装するには、すべてのリクエストに応答するためにO（N）メモリ（合計6Nのメモリが消費される）、 O（N）予備計算、およびO（M *ログ（N））時間が必要です。
このアルゴリズムを使用すると、事前に定義されたツリー上の要求に応答し、それぞれがO（ログ（N））に到着するとすぐに要求に応答できます。
LCA検索問題を解決するための他のアルゴリズムの有効性
この問題を解決するためのアルゴリズムがいくつかあり、それぞれが書き込みの複雑さ、予備計算の時間、要求への応答、必要なメモリのサイズが異なります。
1） O（log N）の要求に対する応答、O（N）の予備計算。 実装の複雑さは、データ構造「セグメントのツリー」または「sqrt-decomposition」を使用する必要があることです。
2） バイナリリフト法 。 O（log N）の要求に対する応答、O（log N）の予備計算、使用済みメモリ（N * log（N））。 私が引用したアルゴリズムよりも実行時間がわずかに優れたかなり単純な実装ですが、追加のメモリが使用されます。
3） Farah-Colton and Benderアルゴリズム 。 これは最適なアルゴリズムであり、O（1）の要求に応答できますが、大量の追加メモリが必要であり、実装が困難です。
O（1）のリクエストに応答できるアルゴリズムと同様に、このためには、すべてのリクエストに関する情報を事前に知る必要があります。
4） Tarjanアルゴリズム
おわりに
したがって、実装の複雑さで示されているアルゴリズムは、わずかに高速なバイナリリフトアルゴリズムよりも若干劣りますが、予備計算に必要なメモリと時間は少なくなります。 この使用法の妥当性と一意性を評価するために、この問題を解決するためのアルゴリズムに精通している人々の意見を聞きたいと思います。 この記事を理解するために時間を割いてくれた皆さんに感謝します。
UPD：知識のある人は、私のアルゴリズムは、 Heavy-Light分解のアプリケーションの1つにすぎないと言っていました。 それ以前は、この分解に慣れていませんでしたが、いずれにしても、たとえそれが存在していても、自分で何かを考え出すのは素晴らしいことです。