Ламінарія#12965

Ламінарія (Розбір)

З’єднувати можливо тільки вершини однакового кольору, інакше неможливо зробити першу операцію.

Розглянемо таку інтерпретацію процесу з умови: назвемо спершу великою вершиною – вершину, яка з’єднує обидва дерева. Далі за кожну операцію будемо об’єднувати велику вершину з певною вершиною , якщо в обох деревах існує ребро між великою вершиною і вершиною . Усі ребра, які виходили зі старих вершин, тепер будуть виходити з нової великої вершини.

Зробимо схожий процес: поки у двох деревах є однакове ребро, об’єднаємо в обох деревах ці вершини в одну вершину. Якщо такий процес не об’єднав усі вершини в кожному з дерев в одну, то відповідь 0, адже в одну велику вершину теж не вийде об’єднати. Такий процес не залежить від початкової великої вершини, тож його можна зробити один раз.

Щоб реалізувати цей процес будемо підтримувати усі інцидентні ребра для вершини в списку та з’єднувати ребра від вершини з меншим степенем до вершини з більшим степенем. Складність такого алгоритму буде O(n \log^2 n), оскільки нам ще також потрібно використати set чи схожу структуру даних, щоб підтримувати, які ребра збігаються в обох деревах.

Подивимось, коли ми об’єднували вершини та , які ребра відповідають цьому об’єднанню в оригінальних деревах. Нехай це (u_1, v_1) в першому дереві та (u_2, v_2) в другому. Якщо u_1 \ne u_2, то якщо велика вершина спершу об’єднала вершини v_1 чи v_2, то ми не зможемо об’єднати також u_1 і u_2. Аналогічно, якщо v_1 \ne v_2. Тож якщо u_1 = u_2, додамо в додатковий граф напрямлені ребра v_1 \to u_1, v_2 \to u_1. Це означає, що якщо ми об’єднали в велику вершину вершини з , то зможемо об’єднати також вершини з . Аналогічно додамо напрямлені ребра, якщо v_1=v_2. Тоді відповідь – це кількість вершин, з яких досяжні всі інші вершини в додатковому графі. Таке значення можна знайти, якщо зробити топологічне сортування, або також існують простіші методи, які враховують специфічну структуру додаткового графа.