Maksimal məbləğ ağacda#973

Maksimal məbləğ ağacda (Həll təhlili)

Güman edək ki, $v$ — ağacın zirvəsidir. Aşağıdakıları qeyd edək:

$d p_{1} (v)$ dp_1(v) zirvə $v$ -dəki pulları götürdüyümüz halda, kökü $v$ olan alt ağacdan toplaya biləcəyimiz ən böyük pul məbləğidir.
$d p_{2} (v)$ dp_2(v) zirvə $v$ -dəki pulları götürmədiyimiz halda, kökü $v$ olan alt ağacdan toplaya biləcəyimiz ən böyük pul məbləğidir.

Beləliklə, problemi cavabı, zirvə $1$ -i ağacın kökü kimi qəbul etdikdə, $ma x (d p_{1} (1), d p_{2} (1))$ max(dp_1(1), dp_2(1)) olacaq.

Tərtib olunan funksiyaları rekursiv olaraq təyin edək:

Zirvə $v$ -dəki pulları götürsək, onun oğlanlarından pulları götürmək olmaz:

d p_{1} (v) = c_{v} + i = 1 \sum k d p_{2} (t o_{i}), b u r a d a t o_{1}, ..., t o_{k} - z i r v ə nin v o g ˘ l an l a r ı d ı r .

dp_1(v) = c_v + \sum_{i=1}^k dp_2(to_i) , burada~to_1, ..., to_k - zirvənin~v~oğlanlarıdır.

Zirvə $v$ -dəki pulları götürməsək, oğlanlarından pulları ya götürmək, ya da götürməmək olar. Bu iki variantdan daha çox pul məbləği olan variantı seçmək lazımdır:

d p_{2} (v) = i = 1 \sum k ma x (d p_{1} (t o_{i}), d p_{2} (t o_{i})), b u r a d a t o_{1}, ..., t o_{k} - z i r v ə nin v o g ˘ l an l a r ı d ı r .

dp_2(v) = \sum_{i=1}^k max(dp_1(to_i), dp_2(to_i)), burada~to_1, ..., to_k - zirvənin~v~oğlanlarıdır.

Əgər $v$ - $c_{v}$ c_v pulu olan bir yarpaqdırsa, onda funksiyalar aşağıdakı qiymətləri alacaq: $d p_{1} (v) = c_{v}$ dp_1(v) = c_v və $d p_{2} (v) = 0$ dp_2(v) = 0.

Nümunə

Zirvələrdəki $d p_{1} (v) / d p_{2} (v)$ dp_1(v) / dp_2(v) etiketlərini qoyaq nümunələrin ağaclarına.

Birinci nümunə üçün:

$d p_{1} (1) = c_{1} + d p_{2} (2) + d p_{2} (3) = 1 + 3 + 0 = 4$ dp_1(1) = c_1 + dp_2(2) + dp_2(3) = 1 + 3 + 0 = 4;
$d p_{2} (1) = ma x (d p_{1} (2), d p_{2} (2)) + ma x (d p_{1} (3), d p_{2} (3)) = 5 + 7 = 12$ dp_2(1) = max(dp_1(2), dp_2(2)) + max(dp_1(3), dp_2(3)) = 5 + 7 = 12;
$d p_{1} (2) = c_{2} + d p_{2} (4) + d p_{2} (5) = 5 + 0 + 0 = 5$ dp_1(2) = c_2 + dp_2(4) + dp_2(5) = 5 + 0 + 0 = 5;
$d p_{2} (2) = ma x (d p_{1} (4), d p_{2} (4)) + ma x (d p_{1} (5), d p_{2} (5)) = 1 + 2 = 3$ dp_2(2) = max(dp_1(4), dp_2(4)) + max(dp_1(5), dp_2(5)) = 1 + 2 = 3;

İkinci nümunə üçün:

$d p 1 (1) = c_{1} + d p_{2} (2) + d p_{2} (3) = 3 + 11 + 0 = 14$ dp1(1) = c_1 + dp_2(2) + dp_2(3) = 3 + 11 + 0 = 14;
$d p_{2} (1) = ma x (d p_{1} (2), d p_{2} (2)) + ma x (d p_{1} (3), d p_{2} (3)) = 11 + 5 = 16$ dp_2(1) = max(dp_1(2), dp_2(2)) + max(dp_1(3), dp_2(3)) = 11 + 5 = 16;
$d p_{1} (2) = c_{2} + d p_{2} (4) + d p_{2} (5) = 7 + 0 + 0 = 7$ dp_1(2) = c_2 + dp_2(4) + dp_2(5) = 7 + 0 + 0 = 7;
$d p_{2} (2) = ma x (d p_{1} (4), d p_{2} (4)) + ma x (d p_{1} (5), d p_{2} (5)) = 10 + 1 = 11$ dp_2(2) = max(dp_1(4), dp_2(4)) + max(dp_1(5), dp_2(5)) = 10 + 1 = 11;

Tapşırıq

Ağacın zirvələrində $d p_{1} (v) / d p_{2} (v)$ dp_1(v) / dp_2(v) etiketlərini qoyun:

Alqoritmin həyata keçirilməsi

İş səviyyələri elan edək.

vector<vector<int> > g;
vector<int> dp1, dp2, cost;

dfs funksiyası dərinliyi axtarışı həyata keçirir. $d p_{1}$ dp_1 və $d p_{2}$ dp_2 qiymətlərini ağacın bütün zirvələrində hesablayaq.

void dfs(int v, int p = -1)
{
  dp1[v] = cost[v];
  dp2[v] = 0;

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

    dfs(to, v);

    dp1[v] += dp2[to];
    dp2[v] += max(dp1[to], dp2[to]);
  }
}

C++

Proqramın əsas hissəsi. Ağacı və pul səviyyəsini oxuyuruq.

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

dp1.resize(n+1); dp2.resize(n+1);
cost.resize(n+1);
for(i = 1; i <= n; i++)
  scanf("%d",&cost[i]);

C++

Tutaq ki, ağacın kökü zirvə $1$ -də yerləşir. Oradan dərindən axtarışa başlayırıq.

dfs(1);

Cavabı hesablayırıq və çıxarırıq.

ans = max(dp1[1], dp2[1]);
printf("%d\n",ans);