Чинар - символ Азербайджану#12195

Чинар - символ Азербайджану (Розбір)

Якщо дві вершини одного кольору з'єднані ребром, їх можна об'єднати в одну — при цьому відповідь не зміниться. Введемо поняття "компоненти зв'язності": дві вершини належать одній компоненті зв'язності, якщо вони:

мають однаковий колір;
з'єднані між собою ребром;

Розглянемо, наприклад, дерево зліва. Справа відображено граф його компонент зв'язності.

Якщо застосувати, наприклад, операцію $p ain t (2)$ , то дерево компонент буде стискатися:

Дерево буде пофарбовано в один колір тоді і тільки тоді, коли після таких операцій фарбування зі "стисненням" залишиться рівно одна компонента.

Нехай $d$ — діаметр дерева у графі компонент. Дерево буде пофарбовано в один колір тоді і тільки тоді, коли діаметр дерева стане дорівнювати $0$ , оскільки діаметр дорівнює $0$ лише у дерева, що складається з однієї вершини.

Знайдемо таку вершину, що довжина найкоротшої відстані від неї до будь-якої іншої вершини не перевищує $(d + 1) /2$ (d + 1) / 2. Така вершина завжди знайдеться, оскільки інакше діаметр дерева був би не менше $d + 1$ d + 1. Тепер зауважимо, що, застосувавши $(d + 1) /2$ (d + 1) / 2 операцій фарбування до цієї вершини, ми пофарбуємо дерево в один колір.

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

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

vector<int> color, dist;
vector<vector<int> > g, g1;
vector<int> comp, used;

Функція dfs1 виконує обхід дерева в глибину і розбиває його вершини на "компоненти зв'язності". Кожній вершині $v$ призначається номер компоненти $i d$ , який зберігається в масиві $co m p [v]$ .

void dfs1(int v, int col, int id)
{
  if (used[v]) return;
  if (color[v] != col) return;

  used[v] = 1;
  comp[v] = id;


  for (int to : g[v])
    dfs1(to, col, id);
}

C++

Функція dfs2 виконує обхід дерева в глибину і обчислює відстані від джерела до кожної вершини. Для вершини $v$ ця відстань зберігається в $d i s t [v]$ dist[v]. Поточна відстань від джерела до вершини $v$ дорівнює $d$ .

void dfs2(int v, int d, int p = -1)
{
  dist[v] = d;
  for (int to : g1[v])
    if (to != p) dfs2(to, d + 1, v);
}

Основна частина програми. Читаємо вхідні дані. Ініціалізуємо масиви.

scanf("%d", &n);
color.resize(n + 1);
g.resize(n + 1);
comp.resize(n + 1);
used.assign(n + 1, 0);
for (i = 1; i <= n; i++)
  scanf("%d", &color[i]);

C++

Читаємо і будуємо неорієнтоване дерево.

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

Розділяємо вершини дерева на компоненти. Загальна кількість компонент дорівнює $c n t$ . Нумерація компонент починається з $1$ .

cnt = 0;
for (i = 1; i <= n; i++)
  if (!used[i])
  {
    cnt++;
    dfs1(i, color[i], cnt);
  }

C++

Будуємо граф $g 1$ — граф компонент (стиснене дерево).

g1.resize(cnt + 1);
for (v = 1; v <= n; v++)
  for (int to : g[v])
    if (comp[v] != comp[to])
      g1[comp[v]].push_back(comp[to]);

Визначаємо діаметр графу компонент.

dist.resize(cnt + 1);

Запускаємо пошук в глибину з вершини $1$ і заповнюємо масив $d i s t$ , що містить найкоротші відстані від цієї вершини.

dfs2(1, 0, -1);

Вершина $a$ знаходиться на максимальній відстані від вершини $1$ .

a = max_element(dist.begin(), dist.begin() + cnt + 1) - dist.begin();

Запускаємо пошук в глибину з вершини $a$ і знову заповнюємо масив $d i s t$ .

dfs2(a, 0, -1);

Вершина $b$ найбільш віддалена від $a$ . Відстань між $a$ і $b$ є діаметром графу компонент.

b = max_element(dist.begin(), dist.begin() + cnt + 1) - dist.begin();

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

printf("%d\n", (dist[b] + 1) / 2);