algorithm - Lowest Common Ancestor (LCA) アルゴリズムに関する不明確な理解

Question

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

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

int n, l; 

vector <vector <int>> g;

vector <int> tin, tout;

int timer;

vector <vector <int>> up;

void dfs (int v, int p = 0) 
{
  tin [v] = ++ timer;
  up [v] [0] = p;
  for (int i = 1; i <= l; i ++)               /** 3)What is this going
     up [v] [i] = up [up [v] [i-1]] [i-1];

  for (i = 0 size_t; i <g [v] .size (); i ++) 
   {
      to g = int [v] [i];
        if (to! = p)
           dfs (to, v);
   }
   tout [v] = ++ timer;
 }

bool upper (int a, int b) 
{
  return tin [a] <= tin [b] && tout [a]> = tout [b];
}

int lca (int a, int b) 
{
  if (upper (a, b)) return a;
  if (upper (b, a)) return b;

  for (int i = l; i> = 0; --i)              /** 2)What is this going
    if (! upper (up [a] [i], b))
        a = up [a] [i];

  return up [a] [0];

}

int main () {

... Read n and g ...

tin.resize (n), tout.resize (n), up.resize (n);
l = 1;                                    
                                      /** 0)What is 'l' used for ?
while ((1 << l) <= n) ++ l;           /** 1)What is this going
for (int i = 0; i <n; i ++) 
  up [i] .resize (l + 1);
dfs (0);

for (;;) //->query loop
  {
    int a, b; // The current query
    int res = lca (a, b); // Response to a request
  }

}

私が理解したこと

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

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

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

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

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

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

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