Virus ağacı 2#10655

Virus ağacı 2 (Həll təhlili)

Ağacın boyanmasına $1$ zirvəsindən başlayırıq. Onu $k$ rənglə boyamaq olar.

Tutaq ki, biz $v$ zirvəsində yerləşirik. Əgər onun atası yoxdursa ( $v = 1$ v = 1), onda oğlanları $k - 1$ k - 1 rənglə boyamaq olar. Əgər $v$ zirvəsinin atası varsa, onda onun oğlanları $k - 2$ k - 2 rənglə boyanmalıdır. Çünki $v$ zirvəsinin oğlanları arasındakı məsafə $2$ -yə bərabərdir, onları eyni rənglərlə boyamaq olmaz.

Tutaq ki, müəyyənlik üçün $v$ zirvəsinin atası var. Onda $v$ zirvəsinin ilk oğlanını $k - 2$ k - 2 rənglə, ikinci oğlanını $k - 3$ k - 3 rənglə və s. boyamaq olar.

Hər zirvənin hansı rənglərlə boyanabileceyi hesablanmış rəng saylarını vurmaq qalır.

Nümunə

Birinci nümunə üçün $6$ boyama üsulu vardır:

İkinci testə nəzər salaq. Hər zirvənin yanında rəng sayı göstərək. Məsələn, $5$ zirvəsini 2 rənglə boyamaq olar, çünki onun rəngi $1$ və $4$ zirvələrinin rənglərinə uyğun olmamalıdır. Ağacı boyamağın ümumi üsulları $4 \cdot 3 \cdot 2 \cdot 1 \cdot 2 = 48$ 4 \cdot 3 \cdot 2 \cdot 1 \cdot 2 = 48-ə bərabərdir.

Alqoritmin realizasiyası

Girişdə verilən qraf qonşuluq siyahısında $g$ saxlanılır. $M O D$ sabiti – modulunu elan edirik.

#define MOD 1000000007
vector<vector<int>> g;

dfs funksiyası kökə $v$ zirvəsindən başlanan ağacın boyanma üsullarının sayını $M O D = 1 0^{9} + 7$ MOD = 10^9 + 7 modulu üzrə qaytarır. $v$ zirvəsinin atası $p$ -dir. $v$ zirvəsi $co l$ rənglərlə boyana bilər.

int dfs(int v, int col, int p = -1)
{
  long long res = col;

Biz $v$ zirvəsində yerləşirik. $v$ zirvəsinin oğlanlarının hansı rənglərlə boyanmayacağını $c n t$ dəyişənində qeyd edirik. Əvvəlcə $c n t = 1$ cnt = 1 qoyuruq, çünki $v$ zirvəsinin oğlanları $v$ zirvəsinin rəngi ilə eyni ola bilməz. Əgər $v$ zirvəsinin atası varsa ( $p \neq = - 1$ p \ne -1), onda $v$ zirvəsinin oğlanları $v$ -nin atasının rəngi ilə də eyni ola bilməz.

  int cnt = 1;
  if (p >= 0) cnt++;

$v$ zirvəsinin to oğlanlarını dolaşırıq.

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

to zirvəsi $k - c n t$ k - cnt rənglə boyana bilər. Hər oğlanla cnt dəyəri 1 artır.

      res = (res * dfs(to, k - cnt, v)) % MOD;
      cnt++;
    }
  return res;
}

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

scanf("%d %d", &n, &k);
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++

Dərinlik axtarışını $1$ zirvəsindən başlayırıq. $1$ zirvəsi $k$ rənglə boyana bilər.

res = dfs(1, k);

Cavabı ekrana çıxarırıq.

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

Python realizasiyası

Python interpretatorunun maksimum dərinliyini müəyyən edirik.

import sys
sys.setrecursionlimit(1000000)

$M O D$ sabitini – modulu elan edirik.

MOD = 1000000007

def dfs(v, col, p = -1):
  res = col

  cnt = 1
  if p >= 0: cnt += 1

$v$ zirvəsinin $t o$ oğlanlarını dolaşırıq.

  for to in g[v]:
    if to != p:

to zirvəsi $k - c n t$ k - cnt rənglə boyana bilər. Hər oğlanla cnt dəyəri 1 artır.

      res = (res * dfs(to, k - cnt, v)) % MOD
      cnt += 1
  return res

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

n, k = map(int, input().split())
g = [[] for _ in range(n + 1)]
for _ in range(n - 1):
  a, b = map(int, input().split())
  g[a].append(b)
  g[b].append(a)

Dərinlik axtarışını $1$ zirvəsindən başlayırıq. $1$ zirvəsi $k$ rənglə boyana bilər.

res = dfs(1, k)

Cavabı ekrana çıxarırıq.

print(res)