Ağac#2923

Ağac (Həll təhlili)

Ağacın kökündən başlayaraq dərinlik üzrə ağacı gəzin. Hər bir $i$ zirvəsi üçün $s_{i}$ s_i çoxluğunu saxlayacağıq ki, burada kökü $i$ olan alt ağacda olan bütün zirvələrin rəngləri toplanır.

Əgər $j$ zirvəsi gəzinti prosesində $i$ zirvəsinin oğludursa, onda $s_{j}$ s_j çoxluğu $s_{i}$ s_i içərisinə daxil edilməlidir.

Kökü $i$ zirvəsində olan alt ağacda fərqli rənglərin sayı $s_{i}$ s_i çoxluğunun gücünə (ölçüsünə) bərabərdir.

Nümunə

Hər bir zirvənin solunda onun rəngi, sağında isə bu zirvənin kökü olduğu alt ağacda olan rənglərin çoxluğu göstərilir.

Alqoritmin həyata keçirilməsi

$co l or [i]$ color[i] massivində $i$ zirvəsinin rengi saxlanılır. $s [i]$ çoxluğunda isə kökü $i$ olan alt ağacda qarşılaşan rənglər toplanacaq.

Əyri ağac qrafın qonşuluq siyahısı şəklində təqdim olunub, $g$ . $r es [i]$ massivində kökü $i$ olan alt ağacdakı müxtəlif rənglərin sayı saxlanılır.

#define MAX 1000010
int color[MAX], res[MAX];
set<int> s[MAX];
vector<vector<int> > g;

dfs funksiyası $v$ zirvəsindən başlayaraq dərinlik üzrə ağacı gəzir.

void dfs(int v)
{

İlk olaraq $s [v]$ çoxluğuna $v$ zirvəsinin öz rəngini əlavə edirik.

  s[v].insert(color[v]);

Ağacın kənarlarını $(v, t o)$ (v, to) araşdırırıq.

  for (int to : g[v])
  {
    dfs(to);

Hər bir $(v, t o)$ (v, to) kənarı üçün $s [t o]$ çoxluğunu $s [v]$ çoxluğuna əlavə edirik. Əgər $s [v]$ çoxluğunun ölçüsü $s [t o]$ çoxluğunun ölçüsündən kiçikdirsə, onları yerləri ilə dəyişdiririk. Daha sonra kiçik $s [t o]$ çoxluğunun məzmununu $s [v]$ çoxluğuna əlavə edirik.

    if (s[v].size() < s[to].size()) s[v].swap(s[to]);
    s[v].insert(s[to].begin(), s[to].end());

$s [t o]$ çoxluğunu təmizləyirik — bizə daha lazım deyil.

    s[to].clear();
  }

Bundan sonra $r es [v]$ -də alt ağacdakı fərqli rənglərin sayını yazırıq, yəni $s [v]$ çoxluğunun ölçüsü.

  res[v] = s[v].size();
}

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

scanf("%d",&n);
g.resize(n+1);
for(i = 1; i <= n; i++)
{
  scanf("%d %d",&p,&c);
  g[p].push_back(i);
  color[i] = c;
}

C++

Ağacın kökündən - $0$ nömrəli zirvədən dərinlik axtarışına başlayırıq.

dfs(0);

Cavabı çıxardırıq.

for(i = 1; i <= n; i++)
  printf("%d ",res[i]);
printf("\n");