Kinqpinin Qaçışı#9888

Kinqpinin Qaçışı (Həll təhlili)

Sığınacaqlar və yollar $n$ təpədən ibarət ağac əmələ gətirir. Yolun bağlanması – kənarın silinməsidir. İstənilən bir kənarı sildikdən sonra qrafın əlaqəli qalması üçün ən az sayda kənar əlavə etmək tələb olunur, yəni onda körpülər olmamalıdır. Əgər qraf əlaqəli qalırsa, onda istənilən sığınacaqdan qərargaha çatmaq mümkündür, buna görə də qərargahın nömrəsi $h$ cavaba təsir etmir.

Aşağı qiymətləndirmə. Dərəcəsi $1$ olan təpəyə yarpaq deyək və ağacda $L$ yarpaq olsun. Yarpaqdan çıxan yeganə kənar körpüdür. Onun körpü olmaması üçün yarpağa ən azı bir yeni kənar çəkmək lazımdır. Hər yeni kənarın iki ucu var, buna görə o, ən çoxu iki yarpağı əhatə edir. Deməli, ən azı $⌈ L /2 ⌉$ yeni kənar lazım olacaq.

Qurma. Göstərək ki, $⌈ L /2 ⌉$ kənar həmişə kifayətdir. İstənilən təpədən dərinliyə axtarış işə salaq və yarpaqları onların gəzilmə sırası ilə yazaq: $l_{0}, l_{1}, ..., l_{L - 1}$ l_0, l_1, ..., l_{L-1}. $k = ⌊ L /2 ⌋$ k = \lfloor L / 2 \rfloor işarə edək və bu siyahıda nömrələri $k$ fərqlənən yarpaqları birləşdirək:

l_{0} - l_{k}, l_{1} - l_{k + 1}, ..., l_{⌈ L /2 ⌉ - 1} - l_{⌈ L /2 ⌉ - 1 + k}

l_0 - l_k, l_1 - l_{k+1}, ..., l_{\lceil L / 2 \rceil - 1} - l_{\lceil L / 2 \rceil - 1 + k}

Dəqiq olaraq $⌈ L /2 ⌉$ kənar alınır və hər yarpaq onlardan ən azı birinin ucu olur. $L$ tək olduqda $l_{k}$ l_k yarpağı iki kənarda iştirak edir.

Misal. Şəkildə $L = 5$ L = 5 və $k = 2$ k = 2. Yarpaqlar rənglənmişdir, hər birinin yanında gəzilmə sırasındakı nömrəsi göstərilmişdir. Əlavə edilmiş $(3, 5), (4, 7)$ (3, 5), (4, 7) və $(5, 8)$ kənarları nöqtəli xətlə göstərilmişdir, $5$ yarpağı onların ikisində iştirak edir.

Niyə körpü qalmır. Ağacı axtarışın işə salındığı təpədən asaq. Ağacın ( $v$ , $v$ -nin valideyni) kənarı körpü olmaqdan çıxır, əgər ən azı bir yeni kənar $v$ -nin alt ağacı daxilindəki yarpağı onun xaricindəki yarpaqla birləşdirirsə. Dərinliyə axtarış $v$ -nin alt ağacını fasiləsiz olaraq bütövlükdə gəzir, buna görə bu alt ağacın yarpaqları siyahıda ardıcıl gəlir və $s$ uzunluqlu parça tutur. Alt ağacda ən azı bir yarpaq var, lakin bütün $L$ yarpaq onda ola bilməz: ya kökün öz yarpaqları olan başqa alt ağacları var, ya da kökün özü yarpaqdır. Buna görə $1 \leq s \leq L - 1$ 1 \le s \le L - 1.

Yeni kənarda hər yarpağın tərəfdaşı siyahıda ondan dəqiq olaraq $k$ mövqe aralı yerləşir. İki hal baxaq:

$s \leq k$ s \le k. Parçanın ilk yarpağının tərəfdaşı ondan $k \geq s$ k \ge s məsafədədir, yəni parçanın xaricindədir;
$se x t g r e a t er k$ s extgreater k. Parçanın xaricində $L - s \leq L - k - 1 \leq k$ L - s \le L - k - 1 \le k yarpaq qalır. Onlardan hər hansı birini götürək. Onun tərəfdaşı ondan $k$ mövqe aralıdır, lakin parçanın xaricində bu məsafədə iki yarpaq yoxdur. Buna görə tərəfdaş parçanın daxilindədir.

