@[2022_37_yzyUUU](/user/785636)
LCA 要用倍增跳
by szh_AK_all @ 2024-04-13 09:38:12
@[szh_AK_all](/user/939431) 能具体说一下吗？
by 2022_37_yzyUUU @ 2024-04-13 09:42:37
@[2022_37_yzyUUU](/user/785636)
这个其实是个板子。
用 f[x][i] 记录 x 向上 $2_i$ 步的父亲，那么有 f[x][i]=f[f[x][i-1]][i-1].
然后跳 LCA 的时候不断倍增跳就行，一次跳一步很慢。
```cpp
记录父亲
fa[x][0] = f;
de[x] = de[f] + 1;
for (int i = 1; i <= 25; i++)
fa[x][i] = fa[fa[x][i - 1]][i - 1];
.....
跳 LCA
int lca(int x, int y) {
if (de[x] < de[y])
swap(x, y);
for (int i = 25; i >= 0; i--)
if (de[fa[x][i]] >= de[y])
x = fa[x][i];
if (x == y)
return x;
for (int i = 25; i >= 0; i--)
if (fa[x][i] != fa[y][i])
x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
```
by szh_AK_all @ 2024-04-13 09:45:14
@[szh_AK_all](/user/939431) 万分感谢
by 2022_37_yzyUUU @ 2024-04-13 09:48:05
智瑶nb
by ask666UU @ 2024-04-13 09:54:22
智瑶nb
by 0xllllllllllf @ 2024-04-13 09:58:10
智瑶nb
by zhuxiangruicn @ 2024-04-18 18:19:36