Розфарбування дерева#11002

Розфарбування дерева (Розбір)

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

Запустимо пошук у глибину з вершини $1$ і обчислимо значення $w e i g h t [v]$ weight[v] — розмір піддерева з коренем у вершині $v$ (тобто кількість вершин у піддереві $v$ ). Нехай $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k — сини $v$ . Тоді виконується формула:

w e i g h t [v] = 1 + w e i g h t [t o_{1}] + w e i g h t [t o_{2}] + ... + w e i g h t [t o_{k}]

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

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

Розглянемо функцію dfs2. Нехай ми знаходимось у вершині $v$ , а її батьком є вершина $p$ . Якщо першим ходом вибрати вершину $v$ , то кількість отриманих очок дорівнює $s$ .

v o i d df s 2 (in t v, in tp, l o n g l o n g s)

void~dfs2(int~v,~int p,~long~long~s)

Зробимо перехід по ребру $(v, t o)$ (v, to) і покажемо, як обчислити відповідь, якщо почати гру з вершини $t o$ . Фактично, ми виконуємо переп"ідвішування дерева: корінь переноситься з вершини $v$ у вершину $t o$ .

Зліва зображено дерево з коренем у $v$ . Вершина $t o$ є одним з її нащадків, а $p$ — її предком. Справа показано дерево з коренем у $t o$ .

Щоб обчислити $w e i g h t [t o]$ weight[to] для правого дерева, необхідно зі значення $s$ у лівому дереві відняти $w e i g h t [t o]$ weight[to] лівого дерева і додати кількість вершин в області, позначеній пунктиром. Ця кількість дорівнює $n - w e i g h t [t o]$ n - weight[to].

Приклад

Нехай першою обраною вершиною є $1$ . Тоді кількість отриманих очок становитиме $25$ .

Якщо першою обраною вершиною буде $2$ , то кількість отриманих очок дорівнює $26$ . Перехід від вершини $1$ до вершини $2$ виконаємо наступним чином: віднімемо від $s = 25$ s = 25 значення $w e i g h t [2] = 4$ weight[2] = 4 і додамо $(9 - w e i g h t [4]) = 5$ (9 - weight[4]) = 5. У результаті отримаємо $25 - 4 + 5 = 26$ 25 - 4 + 5 = 26, значення $s$ для дерева з коренем у вершині $2$ .

Максимальна кількість очок дорівнює $36$ і досягається, якщо почати гру з вершини $7$ .

Вправа

Розглянемо наступне дерево:

Нехай першим ходом обрана вершина $1$ . Знайдіть кількість отриманих очок.
Перенесіть корінь з вершини $1$ у вершину $3$ і обчисліть кількість отриманих очок.
Далі перенесіть корінь з $3$ у $4$ , з $3$ у $5$ і з $3$ у $6$ . Розв'яжіть кожну з отриманих задач.

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

Оголосимо список суміжності графа $g$ .

vector\u003cvector\u003cint\u003e\u003e g;
vector\u003cint\u003e weight;

Функція dfs1 виконує пошук у глибину з вершини $v$ , предком якої є вершина $p$ . При цьому обчислюється $w e i g h t [v]$ weight[v] — розмір піддерева з коренем у вершині $v$ , тобто кількість вершин у цьому піддереві.

void dfs1(int v, int p)
{
  weight[v] = 1;
  for (int to : g[v])
    if (to != p)
    {
      dfs1(to, v);
      weight[v] += weight[to];
    }
}

C++

Функція dfs2 виконує пошук у глибину з вершини $v$ , предком якої є вершина $p$ . Якщо першим ходом гри вибрати вершину $v$ , то кількість отриманих очок становитиме $s$ .

void dfs2(int v, int p, long long s)
{
  res = max(res, s);
  for (int to : g[v])
    if (to != p) dfs2(to, v, s - weight[to] + n - weight[to]);
}

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

scanf("%d", \u0026n);
g.resize(n + 1);
weight.resize(n + 1);
for (i = 1; i \u003c n; i++)
{
  scanf("%d %d", \u0026a, \u0026b);
  g[a].push_back(b);
  g[b].push_back(a);
}

C++

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

dfs1(1, 0);

У змінній $s$ обчислюємо суму всіх чисел у масиві $w e i g h t$ weight. Це значення дорівнює кількості отриманих очок у випадку, якщо першою в грі вибрати вершину $1$ .

s = 0;
for (i = 1; i \u003c= n; i++)
  s += weight[i];

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

dfs2(1, 0, s);

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

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