Ağacda məsafə#4104

Ağacda məsafə (Həll təhlili)

Tutaq ki, $d p [v] [x]$ dp[v][x] — $v$ köklü alt ağacda vərəsələr arasından $v$ -dan $x$ uzaqlıqda yerləşən zirvələrin sayıdır. $d p [v] [0] = 1$ dp[v][0] = 1 qəbul edək, çünki $v$ zirvəsindən 0 uzaqlıqda yalnız özü yerləşir.

Tutaq ki, $v$ zirvəsinin övladları $u_{1}, u_{2}, ..., u_{p}$ u_1, u_2, ..., u_p var. Onda $v$ köklü alt ağacda $v$ zirvəsindən $x$ uzaqlıqda yerləşən zirvələrin sayı, hər bir $u_{1}, u_{2}, ..., u_{p}$ u_1, u_2, ..., u_p zirvəsindən $x - 1$ x-1 uzaqlıqda yerləşən zirvələrin sayı cəminə bərabərdir.

d p [v] [x] = i = 1 \sum p d p [u_{i}] [x - 1]

dp[v][x] = \sum_{i = 1}^p dp[u_i][x-1]

Tutaq ki, kökü $v$ zirvəsi olan alt ağacı nəzərdən keçiririk. Bu alt ağacda tamamilə yerləşən və $v$ zirvəsindən keçən uzunluğu $k$ olan yolların sayını hesablayaq. Bu cür yolları iki qrupa bölək:

$v$ zirvəsində başlayan yollar. Onların sayı $d p [v] [k]$ dp[v][k]-ə bərabərdir.
$v$ zirvəsindən keçən və toplarından biri $v$ zirvəsinin oğlunun alt ağaclarında olan yollar.

Köklü alt ağacdan keçən uzunluğu $k$ olan bir yol nəzərdən keçirək. Yolun bir ucundan $v$ zirvəsinə qədər olan məsafə $x (1 \leq x \leq k - 1)$ x~(1 \le x \le k - 1) olsun. Tutaq ki, həmin ucu $u_{1}$ u_1 zirvəsinin alt ağacında yerləşir. Onda yolun ikinci ucundan $v$ zirvəsinə qədər olan məsafə $k - x$ k - x-ə bərabərdir və bu ikinci ucu $u_{1}$ u_1 zirvəsinin kökü olan alt ağacdan başqa istənilən alt ağacda yerləşə bilər.

Əgər yolun ilk ucundan $v$ zirvəsinə qədər olan məsafə $x$ -ə bərabərdirsə, onda həmin ucdan $u_{1}$ u_1 zirvəsinə qədər olan məsafə $x - 1$ x - 1-ə bərabərdir. Belə bir ilk uc seçməyin sayı $d p [u_{1}] [x - 1]$ dp[u_1][x - 1]-ə bərabərdir.

İkinci ucu seçməyin sayı $v$ zirvəsindən $k - x$ k - x uzaqlıqda yerləşən, lakin $u_{1}$ u_1 köklü alt ağaca aid olmayan zirvələrin sayına bərabərdir. Bu isə aşağıdakına bərabərdir:

d p [v] [k - x] - d p [u_{1}] [k - x - 1]

dp[v][k - x] - dp[u_1][k - x - 1]

Vurulanın qaydalarına əsasən, bu cür yolların ümumi sayı

d p [u_{1}] [x - 1] \cdot (d p [v] [k - x] - d p [u_{1}] [k - x - 1])

dp[u_1][x - 1] \cdot (dp[v][k - x] - dp[u_1][k - x - 1])

Beləliklə, bu cür yolların ümumi sayı

d p [v] [k] + 1/2 i = 1 \sum p x = 1 \sum k - 1 d p [u_{i}] [x - 1] \cdot (d p [v] [k - x] - d p [u_{i}] [k - x - 1])

dp[v][k] + 1/2 \sum_{i = 1}^p \sum_{x = 1}^{k - 1} dp[u_i][x-1] \cdot (dp[v][k-x]-dp[u_i][k-x-1])

