Згруповані вершини#13108

Згруповані вершини (Розбір)

Для вершини позначимо через B(c, r) множину вершин на відстані не більше від , а для ребра покладемо B(uv, r) = B(u, r) \cup B(v, r). Обидві множини зв'язні (кожну вершину з'єднано з або шляхом усередині множини), а їхні діаметри не перевищують і 2r+1 відповідно.

Ключове спостереження. Відповідь для — це розмір найбільшої кулі відповідної парності:

\max_c |B(c, x/2)| \text{ для парного } x, \qquad \max_{uv} |B(uv, (x-1)/2)| \text{ для непарного } x

(і для непарного , якщо n = 1).

За наведеними оцінками ці кулі є допустимими множинами. Навпаки, нехай — зв'язна множина з діаметром D \le x. Оскільки зв'язна, відстані всередині збігаються з відстанями в дереві. Візьмемо в шлях довжини і його середину: вершину , якщо парне, або ребро , якщо непарне. Кожна вершина w \in S лежить на відстані не більше від середини. Справді, нехай — найближча до вершина шляху , скажімо, на половині ближче до ; тоді маршрут від до проходить через , а потім через середину, тож якби була далі ніж від середини, ми отримали б d(w, b) > D. Тепер вмістимо у кулю потрібної парності:

Алгоритм. Запустимо BFS з кожної вершини і порахуємо вершини на кожній відстані; префіксні суми цих кількостей дають |B(c, r)| одразу для всіх (для , більших за найбільшу відстань, куля — це все дерево). Для кожного зберігаємо максимум. Те саме робимо з BFS із двох джерел — обох кінців кожного ребра. Це 2n - 1 запусків BFS по кожен, тож складність — O(n^2) за часом і за пам'яттю на один тестовий випадок.