Заражене дерево#11724

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

Для кожної вершини $v$ обчислимо кількість вершин $s u m [v]$ у піддереві, де вона є коренем. Якщо $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k — сини вершини $v$ , то

s u m [v] = 1 + s u m [t o_{1}] + s u m [t o_{2}] + ... + s u m [t o_{k}]

sum[v] = 1 + sum[to_1] + sum[to_2] + ... + sum[to_k]

Якщо вершина $v$ є листком дерева, то $s u m [v] = 1$ sum[v] = 1.

Нехай $d p [v]$ дорівнює кількості врятованих вершин у піддереві з коренем $v$ , якщо на даний момент вершина $v$ (і тільки вона в піддереві) заражена.

Якщо вершина $v$ має тільки одного сина $t o$ , то $d p [v] = s u m [t o] - 1$ dp[v] = sum[to] - 1 (видалена вершина $t o$ не є врятованою).

Нехай вершина $v$ має двох синів $t o_{1}$ to_1 і $t o_{2}$ to_2 (кожна вершина має ступінь не більше $3$ ). Тоді у нас є два варіанти:

Видалити $t o_{1}$ to_1 і рекурсивно рятувати вершини піддерева з коренем $t o_{2}$ to_2. Кількість врятованих вершин складе $s u m [t o_{1}] - 1 + d p [t o_{2}]$ sum[to_1] - 1 + dp[to_2].
Видалити $t o_{2}$ to_2 і рекурсивно рятувати вершини піддерева з коренем $t o_{1}$ to_1. Кількість врятованих вершин складе $s u m [t o_{2}] - 1 + d p [t o_{1}]$ sum[to_2] - 1 + dp[to_1].

З двох варіантів слід вибрати той, при якому кількість врятованих вершин буде більшою.

Розглянемо процес пошуку в глибину, коли розглядається ребро $(v, t o)$ (v, to).

Нехай $a$ — другий син вершини $v$ . Нам слід обчислити значення $d p [t o] + s u m [a] - 1$ dp[to] + sum[a] - 1. Спробуємо його знайти, використовуючи тільки вершини $v$ і $t o$ . Нам відомо, що

s u m [v] = 1 + s u m [t o] + s u m [a]

sum[v] = 1 + sum[to] + sum[a]

Звідки

s u m [a] = s u m [v] - s u m [t o] - 1

sum[a] = sum[v] - sum[to] - 1

Отже

d p [t o] + s u m [a] - 1 = d p [t o] + s u m [v] - s u m [t o] - 2

dp[to] + sum[a] - 1 = dp[to] + sum[v] - sum[to] - 2

Перебираємо синів $t o$ вершини $v$ і обчислюємо

d p [v] = ma x (d p [t o] + s u m [v] - s u m [t o] - 2)

dp[v] = max(dp[to] + sum[v] - sum[to] - 2)

Приклад

У першому прикладі Хусейн зможе врятувати дві вершини $3$ і $4$ , обравши своїм першим ходом вершину номер $2$ .

Розглянемо другий приклад. Біля кожної вершини $v$ поставимо мітки $s u m [v] / d p [v]$ sum[v] / dp[v]. Вершини, обрані Хусейном, відобразимо зеленим кольором.

Наприклад,

d p [1] = ma x (s u m [2] - 1 + d p [5], s u m [5] - 1 + d p [2]) = ma x (2, 2) = 2, s u m [1] = 1 + s u m [2] + s u m [5] = 1 + 3 + 3 = 7

dp[1] = max(sum[2] - 1 + dp[5], sum[5] - 1 + dp[2]) = max(2, 2) = 2, \\ sum[1] = 1 + sum[2] + sum[5] = 1 + 3 + 3 = 7

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

Оголосимо робочі масиви.

#define MAX 300005
int sum[MAX], dp[MAX];
vector<vector<int>> g;

Функція dfs здійснює пошук в глибину з вершини $v$ . Предком вершини $v$ є $p$ .

void dfs(int v, int p = -1)
{

Ініціалізуємо значення $s u m [v]$ і $d p [v]$ .

  sum[v] = 1;
  dp[v] = 0;

Запускаємо пошук в глибину з синів вершини $v$ .

  for (int to : g[v])
    if (to != p)
    {
      dfs(to, v);
      sum[v] += sum[to];
    }

Вичисляємо значення $d p [v]$ .

  for (int to : g[v])
    if (to != p)
    {
      dp[v] = max(dp[v], sum[to] - 1); // if 1 son
      dp[v] = max(dp[v], dp[to] + sum[v] - sum[to] - 2);
    }
}

C++

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

scanf("%d", &n);
g.clear(); g.resize(n + 1);
memset(dp, 0, sizeof(dp));
memset(sum, 0, sizeof(sum));
for (i = 1; i < n; i++)
{
  scanf("%d %d", &u, &v);
  g[u].push_back(v);
  g[v].push_back(u);
}

C++

Запускаємо пошук в глибину з вершини $1$ .

dfs(1);

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

printf("%d\n", dp[1]);