Втеча ватажка (Розбір)

Втеча ватажка#9888

Сховища та ходи утворюють дерево з $n$ вершин. Перекриття ходу – це видалення ребра. Потрібно додати найменшу кількість ребер так, щоб після видалення будь-якого одного ребра граф залишався зв'язним, тобто щоб у ньому не було мостів. Якщо граф залишається зв'язним, то з будь-якого сховища можна дістатися до штабу, тому номер штабу $h$ на відповідь не впливає.

Нижня оцінка. Назвемо листком вершину степеня $1$ , і нехай у дереві $L$ листків. Єдине ребро, що виходить з листка, є мостом. Щоб воно перестало бути мостом, до листка потрібно провести хоча б одне нове ребро. Кожне нове ребро має два кінці, тому покриває не більше двох листків. Отже, знадобиться не менше $⌈ L /2 ⌉$ нових ребер.

Побудова. Покажемо, що $⌈ L /2 ⌉$ ребер завжди достатньо. Запустимо пошук у глибину з будь-якої вершини і випишемо листки в тому порядку, в якому проходить їхній обхід: $l_{0}, l_{1}, ..., l_{L - 1}$ l_0, l_1, ..., l_{L-1}. Позначимо $k = ⌊ L /2 ⌋$ k = \lfloor L / 2 \rfloor і з'єднаємо листки, номери яких у цьому списку відрізняються на $k$ :

l_{0} - l_{k}, l_{1} - l_{k + 1}, ..., l_{⌈ L /2 ⌉ - 1} - l_{⌈ L /2 ⌉ - 1 + k}

l_0 - l_k, l_1 - l_{k+1}, ..., l_{\lceil L / 2 \rceil - 1} - l_{\lceil L / 2 \rceil - 1 + k}

Отримується рівно $⌈ L /2 ⌉$ ребер, і кожен листок виявляється кінцем хоча б одного з них. При непарному $L$ листок $l_{k}$ l_k бере участь у двох ребрах.

Приклад. На малюнку $L = 5$ L = 5 і $k = 2$ k = 2. Листки зафарбовані, поряд з кожним вказано його номер у порядку обходу. Додані ребра $(3, 5), (4, 7)$ (3, 5), (4, 7) і $(5, 8)$ показані пунктиром, листок $5$ бере участь у двох з них.

Чому мостів не залишається. Підвісимо дерево за вершину, з якої запускався пошук. Ребро дерева ( $v$ , батько $v$ ) перестає бути мостом, якщо хоча б одне нове ребро з'єднує листок всередині піддерева $v$ з листком поза ним. Пошук у глибину обходить піддерево $v$ цілком, не перериваючись, тому листки цього піддерева йдуть у списку підряд і займають відрізок довжини $s$ . У піддереві є хоча б один листок, а всі $L$ листків у ньому опинитися не можуть: або у кореня є інші піддерева зі своїми листками, або корінь сам є листком. Тому $1 \leq s \leq L - 1$ 1 \le s \le L - 1.

Партнер кожного листка в новому ребрі відстоїть від нього в списку рівно на $k$ позицій. Розглянемо два випадки:

$s \leq k$ s \le k. Партнер першого листка відрізка знаходиться від нього на відстані $k \geq s$ k \ge s, тобто поза відрізком;
$s > k$ s > k. Поза відрізком лежить $L - s \leq L - k - 1 \leq k$ L - s \le L - k - 1 \le k листків. Візьмемо будь-який з них. Його партнер відстоїть від нього на $k$ позицій, а поза відрізком немає двох листків на такій відстані. Тому партнер лежить всередині відрізка.

В обох випадках знайдеться нове ребро, що з'єднує піддерево v з рештою дерева. Отже, жодне ребро не залишиться мостом.

Теорема. Найменша кількість нових ребер дорівнює $⌈ L /2 ⌉$ . Достатньо виписати листки в порядку пошуку в глибину і з'єднати кожен листок $l_{i}$ l_i з листком $l_{i} + ⌊ L /2 ⌋$ l_i + \lfloor L / 2 \rfloor для $i = 0, 1, ..., ⌈ L /2 ⌉ - 1$ i = 0, 1, ..., \lceil L / 2 \rceil - 1.

При $n = 2$ n = 2 обидва кінці єдиного ребра є листками, і відповіддю буде друге ребро між ними.

Приклад

У першому прикладі пошук з вершини $0$ проходить листки в порядку $1, 2, 3$ . Тут $L = 3, k = 1$ L = 3, k = 1, і програма додає ребра $(1, 2)$ і $(2, 3)$ :

Відповідь відрізняється від наведеної в умові, але також є вірною: підходить будь-який правильний набір з двох ребер.

У другому прикладі листки в порядку обходу: $4, 5, 2, 3$ 4, 5, 2, 3. Тут $L = 4, k = 2$ L = 4, k = 2:

$i$	0	1	2	3
$l_{i}$ l_i	4	5	2	3

З'єднуємо $l_{0} - l_{2}$ l_0 - l_2 і $l_{1} - l_{3}$ l_1 - l_3, тобто додаємо ребра $(4, 2)$ і $(5, 3)$ :

Перевіримо, наприклад, ребро $(0, 1)$ . Листки піддерева вершини $1$ — це $4$ і $5$ , вони займають у списку відрізок з позицій $0$ і $1$ . Ребро $(4, 2)$ виходить з цього піддерева, тому ребро $(0, 1)$ мостом не є.

Реалізація алгоритму

Дерево зберігаємо у вигляді списку суміжності $g$ . Листки в порядку обходу в глибину збираємо в масив $l e a v es$ .

vector<vector<int>> g;
vector<int> leaves;

Функція dfs виконує пошук у глибину з вершини $v$ . Параметр $p$ — батько вершини $v$ , для кореня $p = - 1$ p = -1. Спочатку обходимо всіх синів вершини $v$ .

void dfs(int v, int p = -1)
{
  for (int to : g[v])
    if (to != p) dfs(to, v);

Вершина степеня $1$ є листком, заносимо її в масив $l e a v es$ . Листки будь-якого піддерева потрапляють у масив підряд.

  if (g[v].size() == 1)
    leaves.push_back(v);
}

Основна частина програми. Читаємо вхідні дані. Номер штабу $h$ на відповідь не впливає.

  scanf("%d %d", &n, &h);
  g.resize(n);
  for (i = 1; i < n; i++)
  {
    scanf("%d %d", &a, &b);
    g[a].push_back(b);
    g[b].push_back(a);
  }

C++

Запускаємо пошук у глибину з вершини $0$ і збираємо листки. Змінна $m$ містить кількість листків, а $r = ⌈ m /2 ⌉$ r = \lceil m / 2 \rceil — кількість нових ходів.

  dfs(0);
  m = leaves.size();
  r = (m + 1) / 2;

Виводимо відповідь: листок з номером $i$ у списку з'єднуємо з листком з номером $i + ⌊ m /2 ⌋$ i + \lfloor m / 2 \rfloor.

  printf("%d\n", r);
  for (i = 0; i < r; i++)
    printf("%d %d\n", leaves[i], leaves[i + m / 2]);