树上倍增

豪用

求第Y个祖先

N个节点的树，M次询问第X个节点的第Y个祖先

n, m <= 1e4

f[x][2] = f[f[x][1]][1], f[x][y + y] = f[f[x][y]][y]

定义数组F[x][y] = f[x][

2 ^ y

] 。

节点祖先的性质，易得F[x][y + 1] = F[F[x][y]][y]

从小到大枚举y，求出一切节点的F[x][y]，如此往复，通过已知的F[x][y]求出F[x][y + 1]。

y 的上界：O(

long _ n

)，因此预处理O(n *

log_n

)

模版

CPP

void init(){
	for(int i = 1 ; i <= n ; i ++)
		F[i][0] = fa[i];
	for(int i = 1 ; i <= 20; i ++)
		for(int j = 1 ; j <= n ; j ++){
			if(F[j][i - 1] > 0 && F[F[j][j - 1]][j - 1] > 0)
				F[j][i] = F[F[j][i - 1]][i - 1];
		}
}

int f(int x, int n){
	for(int i = 20; i >= 0;; i --){
		if(n >= (1 << i)){
			n -= (1 << i);
			x = F[x][i];
		}
	}
	return x;
}

求LCA

倍增求F[x][k]，代表节点x的第

2^k

个祖先。

树上倍增

文章操作

树上倍增

豪用

求第Y个祖先

模版

求LCA

相关推荐

评论

树上倍增