Зараження (Розбір)

Зараження#10367

Щоб заразити всі ферми, необхідно виконати два типи дій:

Переміщення. Потрібно відправити рівно $n - 1$ n - 1 корову по дорогах (кожна дорога використовується хоч би раз). Отже, мінімум $n - 1$ n - 1 день знадобиться лише на переміщення корів між фермами.
Подвоєння. Оскільки на фермі спочатку заражена лише одна корова, нам спочатку необхідно "виростити" потрібну кількість корів, виконуючи операції подвоєння.

Зауважимо, що подвоєння і переходи можуть відбуватися в різних місцях дерева після зараження.

Нехай на ферму $v$ прийшла одна хвора корова. Якщо ферма $v$ має $x$ дітей у дереві, то вона повинна відправити заражених корів до $x$ сусідів, тому їй потрібно мати щонайменше $x$ корів.

Спочатку на фермі $v$ є $1$ корова. Здійснюємо подвоєння: $1 \to 2 \to 4 \to 8$ 1 \to 2 \to 4 \to 8.... Мінімальна кількість подвоєнь, щоб отримати не менше $x$ корів, дорівнює $⌈ l o g_{2} x ⌉$ ⌈log_2 x⌉.

Таким чином, мінімальна кількість днів, необхідна для розповсюдження хвороби по всіх фермах, дорівнює

(n - 1) + v = 1 \sum n ⌈ l o g_{2} кількість дітей верхівки v ⌉

(n - 1) + ∑_{v = 1}^n ⌈log_2~кількість~дітей~верхівки~v⌉

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

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

Дерево зберігаємо у вигляді списку суміжності $g$ .

vector<vector<int>> g;

Функція dfs виконує обхід у глибину, починаючи з вершини $v$ , і повертає кількість днів, необхідних для подвоєння заражених корів у всіх вершинах піддерева з коренем у $v$ . Попередником вершини $v$ є $p a r$ .

int dfs(int v, int par = 0)
{
  int ans = 0;
  for (int to : g[v])
    if (to != par)
      ans += dfs(to, v);
  return ans + ceill(log2(g[v].size()));
}

C++

Основна частина програми. Читаємо вхідні дані. Будуємо граф.

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

C++

Запускаємо пошук у глибину з вершини $1$ і обчислюємо мінімальну кількість днів, необхідну для зараження всіх ферм. Відповідь зберігаємо у змінній $r es$ .

res = dfs(1) + n - 1;

Виводимо відповідь.

printf("%d\n", res);