Изменения
Нет описания правки
Нетрудно заметить что ответ для lca(v,u) = ancestor(find(u)).Так же можно понять что для каждого запроса это условие(что одна вершина уже посещена, а другую мы обрабатываем) выполнится только один раз.
=== Реализация ===<tex>
vector<bool> visited;
vector<int> query[n];
int dsu_get (int v) {
return v == dsu[v] ? v : dsu[v] = dsu_get (dsu[v]);
}
void unite (int a, int b,int new_ancestor) {
a = dsu_get (a);
b = dsu_get (b);
dsu[a] = b;
ancestor[b] = new_ancestor;
}
void dfs(int v) {
visited[v] = true;
}
dfs(0);
return 0;
}
=== Оценка сложности ===
Она состоит из нескольких оценок.
Во-первых dfs работает О(n).
Во-вторых, операции по объединению множеств, которые в сумме для всех разумных n затрачивают O(n) операций.
В-третьих, для каждого запроса проверка условия и определение результата, опять же, для всех разумных n выполняется за O(1). Итоговая асимптотика получается O(n+m), но при достаточно больших m ответ за O(1) на один запрос.