Yuxarıdakı ifadəni ağacın bütün zirvələri üçün toplamaq lazımdır.

Məsələnin nümunəsi

Misala verilmiş ağacın quruluşuna nəzər salaq.

Alqoritmin realizasiyası

Massiv $g$ ağacı qıraq siyahıları ilə təqdim edir. Massiv $d p$ dinamik proqramlaşdırmanın tətbiqi üçün istifadə olunur.

vector<vector<int> > g;
vector<vector<int> > dp;

dfs funksiyası $v$ zirvəsindən başlayaraq dərinlik birinci axtarışı yerinə yetirir. Burada $p$ $v$ zirvəsinin qohumunu göstərir. Axtarış zamanı $d p$ massivini hazırlayırıq.

void dfs(int v, int p = -1)
{

Massiv $d p [v]$ -i indeksləyirik.

  dp[v].resize(k+1);
  dp[v][0] = 1;

Bütün zirvələri keçirik ki, $v$ zirvəsindən ona keçid mövcud olsun.

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

    dfs(to,v);

    for(int x = 1; x <= k; x++)
      dp[v][x] += dp[to][x-1];
  }
}

C++

dfsRes funksiyası $v$ zirvəsindən başlayaraq dərinlik birinci axtarışı yerinə yetirir və məcruci cavabı hesablamaq üçün nəzərdə tutulur.

void dfsRes(int v, int p = -1)
{

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

    dfsRes(to,v);

    for(int x = 1; x < k; x++)
      resA += 1LL * dp[to][x-1] * (dp[v][k-x] - dp[to][k-x-1]);
  }

  resB += dp[v][k];
}

C++

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq. Ağacı qururuq.

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++

Birinci dərinlik axtarışı ilə $d p$ massivini qururuq.

dp.resize(n+1);
dfs(1);

Axtarılan cavabı hesablamaq və çıxış etmək.

resA = resB = 0;
dfsRes(1);
res = resA / 2 + resB;
printf("%lld\n",res);

Python icrası

dfs funksiyası $v$ zirvəsindən başlayaraq dərinlik birinci axtarışı yerinə yetirir. Burada $p$ $v$ zirvəsinin qohumunu göstərir. Axtarış zamanı $d p$ massivini hazırlayırıq.

def dfs(v, p):

Massiv $d p [v]$ -i indeksləyirik.

  dp[v] = [0] * (k + 1)
  dp[v][0] = 1

Bütün zirvələri keçirik ki, $v$ zirvəsindən ona keçid mövcud olsun.

  for to in g[v]:
    if to == p: continue
    dfs(to, v)

    for x in range(1, k + 1):
      dp[v][x] += dp[to][x - 1]

dfsRes funksiyası $v$ zirvəsindən başlayaraq dərinlik birinci axtarışı yerinə yetirir və məcruci cavabı hesablamaq üçün nəzərdə tutulur.

def dfsRes(v, p):
  global resA, resB
  for to in g[v]:
    if to == p: continue
    dfsRes(to, v)

    for x in range(1, k):
      resA += dp[to][x - 1] * (dp[v][k - x] - dp[to][k - x - 1])

  resB += dp[v][k]

Python

Proqramın əsas hissəsi. Ağacın $n$ zirvələri və $k$ arasındakı məsafəni oxuyuruq.

n, k = map(int, input().split())

$g$ siyahısında ağacın qraf siyahıları ilə təqdimatı saxlanılır. $d p$ siyahısı dinamik proqramlaşdırmanın tətbiqi üçün istifadə olunur.

g = [[] for _ in range(n + 1)]
dp = [[] for _ in range(n + 1)]

Kənarların siyahısını oxuyuruq. Ağacı qururuq.

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

Birinci dərinlik axtarışı ilə $d p$ massivini qururuq.

dfs(1, -1)

Axtarılan cavabı hesablamaq və çıxış etmək.

resA, resB = 0, 0
dfsRes(1, -1)
res = resA // 2 + resB
print(res)