74
правки
Изменения
Нет описания правки
Предположим, что нашли предка, который не является наименьшим, тогда это нас моментально приводит к противоречию, потому что запросмы должны были рассмотреть ранее {{---}} на минимальном предке.
Если он не минимальный, значит, есть на какой-то большей глубине, то есть такая вершина, которая была посещена раньше и для которой условия на <tex>u</tex> и <tex>v</tex< выполнялись, значит, тогда должна была найтись эта вершина в качестве <tex>LCA</tex>.
[[file:mytree.png|500px|разные цвета {{---}} разные классы, а белые вершины ещё не просмотренные в dfs]]
=== Реализация ===
vector <int> query[n];
int dsu_get (int v) {
return v == dsu[v] ? v : dsu[v] = dsu_get (dsu[v]);
unite (int a, int b, int new_ancestor) {
a = dsu_get (a);
b = dsu_get (b);
dsu[a] = b;
ancestor[b] = new_ancestor;
dfs(int v) {
visited[v] = true;
for (u таких, что (v, u) — ребро в G)
if (visited[query[v][i]])
cout << "LCA " << v << " " << u << " = " << ancestor[dsu_get(q[v][i])];
int main() {
dfs(1); // можно запускать от любой вершины
=== Оценка сложности ===
