526互联

模板 最近公共祖先（LCA）

发布时间 2023-07-31 02:32:40作者: wuyoudexian
void dfs(int u, int v) {//求出每个结点的深度1
	dep[u] = dep[p] + 1;
    fa[u][0] = p;
    for(int i = 1; (1 << i) <= dep[u]; i++) {
    	fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    for(int v : adj[u]) {
    	if(v == p) continue;
    	dfs(v, u);
    }
}

int lca(int u, int v) {//求出lca
	if(dep[u] < dep[v]) swap(u, v);
	for(int i = 19; i >= 0; i--) {//i的初始值由节点数确定
		if(dep[u] - (1 << i) >= dep[v]) {
			u = fa[u][i];
		}
	}
	if(u == v) return u;
	for(int i = 19; i >= 0; i--) {
		if(fa[u][i] != fa[v][i]) {
			u = fa[u][i];
			v = fa[v][i];
		}
	}
	return fa[u][0]; 
}