\(dfn\)序的长度是欧拉序的一半，常数较小，并且代码便于理解背诵。
让欧拉序求lca成为时代的眼泪。
代码部分实现思路来自cqbz_dongjie
点击查看代码
auto minlca = [&](int x, int y) {
return (dfn[x] < dfn[y])? x : y;
};
int t = std::__lg(n) + 1;
std::vector <std::vector<int> > st(t + 1);
for (int i = 0; i <= t; i++) st[i].resize(n + 1);
for (int i = 1; i <= n; i++) st[0][dfn[i]] = fa[i];
for (int j = 1; j <= t; j++) {
for (int i = 1; i <= n; i++) {
st[j][i] = minlca(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}
}
auto lca = [&](int x, int y) {
if (x == y) return x;
if (dfn[x] > dfn[y]) std::swap(x, y);
int lg = std::__lg(dfn[y] - dfn[x]);
return minlca(st[lg][dfn[x] + 1], st[lg][dfn[y] - (1 << lg) + 1]);
};