Для вершини позначимо через B(c, r) множину вершин на відстані не більше від , а для ребра покладемо B(uv, r) = B(u, r) \cup B(v, r). Обидві множини зв'язні (кожну вершину з'єднано з або шляхом усередині множини), а їхні діаметри не перевищують і 2r+1 відповідно.
Ключове спостереження. Відповідь для — це розмір найбільшої кулі відповідної парності:
(і для непарного , якщо n = 1).
За наведеними оцінками ці кулі є допустимими множинами. Навпаки, нехай — зв'язна множина з діаметром D \le x. Оскільки зв'язна, відстані всередині збігаються з відстанями в дереві. Візьмемо в шлях довжини і його середину: вершину , якщо парне, або ребро , якщо непарне. Кожна вершина w \in S лежить на відстані не більше від середини. Справді, нехай — найближча до вершина шляху , скажімо, на половині ближче до ; тоді маршрут від до проходить через , а потім через середину, тож якби була далі ніж від середини, ми отримали б d(w, b) > D. Тепер вмістимо у кулю потрібної парності:
парне, парне: S \subseteq B(c, D/2) \subseteq B(c, x/2);
парне, непарне: S \subseteq B(uv, (D-1)/2) \subseteq B(u, (D+1)/2) \subseteq B(u, x/2);
непарне, непарне: S \subseteq B(uv, (D-1)/2) \subseteq B(uv, (x-1)/2);
непарне, парне: S \subseteq B(c, D/2) \subseteq B(cv, (x-1)/2) для будь-якого сусіда вершини (він існує, якщо n > 1).
Алгоритм. Запустимо BFS з кожної вершини і порахуємо вершини на кожній відстані; префіксні суми цих кількостей дають |B(c, r)| одразу для всіх (для , більших за найбільшу відстань, куля — це все дерево). Для кожного зберігаємо максимум. Те саме робимо з BFS із двох джерел — обох кінців кожного ребра. Це 2n - 1 запусків BFS по кожен, тож складність — O(n^2) за часом і за пам'яттю на один тестовий випадок.