Yoluxmuş ağac#11724

Yoluxmuş ağac (Həll təhlili)

Hər bir $v$ zirvəsi üçün o zirvənin kök olduğu alt ağacdakı zirvələrin sayını $s u m [v]$ hesablayın. $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k - $v$ zirvəsinin oğlanlarıdırsa,

s u m [v] = 1 + s u m [t o_{1}] + s u m [t o_{2}] + ... + s u m [t o_{k}]

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

Əgər $v$ zirvəsi ağacın bir yarpaq zirvəsidirsə, onda $s u m [v] = 1$ sum[v] = 1.

Qoy $d p [v]$ hazırda yoluxmuş olan və yoluxmuşlar arasında yalnız $v$ zirvəsi olan alt ağacdakı xilas edilən zirvələrin sayını göstərsin.

Əgər $v$ zirvəsinin yalnız bir oğulu $t o$ varsa, o zaman $d p [v] = s u m [t o] - 1$ dp[v] = sum[to] - 1 (çıxarılan $t o$ zirvəsi xilas edilmiş olmaz).

Qoy $v$ zirvəsinin iki oğulu $t o_{1}$ to_1 və $t o_{2}$ to_2 olsun (hər bir zirvənin dərəcəsi 3-dən böyük deyil). Onda iki variantımız var:

$t o_{1}$ to_1 zirvəsini çıxarın və kökü $t o_{2}$ to_2 olan alt ağacdakı zirvələri rekursiv olaraq xilas edin. Xilas edilən zirvələrin sayı $s u m [t o_{1}] - 1 + d p [t o_{2}]$ sum[to_1] - 1 + dp[to_2] olacaq.
$t o_{2}$ to_2 zirvəsini çıxarın və kökü $t o_{1}$ to_1 olan alt ağacdakı zirvələri rekursiv olaraq xilas edin. Xilas edilən zirvələrin sayı $s u m [t o_{2}] - 1 + d p [t o_{1}]$ sum[to_2] - 1 + dp[to_1] olacaq.

İki variantdan xilas edilən zirvələrin sayının çox olduğu variant seçilməlidir.

Dərinliklə axtarış prosesini, $(v, t o)$ (v, to) kənarı nəzərə alındığı zaman nəzərdən keçirək.

Qoy $a$ - $v$ zirvəsinin ikinci oğulu olsun. Biz $d p [t o] + s u m [a] - 1$ dp[to] + sum[a] - 1 dəyərini hesablamalıyıq. Onu yalnız $v$ və $t o$ zirvələrini istifadə edərək tapaq. Belə bilirik ki,

s u m [v] = 1 + s u m [t o] + s u m [a]

sum[v] = 1 + sum[to] + sum[a]

Buradan

s u m [a] = s u m [v] - s u m [t o] - 1

sum[a] = sum[v] - sum[to] - 1

Buna görə də,

d p [t o] + s u m [a] - 1 = d p [t o] + s u m [v] - s u m [t o] - 2

dp[to] + sum[a] - 1 = dp[to] + sum[v] - sum[to] - 2

$v$ zirvəsinin oğulları üzərində iterasiya edərək hesablayırıq

d p [v] = ma x (d p [t o] + s u m [v] - s u m [t o] - 2)

dp[v] = max(dp[to] + sum[v] - sum[to] - 2)

Məsələn

Birinci nümunədə Hüseyn $3$ və $4$ nömrəli zirvələri xilas edə bilər, birinci gedişində $2$ nömrəli zirvəni seçməklə.

İkinci nümunəni nəzərə alaq. Hər bir $v$ zirvəsinin yanında $s u m [v] / d p [v]$ sum[v] / dp[v] işarələrini qoyaq. Hüseyn tərəfindən seçilən zirvələr yaşıl rənglərlə göstərilmişdir.

Məsələn,

d p [1] = ma x (s u m [2] - 1 + d p [5], s u m [5] - 1 + d p [2]) = ma x (2, 2) = 2, s u m [1] = 1 + s u m [2] + s u m [5] = 1 + 3 + 3 = 7

dp[1] = max(sum[2] - 1 + dp[5], sum[5] - 1 + dp[2]) = max(2, 2) = 2, \\ sum[1] = 1 + sum[2] + sum[5] = 1 + 3 + 3 = 7

Alqoritmin həyata keçirilməsi

İşçi massivləri elan edək.

#define MAX 300005
int sum[MAX], dp[MAX];
vector<vector<int>> g;

dfs funksiyası $v$ zirvəsindən dərinlik axtarışını həyata keçirir. $v$ zirvəsinin atası $p$ -dir.

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

$s u m [v]$ və $d p [v]$ dəyərlərini startlaşdırırıq.

  sum[v] = 1;
  dp[v] = 0;

$v$ zirvəsinin oğullarından dərinlik axtarışını başlayırıq.

  for (int to : g[v])
    if (to != p)
    {
      dfs(to, v);
      sum[v] += sum[to];
    }

$d p [v]$ dəyərini hesablayırıq.

  for (int to : g[v])
    if (to != p)
    {
      dp[v] = max(dp[v], sum[to] - 1); // əgər 1 oğul varsa
      dp[v] = max(dp[v], dp[to] + sum[v] - sum[to] - 2);
    }
}

C++

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

scanf("%d", &n);
g.clear(); g.resize(n + 1);
memset(dp, 0, sizeof(dp));
memset(sum, 0, sizeof(sum));
for (i = 1; i < n; i++)
{
  scanf("%d %d", &u, &v);
  g[u].push_back(v);
  g[v].push_back(u);
}

C++

1 nömrəli zirvədən dərinlik axtarışına başlayırıq.

dfs(1);

Cavabı çıxarırıq.

printf("%d\n", dp[1]);