Ağacın rənglənməsi#11002

Ağacın rənglənməsi (Həll təhlili)

Qazanılan xalların sayı birmənalı şəkildə seçilən birinci təpə ilə müəyyən olunur. Buna görə də bütün mümkün başlanğıc təpələri yoxlamaq, hər biri üçün yekun xal sayını hesablamaq və maksimum qiyməti seçmək kifayətdir.

$1$ təpəsindən dərinliyə axtarış işə salaq və $w e i g h t [v]$ weight[v] — kökü $v$ təpəsində olan alt ağacın ölçüsünü (yəni $v$ alt ağacındakı təpələrin sayını) hesablayaq. Tutaq ki, $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k — $v$ -nin oğullarıdır. Onda aşağıdakı düstur doğrudur:

w e i g h t [v] = 1 + w e i g h t [t o_{1}] + w e i g h t [t o_{2}] + ... + w e i g h t [t o_{k}]

weight[v] = 1 + weight[to_1] + weight[to_2] + ... + weight[to_k]

İkinci dərinliyə axtarış bütün təpələr üzrə yerinə yetirilir və verilmiş təpədən oyuna başladıqda əldə edilə biləcək maksimum xal sayını yenidən hesablamağa imkan verir.

dfs2 funksiyasına baxaq. Tutaq ki, biz $v$ təpəsindəyik, onun valideyni isə $p$ təpəsidir. Əgər birinci hərəkətdə $v$ təpəsi seçilərsə, qazanılan xalların sayı $s$ -ə bərabərdir.

v o i d df s 2 (in t v, in tp, l o n g l o n g s)

void~dfs2(int~v,~int p,~long~long~s)

$(v, t o)$ (v, to) kənarı boyunca keçid edək və $t o$ təpəsindən oyuna başladıqda cavabın necə hesablanacağını göstərək. Faktiki olaraq biz ağacın yenidən asılmasını (переподвешивание) yerinə yetiririk: kök $v$ təpəsindən $t o$ təpəsinə köçürülür.

Solda kökü $v$ -də olan ağac təsvir olunub. $t o$ təpəsi onun nəvələrindən (potomoklarından) biridir, $p$ isə onun əcdadıdır. Sağda isə kökü $t o$ -da olan ağac göstərilib.

Sağdakı ağac üçün $w e i g h t [t o]$ weight[to]-nu hesablamaq üçün soldakı ağacda olan $s$ qiymətindən soldakı ağacın $w e i g h t [t o]$ weight[to]-sunu çıxmaq və nöqtəli xətlə işarələnmiş sahədəki təpələrin sayını əlavə etmək lazımdır. Bu say $n - w e i g h t [t o]$ n - weight[to]-ya bərabərdir.

Misal

Tutaq ki, seçilən birinci təpə $1$ -dir. Onda qazanılan xalların sayı $25$ olacaq.

Əgər seçilən birinci təpə $2$ olarsa, qazanılan xalların sayı $26$ -ya bərabər olacaq. $1$ təpəsindən $2$ təpəsinə keçidi aşağıdakı kimi yerinə yetirək: $s = 25$ s = 25 qiymətindən $w e i g h t [2] = 4$ weight[2] = 4 qiymətini çıxaq və $(9 - w e i g h t [4]) = 5$ (9 - weight[4]) = 5 əlavə edək. Nəticədə $25 - 4 + 5 = 26$ 25 - 4 + 5 = 26 alınır, bu da kökü $2$ təpəsində olan ağac üçün $s$ qiymətidir.

Maksimum xal sayı $36$ -ya bərabərdir və oyuna $7$ təpəsindən başlandıqda əldə edilir.

Məşq

Aşağıdakı ağaca baxaq:

Tutaq ki, birinci hərəkətdə $1$ təpəsi seçilib. Qazanılan xalların sayını tapın.
Kökü $1$ təpəsindən $3$ təpəsinə köçürün və qazanılan xalların sayını hesablayın.
Sonra kökü $3$ -dən $4$ -ə, $3$ -dən $5$ -ə və $3$ -dən $6$ -ya köçürün. Əldə edilən məsələlərin hər birini həll edin.

Alqoritmin realizasiyası

Qrafın qonşuluq siyahısını elan edək $g$ .

vector<vector<int>> g;
vector<int> weight;

dfs1 funksiyası $v$ təpəsindən dərinliyə axtarışı yerinə yetirir, onun valideyni $p$ təpəsidir. Bu zaman $w e i g h t [v]$ weight[v] — kökü $v$ təpəsində olan alt ağacın ölçüsü, yəni bu alt ağacdakı təpələrin sayı hesablanır.

void dfs1(int v, int p)
{
  weight[v] = 1;
  for (int to : g[v])
    if (to != p)
    {
      dfs1(to, v);
      weight[v] += weight[to];
    }
}

C++

dfs2 funksiyası $v$ təpəsindən dərinliyə axtarışı yerinə yetirir, onun valideyni $p$ təpəsidir. Əgər oyunun birinci hərəkətində $v$ təpəsi seçilərsə, qazanılan xalların sayı $s$ olacaq.

void dfs2(int v, int p, long long s)
{
  res = max(res, s);
  for (int to : g[v])
    if (to != p) dfs2(to, v, s - weight[to] + n - weight[to]);
}

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

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

C++

$1$ təpəsindən dərinliyə axtarışı işə salırıq.

dfs1(1, 0);

$s$ dəyişənində $w e i g h t$ weight massivindəki bütün ədədlərin cəmini hesablayırıq. Bu qiymət, əgər oyunda birinci $1$ təpəsi seçilərsə, qazanılan xalların sayına bərabərdir.

s = 0;
for (i = 1; i <= n; i++)
  s += weight[i];

$1$ təpəsindən ikinci dərinliyə axtarışı işə salırıq.

dfs2(1, 0, s);

Cavabı çap edirik.

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