OldPost --- NewPost#379

OldPost --- NewPost (Розбір)

Автор задачі:

Костянтин Денисов

Задачу підготував:

Данило Квіт

Розбір написав:

Костянтин Денисов

Формально кажучи, в задачі треба було знайти два діаметри на дереві, що перетинаються по найменшій кількості вершин.

Розберемося, як можна просто працювати з діаметрами на дереві. Не порушуючи загальності, припустимо, що шлях між вершинами та — діаметр. Зобразимо наше дерево так, ніби воно "підвішене" за цей шлях. Як тоді можна представити інші діаметри?

Для кожної вершини діаметра подивимось на піддерева сусідніх вершин, що не належать діаметру. Випишемо, яка максимальна можлива відстань від вершини до вершин в цих піддеревах. Якщо v_1, v_2, ..., v_l — вершини діаметра в порядку обходу, то максимальна відстань в цих піддеревах для вершини v_i буде \min(i-1, n-i). Позначимо зеленим вершини в піддеревах, на яких відповідний максимум досягається.

Твердження 1. Розділимо наші вершини на три частини (у випадку діаметра парної довжини на дві частини). Групи:

  1. Вершини, що знаходяться у піддеревах вершин v_1, v_2, ..., v_{\lfloor \frac{l}{2} \rfloor};

  2. Вершини, що знаходяться у піддеревах вершин v_{\lfloor \frac{l+1}{2} \rfloor + 1 }, v_{\lfloor \frac{l+1}{2} \rfloor + 2}, ..., v_{l};

  3. Вершини, що знаходяться у піддеревах вершини v_{\lfloor \frac{l+1}{2} \rfloor} (лише у випадку непарного ).

Для будь-якого діаметра (нехай та його кінцеві вершини) виконуються наступні твердження:

  • — зелені вершини;

  • хоча б одне з наступних тверджень:

    • — у першій групі, — у другій групі (або навпаки);

    • — у першій або другій групі, — у третій (або навпаки);

    • — у третій групі, але у різних піддеревах відносно вершини v_{\lfloor \frac{l+1}{2} \rfloor};

Твердження 2. Якщо є дві зелені вершини , третьої групи, що знаходяться в різних піддеревах відносно вершини v_{\lfloor \frac{l+1}{2} \rfloor}, то можна зробити перетин діаметрів рівний , взявши діаметри — та — .

Твердження 3. Нехай немає зелених вершин третьої групи. Для вершин першої групи знайдемо вершину діаметра v_{right} першої групи, що в її піддереві є зелена вершина , та v_{right} якомога ближче до середини діаметра. Аналогічно треба знайти вершину діаметра v_{left} другої групи, що в її піддереві є зелена вершина та v_{left} якомога ближче до середини діаметра. Тоді вигідно взяти такі діаметри — та — , бо в цьому випадку діаметри завжди будуть перетинатися по вершинах v_{right}, v_{right+1}, \ldots, v_{left}.

На малюнку червоним зображено вершини v_{right} та v_{left}.

Твердження 4. Нехай є зелена вершина третьої групи й немає таких двох вершин з твердження . Тоді всі такі зелені вершини третьої групи розташовані в одному піддереві відносно вершини v_{\lfloor \frac{l+1}{2} \rfloor}. У цьому випадку нам, крім знаходження v_{right} та v_{left}, треба знайти v_{down}, вершину, що в її піддереві є дві зелені вершини в різних піддеревах відносно неї (або v_{down}=a, якщо такої не існує), що якомога ближче до вершини v_{\lfloor \frac{l+1}{2} \rfloor}.

На малюнку червоним зображено вершини v_{right}, v_{down} та v_{left}. В цьому випадку ми не можемо зробити перетин краще ніж

\min(d(v_{right}, v_{\lfloor \frac{l+1}{2} \rfloor}), d(v_{left}, v_{\lfloor \frac{l+1}{2} \rfloor}), d(v_{down}, v_{\lfloor \frac{l+1}{2} \rfloor})),

де d(u, v) — кількість вершин на шляху між вершинами та .

Наприклад, якщо взяти діаметри — та — , то перетин буде

v_{\lfloor \frac{l+1}{2} \rfloor}, v_{\lfloor \frac{l+1}{2} \rfloor + 1}, \ldots, v_{left}.

Тоді розв'язання задачі має наступний вигляд:

  1. Знаходимо будь-який діаметр. Це можна зробити загальновідомим алгоритмом з двома dfs-ами просто знайшов найдальшу вершину від вершини , а потім аналогічно знайти найдальшу вершину від . Можна показати, що — — діаметр;

  2. Розглядаємо випадки в залежності в яке твердження попадаємо.

Складність алгоритму .