Погоня за метеликом#11058

Погоня за метеликом (Розбір)

Виконаємо обхід в глибину з вершини $1$ . Для кожної вершини обчислимо два значення:

$d [v]$ — відстань від вершини $1$ до вершини $v$ . Якщо $p$ — батько $v$ , то
$d [v] = d [p] + 1$
d[v] = d[p] + 1
$h [v]$ — відстань від вершини $v$ до найближчого листа в піддереві з коренем $v$ . Якщо $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k — сини вершини $v$ , то
$h [v] = 1 + min (h [t o_{1}], h [t o_{2}], ..., h [t o_{k}])$
h[v] = 1 + min(h[to_1], h[to_2], ..., h[to_k])
Якщо $v$ — лист дерева, то покладемо $h [v] = 0$ h[v] = 0.

Потім запустимо другий обхід в глибину. Під час цього обходу будемо обчислювати значення $r es [v]$ — мінімальна кількість друзів, яких потрібно розмістити в деяких із листків піддерева з коренем у вершині $v$ , щоб гарантовано зловити метелика, за умови, що він вибрав це піддерево.

Якщо $h [v] \leq d [v]$ h[v] \le d[v], то $r es [v] = 1$ res[v] = 1. В цьому випадку достатньо розмістити одного друга в листі з мінімальною глибиною в піддереві вершини $v$ : він встигне дійти до вершини $v$ не пізніше, ніж метелик — з кореня дерева.

В іншому випадку, якщо $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k — сини вершини $v$ , то

r es [v] = r es [t o_{1}] + r es [t o_{2}] + ... + r es [t o_{k}]

res[v] = res[to_1] + res[to_2] + ... + res[to_k]

Якщо метелик не буде спійманий в самій вершині $v$ , необхідно бути готовими перехопити його в будь-якому із піддерев, що виходять із синів $v$ .

Шуканою відповіддю на задачу є значення $r es [1]$ .

Приклад

У першому прикладі (на малюнку зліва) потрібні два друга, яких необхідно розмістити у двох виходах. Метелик може полетіти з вершини $1$ або в вершину $2$ , або в вершину $3$ . В будь-якому з цих випадків його перехопить один із друзів Нюші.

У другому прикладі (на малюнку справа) достатньо одного друга, якого можна розмістити в будь-якому з двох виходів — вершині $3$ або $4$ . За одну хвилину метелик долетить з вершини $1$ до вершини $2$ . За цей же час друг добереться до вершини $2$ і зловить метелика там.

Розглянемо наступний приклад. Для поимки метелика Нюше знадобляться три друга.

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

Оголосимо константу нескінченність та робочі масиви.

#define INF 2000000000
vector<vector<int> > g;
vector<int> d, h, res;

Функція dfs $(v, p, c n t)$ (v, p, cnt) виконує обхід в глибину, починаючи з вершини $v$ , і повертає значення $h [v]$ . При цьому $p$ — предок вершини $v$ , а $c n t$ — відстань від вершини $1$ до $v$ . В процесі обходу для кожної вершини $v$ обчислюються значення $d [v]$ та $h [v]$ .

int dfs(int v, int p = -1, int cnt = 0)
{

Значення $c n t$ , рівне відстані від вершини $1$ до $v$ , зберігаємо в $d [v]$ .

  d[v] = cnt;
  int height = INF;

Перебираємо всіх синів вершини $v$ . Розглядаємо ребро $v \to t o$ v \to to. Якщо $t o$ збігається з предком $v (t o = p)$ v~(to = p), переходимо до наступного сина.

  for (int to : g[v])
    if (to != p)

У змінній $h e i g h t$ обчислюємо значення

min (h [t o_{1}], h [t o_{2}], ..., h [t o_{k}]),

min(h[to_1], h[to_2], ..., h[to_k]),

де $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k — сини вершини $v$ .

h e i g h t = min (h e i g h t, df s (t o, v, c n t + 1));

height = min(height, dfs(to, v, cnt + 1));

Якщо $h e i g h t = I N F$ height = INF, значить вершина $v$ є листом, і слід встановити $h [v] = 0$ h[v] = 0. В іншому випадку повертаємо

h [v] = 1 + min (h [t o_{1}], h [t o_{2}], ..., h [t o_{k}])

h[v] = 1 + min(h[to_1], h[to_2], ..., h[to_k])

  return h[v] = (height == INF) ? 0 : 1 + height;
}

Функція dfs2 $(v, p)$ виконує обхід в глибину, починаючи з вершини $v$ , і повертає значення $r es [v]$ . Тут $p$ — предок вершини $v$ .

int dfs2(int v, int p = -1)
{
  int s = 0;

Нехай $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k — сини вершини $v$ . У змінній $s$ обчислимо суму:

r es [t o_{1}] + r es [t o_{2}] + ... + r es [t o_{k}]

res[to_1] + res[to_2] + ... + res[to_k]

  for (int to : g[v])
    if (to != p)
    {
      dfs2(to, v);
      s += res[to];
    }

Якщо $h [v] \leq d [v]$ h[v] \le d[v], то достатньо одного друга, і $r es [v] = 1$ res[v] = 1. Інакше

r es [v] = r es [t o_{1}] + r es [t o_{2}] + ... + r es [t o_{k}] = s

res[v] = res[to_1] + res[to_2] + ... + res[to_k] = s

  return res[v] = (h[v] <= d[v]) ? 1 : s;
}

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

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++

Ініціалізуємо масиви.

d.resize(n + 1);
h.resize(n + 1);
res.resize(n + 1);

Запускаємо два обходи в глибину. Перший обхід для кожної вершини $v$ обчислює значення $d [v]$ та $h [v]$ .

dfs(1);
dfs2(1);

Виводимо відповідь — мінімальна кількість друзів, необхідна для поимки метелика.

printf("%lld\n", res[1]);