Неясное понимание алгоритма самого низкого общего предка (LCA)

Question

Я пытался выучить алгоритм LCA O(nlog n) и предварительную обработку O(log n). Я читаю его с русского сайта с помощью google translate. Но он плохо переводится, и мне трудно понять его Кто-нибудь может мне помочь с этим?

Это псевдокод, который я взял с этого сайта

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 и аналогично второй шаг.

То, что я не понимаю, упоминается мной в псевдокоде. Пожалуйста, помогите мне и подтвердите, все ли я правильно понял или нет.

PS-> Извините за мой английский. Не очень удобно с этим.