对倍增求LCA的理解

\(updata : 2021.11.22\) 复习 \(LCA\) , 才发现对 \(LCA\) 并不理解.

\(① :\) \(倍增数组的构建\)

易想到 : bz[i][j] = bz[bz[i][j-1]][j-1] .

那枚举顺序呢? 我复习时想到的是先枚举点 \(i\) , 在枚举到 \(2\) 的倍数 \(j\) , 这样 bz[i][j-1] 必然是 \(i\) 的祖先 , 那么考虑到 \(DP\) 更新顺序 , 可以考虑 \(dfs\) 遍历顺序更新.

void dfs1(int x,int f){
	for(int k=head[x];k;k=len[k].next){
		int to = len[k].to;
		if(to != f){
			for(int j=1;j<=19;++j)
				bz[to][j] = bz[bz[to][j-1]][j-1];
			dfs1(to , x);
		}
	}
}

看了一下 \(std\) , 发现先枚举 \(j\) , 再枚举 \(i\) 即可.

for(int j=1;j<=19;++j)
		for(int i=1;i<=n;++i)
			bz[i][j] = bz[bz[i][j-1]][j-1];

\(② :\) 倍增跳到相同的高度

先看代码:

	for(int j=19;j>=0;--j)
			if(dep[ bz[x][j] ] >= dep[y])
				x = bz[x][j];

包括后面的倍增跳 \(LCA\) , 我都认为了都利用了"数的二进制拆分"的思想 , 有如下子问题:

"如何将 t 二进制数的各位位置找出来?"

其实我们从 \(2^n\) ( \(n\) 是一个足够的数 , \(2^n > t\) ) , \(n\)自减 , \(t\) 能减 \(2^n\) 就减 , 此时 \(n\) 必是一个位置.

注意一定是高位从低位枚举 , 而不是从低位枚举到高位.

同理就会明白倍增数组为什么从高位枚举.

\(③ :\) 倍增跳 \(LCA\) , 同理 \(②\) .

\(④ :\) 为什么是答案是 \(fa[x]\)

举个例子 ： 如果二者的 \(2^n\) 辈相同时( \(LCA\) ) , 并不赋值 x = bz[x][n] , 而将 \(2^n\) 再二进制拆解 , 最后 \(2^n\) 不断变小 , \(n\) 必最后为 \(0\) .为什么不发现 \(LCA\) 就直接停止呢? 因为 \(n\) 从高位枚举 , 到 \(LCA\) 之前的 \(2^n\) 辈都相同 , 怎么会知道哪点是 \(LCA\) , 所以有 while(bz[x][j] != bz[y][j]) x = bz[x][j] , y = bz[y][j]; ,只有不等才改.