Kəpənəyin Arxasınca Qaçış#11058

Kəpənəyin Arxasınca Qaçış (Həll təhlili)

Dərinlik üzrə keçməyi $1$ təpəsindən başlayaraq icra edək. Hər bir təpə üçün iki dəyəri hesablayacağıq:

$d [v]$ — təpə $1$ -dən təpə $v$ -ə qədər məsafə. Əgər $p$ — $v$ təpəsinin valideyni isə, onda
$d [v] = d [p] + 1$
d[v] = d[p] + 1
$h [v]$ — təpə $v$ -dən $v$ -də köklü alt ağacın ən yaxın yarpağına qədər məsafə. Əgər $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k — $v$ təpəsinin övladlarıdırsa, onda
$h [v] = 1 + min (h [t o_{1}], h [t o_{2}], ..., h [t o_{k}])$
h[v] = 1 + min(h[to_1], h[to_2], ..., h[to_k])
Əgər $v$ ağacın yarpağıdırsa, onda $h [v] = 0$ h[v] = 0 qoyaq.

Daha sonra ikinci dərinlik üzrə keçməyi başladaq. Bu keçmə zamanı $r es [v]$ dəyərini hesablayacağıq — $v$ təpəsində köklü alt ağacda bəzi yarpaqlarda yerləşdirilməli olan minimum dost sayını, belə ki, kəpənəyi mütləq tutmaq olar, əgər o, bu alt ağacı seçərsə.

Əgər $h [v] \leq d [v]$ h[v] \le d[v]-dirsə, onda $r es [v] = 1$ res[v] = 1. Bu halda, $v$ təpəsinin alt ağacında minimum dərinliyi olan yarpağa bir dostu yerləşdirmək kifayətdir: o, ağacın kökündən çıxaraq keçmədən əvvəl $v$ təpəsinə çatacaq.

Əks halda, əgər $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k — $v$ təpəsinin övladlarıdırsa, onda

r es [v] = r es [t o_{1}] + r es [t o_{2}] + ... + r es [t o_{k}]

res[v] = res[to_1] + res[to_2] + ... + res[to_k]

Əgər kəpənək $v$ təpəsinin özündə tutulmazsa, $v$ -dən çıxan alt ağaclardakı hər hansı birindən onu tutmaq üçün hazır olmalıdırlar.

Tələb olunan cavab $r es [1]$ dəyəridir.

Nümunə

Birinci nümunədə (şəkilin sol tərəfində) iki dost lazımdır, onların iki çıxışda yerləşdirilməli olduğu yerdə. Kəpənək ya təpə $1$ -dən təpə $2$ -yə və ya təpə $3$ -ə uça bilər. Hər hansı bir halda, onu alınacaq.

İkinci nümunədə (şəkilin sağ tərəfində) bir dost kifayətdir, onu iki çıxışdan birinə — təpə $3$ və ya $4$ -ə yerləşdirmək olar. Bir dəqiqə ərzində kəpənək təpə $1$ -dən təpə $2$ -yə çatacaq. Eyni zamanda dostu təpə $2$ -yə çatacaq və onu orada tutacaq.

Növbəti nümunəyə baxaq. Kəpənəyi tutmaq üçün üç dost lazımdır.

Alqoritmin icrası

Sonsuzluq və işçi massivləri elan edək.

#define INF 2000000000
vector<vector<int> > g;
vector<int> d, h, res;

dfs funksiyası $(v, p, c n t)$ (v, p, cnt) dərinlik üzrə keçməni $v$ təpəsindən başlayır və $h [v]$ dəyərini qaytarır. Burada $p$ — $v$ təpəsinin əcdadı, və $c n t$ — $1$ təpəsindən $v$ -ə qədər olan məsafədir. Keçmə prosesi zamanı hər bir $v$ təpəsi üçün $d [v]$ və $h [v]$ dəyərləri hesablanır.

int dfs(int v, int p = -1, int cnt = 0)
{

$c n t$ dəyəri, $1$ təpəsindən $v$ -ə olan məsafə, $d [v]$ -də saxlanılır.

  d[v] = cnt;
  int height = INF;

$v$ təpəsinin bütün övladlarını nəzərdən keçiririk. $v \to t o$ v \to to olan qövsü nəzərdən keçiririk. Əgər $t o$ $v$ -in əcdadı ilə eynidirsə $(t o = p)$ (to = p), növbəti övlada keçirik.

  for (int to : g[v])
    if (to != p)

$h e i g h t$ dəyişənində aşağıdakı dəyəri hesablayırıq

min (h [t o_{1}], h [t o_{2}], ..., h [t o_{k}]),

min(h[to_1], h[to_2], ..., h[to_k]),

burada $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k — $v$ təpəsinin övladlarıdır.

h e i g h t = min (h e i g h t, df s (t o, v, c n t + 1));

height = min(height, dfs(to, v, cnt + 1));

Əgər $h e i g h t = I N F$ height = INF, bu $v$ təpəsinin yarpaq olduğunu və $h [v] = 0$ h[v] = 0-ı təyin etməyin lazım olduğunu bildirir. Əks halda,

h [v] = 1 + min (h [t o_{1}], h [t o_{2}], ..., h [t o_{k}])

h[v] = 1 + min(h[to_1], h[to_2], ..., h[to_k])

funksiya geriyə qaytarır

  return h[v] = (height == INF) ? 0 : 1 + height;
}

dfs2 funksiyası $(v, p)$ dərinlik üzrə keçməni $v$ təpəsindən başlayır və $r es [v]$ -i qaytarır. Burada $p$ — $v$ təpəsinin əcdadıdır.

int dfs2(int v, int p = -1)
{
  int s = 0;

Qoy $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k — $v$ təpəsinin övladlarıdır. $s$ dəyişənində aşağıdakı cəmi hesablayacağıq:

r es [t o_{1}] + r es [t o_{2}] + ... + r es [t o_{k}]

res[to_1] + res[to_2] + ... + res[to_k]

  for (int to : g[v])
    if (to != p)
    {
      dfs2(to, v);
      s += res[to];
    }

Əgər $h [v] \leq d [v]$ h[v] \le d[v]-dirsə, bir dost kifayətdir, və $r es [v] = 1$ res[v] = 1. Əks halda

r es [v] = r es [t o_{1}] + r es [t o_{2}] + ... + r es [t o_{k}] = s

res[v] = res[to_1] + res[to_2] + ... + res[to_k] = s

  return res[v] = (h[v] <= d[v]) ? 1 : s;
}

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

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

C++

Massivləri başladırıq.

d.resize(n + 1);
h.resize(n + 1);
res.resize(n + 1);

İki dərinlik üzrə keçmə işə salırıq. Birinci keçmə hər bir $v$ təpəsi üçün $d [v]$ və $h [v]$ dəyərlərini hesablayır.

dfs(1);
dfs2(1);

Cavabı çıxırıq — kəpənəyi tutmaq üçün lazım olan minimum dost sayını.

printf("%lld\n", res[1]);