Cütləri tap (Həll təhlili)

Şərt d(i, j) = d(i, 1) - d(j, 1) dərinlik axtarışı zamanı $j$ $i$-nin əcdadı olduğu hər bir cüt $(i,j)$ üçün doğrudur. Misal olaraq aşağıdakı şəkli nəzərdən keçirək:

• d(4, 1) = 2, d(4, 1) - d(1, 1) = 2 - 0 = 2;

• d(6, 3) = 2, d(6, 1) - d(3, 1) = 3 - 1 = 2;

• d(2, 2) = 0, d(2, 1) - d(2, 1) = 1 - 1 = 0;

• d(6, 1) = 3, d(6, 1) - d(1, 1) = 3 - 0 = 3;

Bir $v$ düyünün dərinliyi $h[v]$ kök düyündən (1 düyünü) $v$-yə qədər olan yolda olan düyünlərin sayıdır. Şəkildə hər bir düyünün yaxınlığında dərinliyi göstərilmişdir.

İndi bir $i$ düyününü müəyyən edək və soruşaq: neçə $j$ düyünü var ki, bunlar üçün d(i, j) = d(i, 1) - d(j, 1) şərti doğrudur.

Məsələn, i = 6 üçün $4$ belə düyün var: j = 1, 3, 4, 6. Gördüyümüz kimi, h[6] = 4. Deməli, müəyyən edilmiş $i$ düyünü üçün dəqiq $h[i]$ uyğun $j$ düyünləri mövcuddur.

Məsələni həll etmək üçün ağacda hər bir $v$ düyünü üçün onun dərinliyini $h[v]$ hesablamaq, sonra isə bütün dərinliklərin cəmini ağacın daxilində tapmaq lazımdır.

Misal

Məsələnin misalındakı qrafı nəzərdən keçirək. Hər bir düyünün yaxınlığında dərinliyini qeyd edəcəyik.

Bütün düyünlərin dərinliklərinin cəmi 1 + 2 + 3 + 3 + 4 = 13-ə bərabərdir.

Alqoritmin reallaşdırılması

Qrafın qonşuluq siyahısını elan edək $g$. Düyünlərin dərinliyini $h$ massivində saxlayırıq.

vector<vector<int> > g;
vector<int> h;

DFS funksiyası hər bir $v$ məntəqəsi üçün onun dərinliyini hesablayır. $v$ düyünün əcdadı $p$ düyünüdür.

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

(v, to) kənarını nəzərdən keçiririk. Əgər $to$ düyünü $v$ düyününün əcdadı deyilsə, onun dərinliyini hesablayırıq və o nöqtədən dərinlik axtarışını başladırıq.

    if (to != p)
    {
      h[to] = h[v] + 1;
      dfs(to, v);
    }
  return h[v];
}

Proqramın əsas hissəsi. Ağacdakı düyünlərin sayını oxuyuruq $n$.

scanf("%d", &n);
g.resize(n + 1);

Ağacı qururuq.

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

1 düyününün dərinliyini 1 təyin edirik.

h.resize(n + 1);
h[1] = 1;

1 nöqtəsindən başlayaraq dərinlik axtarışını beganırıq.

dfs(1, -1);

Nəticəni hesablamaq – bütün düyünlərin dərinliklərinin cəmini.

res = 0;
for (i = 1; i <= n; i++)
  res += h[i];

Nəticəni çap edirik.

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