Çınar - Azərbaycanın simvolu (Həll təhlili)

Əgər eyni rəngdə olan iki zirvə bir kənarla bağlıdırsa, onları birləşdirərək bir komponentə çevirə bilərik — bu zaman cavab dəyişməyəcək. "Əlaqəlilik komponenti" anlayışını təqdim edək: iki zirvə eyni əlaqəlilik komponentinə aiddirsə, onlar:

• eyni rəngdədirlər;

• bir kənarla birləşdiriliblər;

Məsələn, soldakı ağacı nəzərdən keçirək. Sağda onun əlaqəlilik komponentləri qrafı əks etdirilib.

Məsələn, $paint(2)$ əməliyyatını tətbiq etsək, komponentlərin ağacı sıxılacaq:

Ağac yalnız bir rəngdə olacaq, əgər və yalnız əgər belə sıxıcı boyama əməliyyatlarından sonra dəqiq bir komponent qalarsa.

Qoy $d$ komponentlər qrafında ağacın diametri olsun. Ağac yalnız bir rəngdə olacaq, əgər və yalnız əgər ağacın diametri $0$ olacaq, çünki $0$ diametri yalnız bir zirvəsi olan ağac üçün mövcuddur.

Elə bir zirvə tapaq ki, ondan digər hər hansı bir zirvəyə qədər ən qısa məsafə (d + 1) / 2 -dan böyük olmasın. Belə bir zirvə həmişə tapılar, əks halda ağacın diametri ən azı d + 1 olardı. İndi qeyd edək ki, həmin zirvəyə (d + 1) / 2 boyama əməliyyatı tətbiq etməklə ağacı eyni rəngə boyayacağıq.

Alqoritmin həyata keçirilməsi

İşçi massivlər elan ediləcək.

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

dfs1 funksiyası ağacın dərin özül (DFS) üzrə keçidini yerinə yetirir və zirvələri "əlaqəlilik komponentləri"nə bölür. Hər zirvə $v$ üçün komponent nömrəsi $comp[v]$ massivində saxlanılır.

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);
}

dfs2 funksiyası ağacın dərin özül üzrə keçidini yerinə yetirir və hər bir zirvənin mənbədən olan məsafələrini hesablamaqla saxlayır. Zirvə $v$ üçün bu məsafə dist[v] massivində saxlanılır. Mənbədən $v$ zirvəsinədək cari məsafə $d$ kimi müəyyən edilir.

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);
}

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq. Massivləri inizializasiya edirik.

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]);

Coyə düşürülsün və yönəldilməmiş ağacı quraq.

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

Ağacın zirvələrini komponentlərə bölürük. Ümumi komponentlərin sayı $cnt$ ilə təyin edilir. Komponentlərin nömrələnməsi $1$-dən başlayır.

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

Komponentlər qrafı $g1$ qururuq — sıxılmış ağac.

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]);

Komponentlər qrafının diametrini hesablayırıq.

dist.resize(cnt + 1);

Məsafələri vaxtında yeniləmək üçün birinci zəfərdən axtarışa başlayırıq.

dfs2(1, 0, -1);

$a$ zirvəsi birinci zirvədən maksimum məsafədədir.

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

$a$ zirvəsindən zəfər axtarışına başlayırıq və $dist$ massivini yenidən doldururuq.

dfs2(a, 0, -1);

$b$ zirvəsi $a$-dan maksimum məsafədədir. $a$ və $b$ arasındakı məsafə komponentlər qrafının diametridir.

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

Cavabı çap edirik.

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