74
правки
Изменения
Нет описания правки
После того как мы обработали всех детей вершины <tex>v</tex>, мы можем ответить на все запросы вида <tex>\langle v, u \rangle </tex>, где <tex>u</tex> {{---}} уже посещённая вершина.
Нетрудно заметить, что ответ для <tex>lca \langle v, u \rangle = ancestor[find(u)]</tex>.Так же можно понять что для Для каждого запроса это условие (что одна вершина уже посещена, а другую мы обрабатываем) выполнится только один раз.
Предположим, что нашли предка, который не является наименьшим, тогда это нас моментально приводит к противоречию, потому что запросмы должны были рассмотреть ранее {{---}} на минимальном предке.
'''for''' i = 0 '''to''' query[v].size - 1
'''if''' visited[query[v][i]]
запомнить, что ответ для запроса (\langle v,u) /rangle = ancestor[dsuGet[q[v][i]]]
== Оценка сложности ==
