LCA

dfsdfs:

  1. 现在的节点的上面一个节点是它的父亲,节点的深度是他父亲的深度+1+1

  2. 预处理,这个节点的2n2^n个祖先。

    for (int i = 1; i <= lg[depth[now]]; ++i)
            fa[now][i] = fa[fa[now][i-1]][i-1];
    
  3. 递归遍历图。

LCA(x,y)LCA(x,y):

  1. 如果 xx 的深度比 yy 浅,就交换,确保 xxyy 深。

  2. xx 一直跳到和 yy 深度相同的时候。

while(depth[x] > depth[y])
        x=fa[x][lg[depth[x]-depth[y]]-1];
  1. 如果 xxyy 是同一个节点,就直接 returnreturn

  2. 能跳就跳。

    for(int k = lg[depth[x]] - 1; k >= 0; --k)
    		if(fa[x][k] != fa[y][k])
    			x = fa[x][k], y = fa[y][k];
    
  3. return fa[x][0]return\ fa[x][0]