0

我试图学习 LCA 算法O(nlog n) 预处理和 O(log n) 查询。我在谷歌翻译的帮助下从一个俄罗斯网站阅读它。但它翻译得不好，我很难理解它. 有人可以帮我吗？

这是我从该网站获取的伪代码

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->对不起我的英语。对此不太满意。

4

0 回答 0