Анализ на задача testove

Първо ще разгледаме как ефективно да генерираме дървета:

1. Образуване на дървета от граф:
Реално най-оптималните начини са два: 
а) Със сложност O(NТ)
Идеята е да измислим или да използваме някой алгоритъм, който генерира случаен граф за сложност O(N+M). След това лесно можем да си направим DSU и да направим дърво.
Тази стъпка повтаряме, докато не генерираме T различни дървета. Може да използваме set за да си осигурим уникалността на дърветата.
б) Със сложност O(N^2 * Т) 
Идеята е да построим пълен граф (всеки връх да има пряко ребро с всеки дург връх) и да направим дърво, поддържайки го с DSU. Това го повтаряме T пъти. За да избегнем повторения, може на всяка стъпка 
да разбъркваме пълния граф.
Забележка - възможно е решението с пълния граф да се сведе до O(NT), но трябва да се рандомизира добре взимането на ребрата от пълния граф.

2. Образуване на дървета директно
Най-оптималното решение би изглеждало така:
Създаваме масив par, в който за всяко i, par[i] е родителя на i в текущото дърво. Как да генерираме par, така че да си гарантираме дърво? Това би станало, ако за всяко i,
par[i]<=i-1.Това интуитивно би било гарантирало дърво, защото според условието, дърветата трябва да се коренуват от 1. Тоест за всяко i, родителя би бил с по-малък номер,
следователно родителят му се намира по-нагоре в дървото.

Сега нека разгледаме как да намерим височината на дърво:

Най-оптималното решение (О(N)):
В авторските решения ще видитe начини с bfs и dfs. Реално идеята с bfs е просто в опашката освен да поддържате следващия връх за обикаляне, но и през колко ребра сме минали до този връх.
Идеята с dfs е като аргумент да си пазим текущата височина и да я увеличаваме.
Така като стигнем до връх без излизащи ребра (тоест листо) спираме и променяме максимума, ако е нужно.

Сега нека видим как можем да отговаряме на заявки:

Най-оптимално решение O(QlogT):
Това го извършваме със сегментно дърво с update върху височините на генерираните дървета.

Оптимални решения без update (QlogN), (Qsqrt(N))
Можем пак да използваме сегментно дърво без ъпдейти , но също така и със спарс таблици.

Така общата ни сложност става O(NT + Q log T).


Идея, условие, анализ, решения: Кирил Зашев
Решения: Димитър Шапатов