Suç Baronunun Kaçışı#9888

Suç Baronunun Kaçışı (Editoryal)

Sığınaklar ve geçitler $n$ köşeli bir ağaç oluşturur. Bir geçidin kapatılması, bir kenarın silinmesi anlamına gelir. Herhangi bir kenar silindiğinde grafın bağlantılı kalması için, yani grafta köprü kalmaması için eklenmesi gereken en az kenar sayısı bulunmalıdır. Graf bağlantılı kalırsa, herhangi bir sığınaktan karargaha ulaşmak mümkündür, bu yüzden karargahın numarası $h$ cevabı etkilemez.

Alt sınır. Derecesi $1$ olan köşeye yaprak diyelim ve ağaçta $L$ tane yaprak olsun. Bir yaprak köşeden çıkan tek kenar bir köprüdür. Bu kenarın köprü olmaktan çıkması için yaprağa en az bir yeni kenar çekilmesi gerekir. Her yeni kenarın iki ucu vardır, bu yüzden en fazla iki yaprağı kapsar. Demek ki en az $⌈ L /2 ⌉$ yeni kenar gerekecektir.

İnşa. $⌈ L /2 ⌉$ kenarın her zaman yeterli olduğunu gösterelim. Herhangi bir köşeden derinlik öncelikli arama başlatalım ve yaprakları dolaşım sırasına göre yazalım: $l_{0}, l_{1}, ..., l_{L - 1}$ l_0, l_1, ..., l_{L-1}. $k = ⌊ L /2 ⌋$ k = \lfloor L / 2 \rfloor olarak gösterelim ve bu listede numaraları $k$ kadar farklı olan yaprakları birleştirelim:

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}

Tam olarak $⌈ L /2 ⌉$ kenar elde edilir ve her yaprak bunlardan en az birinin ucu olur. $L$ tek olduğunda $l_{k}$ l_k yaprağı iki kenara dahil olur.

Örnek. Şekilde $L = 5$ L = 5 ve $k = 2$ k = 2. Yapraklar boyanmıştır, her birinin yanında dolaşım sırasındaki numarası belirtilmiştir. Eklenen $(3, 5), (4, 7)$ (3, 5), (4, 7) ve $(5, 8)$ kenarları kesikli çizgiyle gösterilmiştir, yaprak $5$ bunlardan ikisine dahildir.

Neden köprü kalmıyor. Ağacı aramanın başlatıldığı köşeden asalım. Ağacın ( $v$ , $v$ 'nin ebeveyni) kenarı, eğer en az bir yeni kenar $v$ alt ağacının içindeki bir yaprağı dışındaki bir yaprakla birleştiriyorsa köprü olmaktan çıkar. Derinlik öncelikli arama, $v$ alt ağacını kesintisiz olarak tamamen dolaşır, bu yüzden bu alt ağacın yaprakları listede art arda gelir ve $s$ uzunluğunda bir aralık kaplar. Alt ağaçta en az bir yaprak vardır ve $L$ yaprağın tümü onda bulunamaz: ya kökün kendi yapraklarına sahip başka alt ağaçları vardır, ya da kökün kendisi bir yapraktır. Bu yüzden $1 \leq s \leq L - 1$ 1 \le s \le L - 1.

Yeni kenardaki her yaprağın ortağı, listede ondan tam olarak $k$ pozisyon uzaktadır. İki durumu inceleyelim:

$s \leq k$ s \le k. Aralığın ilk yaprağının ortağı ondan $k \geq s$ k \ge s mesafede yer alır, yani aralığın dışındadır;
$se x t g r e a t er k$ s extgreater k. Aralığın dışında $L - s \leq L - k - 1 \leq k$ L - s \le L - k - 1 \le k yaprak bulunur. Bunlardan herhangi birini alalım. Onun ortağı ondan $k$ pozisyon uzaktadır, ancak aralığın dışında bu mesafede iki yaprak yoktur. Bu yüzden ortağı aralığın içinde yer alır.

Her iki durumda da v alt ağacını ağacın geri kalanıyla birleştiren yeni bir kenar bulunacaktır. Demek ki hiçbir kenar köprü olarak kalmaz.

Teorem. En az yeni kenar sayısı $⌈ L /2 ⌉$ 'ye eşittir. Yaprakları derinlik öncelikli arama sırasına göre yazmak ve her $l_{i}$ l_i yaprağını $i = 0, 1, ..., ⌈ L /2 ⌉ - 1$ i = 0, 1, ..., \lceil L / 2 \rceil - 1 için $l_{i} + ⌊ L /2 ⌋$ l_i + \lfloor L / 2 \rfloor yaprağıyla birleştirmek yeterlidir.

$n = 2$ n = 2 olduğunda, tek kenarın her iki ucu da yapraktır ve cevap bu ikisi arasındaki ikinci kenar olacaktır.

Örnek

İlk örnekte, $0$ köşesinden başlayan arama yaprakları $1, 2, 3$ sırasıyla dolaşır. Burada $L = 3, k = 1$ L = 3, k = 1 ve program $(1, 2)$ ve $(2, 3)$ kenarlarını ekler:

Cevap, koşulda verilenden farklıdır, ancak o da doğrudur: herhangi bir doğru iki kenarlık küme uygundur.

İkinci örnekte, dolaşım sırasındaki yapraklar: $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 ve $l_{1} - l_{3}$ l_1 - l_3'ü birleştiriyoruz, yani $(4, 2)$ ve $(5, 3)$ kenarlarını ekliyoruz:

Örneğin, $(0, 1)$ kenarını kontrol edelim. $1$ köşesinin alt ağacının yaprakları $4$ ve $5$ 'tir, bunlar listede $0$ ve $1$ pozisyonlarından oluşan bir aralık kaplar. $(4, 2)$ kenarı bu alt ağaçtan çıkar, bu yüzden $(0, 1)$ kenarı köprü değildir.

Algoritmanın uygulanması

Ağacı $g$ komşuluk listesi şeklinde saklıyoruz. Derinlik öncelikli dolaşım sırasındaki yaprakları $l e a v es$ dizisinde topluyoruz.

vector	extless vector	extless int	extgreater 	extgreater g;
vector	extless int	extgreater leaves;

dfs fonksiyonu $v$ köşesinden derinlik öncelikli arama yapar. $p$ parametresi $v$ köşesinin ebeveynidir, kök için $p = - 1$ p = -1. Önce $v$ köşesinin tüm çocuklarını dolaşırız.

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

Derecesi $1$ olan köşe bir yapraktır, onu $l e a v es$ dizisine ekleriz. Herhangi bir alt ağacın yaprakları diziye art arda düşer.

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

Programın ana bölümü. Girdi verilerini okuyoruz. Karargahın numarası $h$ cevabı etkilemez.

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

C++

$0$ köşesinden derinlik öncelikli arama başlatıyoruz ve yaprakları topluyoruz. $m$ değişkeni yaprak sayısını, $r = ⌈ m /2 ⌉$ r = \lceil m / 2 \rceil ise yeni geçit sayısını içerir.

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

Cevabı yazdırıyoruz: listede $i$ numaralı yaprağı $i + ⌊ m /2 ⌋$ i + \lfloor m / 2 \rfloor numaralı yaprakla birleştiriyoruz.

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