Hər iki halda $v$ alt ağacını qalan ağacla birləşdirən yeni kənar tapılacaq. Deməli, heç bir kənar körpü olaraq qalmayacaq.

Teorem. Ən az yeni kənar sayı $⌈ L /2 ⌉$ -ə bərabərdir. Yarpaqları dərinliyə axtarış sırası ilə yazıb hər $l_{i}$ l_i yarpağını $l_{i} + ⌊ L /2 ⌋$ l_i + \lfloor L / 2 \rfloor yarpağı ilə $i = 0, 1, ..., ⌈ L /2 ⌉ - 1$ i = 0, 1, ..., \lceil L / 2 \rceil - 1 üçün birləşdirmək kifayətdir.

$n = 2$ n = 2 olduqda yeganə kənarın hər iki ucu yarpaqdır, və cavab onların arasındakı ikinci kənar olacaq.

Misal

Birinci misalda $0$ təpəsindən axtarış yarpaqları $1, 2, 3$ sırası ilə gəzir. Burada $L = 3, k = 1$ L = 3, k = 1, və proqram $(1, 2)$ və $(2, 3)$ kənarlarını əlavə edir:

Cavab şərtdə verilmiş cavabdan fərqlənir, lakin o da düzgündür: istənilən düzgün iki kənar dəsti uyğun gəlir.

İkinci misalda yarpaqlar gəzilmə sırası ilə: $4, 5, 2, 3$ 4, 5, 2, 3. Burada $L = 4, k = 2$ L = 4, k = 2:

$i$	0	1	2	3
$l_{i}$ l_i	4	5	2	3

$l_{0} - l_{2}$ l_0 - l_2 və $l_{1} - l_{3}$ l_1 - l_3 birləşdiririk, yəni $(4, 2)$ və $(5, 3)$ kənarlarını əlavə edirik:

Məsələn, $(0, 1)$ kənarını yoxlayaq. $1$ təpəsinin alt ağacının yarpaqları $4$ və $5$ -dir, onlar siyahıda $0$ və $1$ mövqelərindən ibarət parçanı tuturlar. $(4, 2)$ kənarı bu alt ağacdan çıxır, buna görə $(0, 1)$ kənarı körpü deyil.

Alqoritmin realizasiyası

Ağacı qonşuluq siyahısı $g$ şəklində saxlayırıq. Dərinliyə axtarış sırası ilə yarpaqları $l e a v es$ massivinə toplayırıq.

vector<vector<int>> g;
vector<int> leaves;

dfs funksiyası $v$ təpəsindən dərinliyə axtarış aparır. $p$ parametri $v$ təpəsinin valideynidir, kök üçün $p = - 1$ p = -1. Əvvəlcə $v$ təpəsinin bütün övladlarını gəzirik.

void dfs(int v, int p = -1)
{
  for (int to : g[v])
    if (to != p) dfs(to, v);

Dərəcəsi $1$ olan təpə yarpaqdır, onu $l e a v es$ massivinə yazırıq. İstənilən alt ağacın yarpaqları massivdə ardıcıl düşür.

  if (g[v].size() == 1)
    leaves.push_back(v);
}

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq. Qərargahın nömrəsi $h$ cavaba təsir etmir.

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

C++

$0$ təpəsindən dərinliyə axtarış işə salırıq və yarpaqları toplayırıq. $m$ dəyişəni yarpaqların sayını saxlayır, $r = ⌈ m /2 ⌉$ r = \lceil m / 2 \rceil isə yeni yolların sayıdır.

  dfs(0);
  m = leaves.size();
  r = (m + 1) / 2;

Cavabı çıxarırıq: siyahıda $i$ nömrəli yarpağı $i + ⌊ m /2 ⌋$ i + \lfloor m / 2 \rfloor nömrəli yarpaqla birləşdiririk.

  printf("%d\n", r);
  for (i = 0; i < r; i++)
    printf("%d %d\n", leaves[i], leaves[i + m / 2]);