LCA
2025-04-05 11:26:59
发布于：广东
17阅读
0回复
0点赞
void dfs(int idx, int pre){
father[idx] = pre;
dep[idx] = dep[pre] + 1;
for(int i:v[idx]){
if(i == pre) continue;
dfs(i, idx);
}
}
void init(){
dfs(k, 0);
father[k] = k;
for(int i = 1; i <= n; i++){
ST[0][i] = father[i];
}
for(int i = 1; i <= 20; i++){
for(int j = 1; j <= n; j++){
ST[i][j] = ST[i - 1][ST[i - 1][j]];
}
}
}
int lca(int x, int y){
if(dep[x] < dep[y]) swap(x, y);
int diff = dep[x] - dep[y];
for(int i = 0; i <= 20; i++){
if(diff >> i & 1) x = ST[i][x];
}
if(x == y) return x;
for(int i = 20; i >= 0; i--){
if(ST[i][x] != ST[i][y]) x = ST[i][x], y = ST[i][y];
}
return father[x];
}
这里空空如也
有帮助，赞一个