6. TokTik Mačiatka vzorové riešenie

5
15 20 13 24 19
0 3
1 2
2 3
3 4

54

Najprv rýchle odrozprávkovanie zadania. Máme strom s ohodnotenými vrcholmi. Chceme vybrať nejakú množinu vrcholov s čo najväčším súčtom hodnôt tak, aby žiadne dva vrcholy v našej vybranej množine boli spojené hranou. Bude takúto nejakú množinu vrcholov volať pokrytie, a súčet hodnôt vrcholov v tomto pokrytí budem volať hodnota pokrytia. Ak pokrytie zároveň splňuje podmienku zo zadania, teda že žiadne dva vrcholy v pokrytí nesmú byť spojené hranou, budem ho volať platné pokrytie.

Bruteforce

Najprv rýchlo spomenieme pomerne neefektívny algoritmus hrubej sily, ktorý rieši prvú sadu - vyskúšame ním všetky možnosti. Počet vrcholov je iba malý, takže môžeme jednoducho vyskúšať všetky možné pokrytia, pre každé skontrolovať, či je platné, a vybrať to s najväčšou hodnotou. Počet takýchto pokrytí je však pomerne veľký, pretože každý vrchol môže v každom pokrytí buď byť, alebo nebyť. Počet pokrytí je teda \(2^n\), a pre každé pokrytie treba ešte skontrolovať, či je platné. To vieme spraviť jedným prechodom stromu, čiže nejaké DFS. Celková časová zložitosť teda bude \(O(n \cdot 2^n)\), čo stačí na prvú sadu.

Greedy riešenie tretej sady

Pred riešením na plný počet bodov sa ešte poďme pozrieť na riešenie tretej sady, kde mali všetky vrcholy rovnakú hodnotu. Táto sada sa dala vyriešiť greedy (pažravým) riešením. Vieme si totiž uvedomiť, že v optimálnemu pokrytiu totiž určite neuškodí, ak doňho zahrnieme nejaký list stromu. Zakoreňme si strom a povedzme, že vrchol \(A\) je list a jeho rodič je vrchol \(B\). V optimálnom pokrytí určite chceme mať buď vrchol \(A\), alebo vrchol \(B\), a to práve jeden z nich. Ak do pokrytia zahrnieme vrchol \(A\), vieme, že nič okrem vrcholu \(B\) tým neobmedzíme. Naopak, ak vezmeme vrchol \(B\), môže sa stať, že si uškodíme na iných miestach. Teda vždy sa nám oplatí vziať list \(A\), a poznamenať si, že \(B\) zobrať nemôžeme. Inými slovami, ak zoberieme rodiča listu, tak skóre si vylepšíme rovnako, ale vrcholy, ktoré sú v pokrytí, alebo ich nemôžeme zobrať, budú stále nadmnožina vrcholov v pokrytí, alebo vrcholov ktoré nemôžeme zobrať ak zoberieme list. Teda nedosiahneme lepšie riešenie ako keď zoberieme list. No ale ak už sme teda nejaký list do pokrytia zahrnuli, tak nás už až tak nazaujíma, tak ho môžeme zo stromu odpojiť. Toto nám zachová strom, teda určite bude existovať nejaký iný list na spracovanie.

Algoritmus teda postupuje nasledovne: budeme si udržiavať stack listov na spracovanie. Vždy so spracovaným listom spravíme nasledovné: ak sme si niekedy poznamenali, že ho vziať nemôžeme, tak nič nerobíme, ak nie, zahrnieme ho do pokrytia a pre jeho rodiča si poznamenáme, že ho nemôžeme zobrať. Potom tento list odstránime, updatneme rodiča, a ak sa rodič práve stal listom, zaradíme rodiča do stacku listov na spracovanie. Tento algoritmus beží v \(O(n)\) a k riešeniu na plný počet bodov nám nepomôže, avšak je fajn vedieť, že sa podúloha dá riešiť aj takto.

Čo s cestou?

Presuňmne sa zaujímavejšej sade - sade 2. V tejto sade máme garantované, že graf je cesta, čo však znamená, nemusíme rozmýšľať nad nijakým grafom. Jednoducho si úlohu pretransformujeme na nasledovnú: máme pole čísel, a chceme z nich vybrať množinu čísel čo najväčšiu v súčte, avšak žiadne dva vybraté prvky nemôžu byť susedné. Veľa z vám táto úloha príde pomerne povedomá - nachádza sa totiž na testovači, prípadne sme ju vedeli nájsť aj v tohtoročných zadaniach Kasiopei. Táto úloha sa dá riešiť dynamickým programovaním.

Myšlienka dynamického programovania

Budeme postupne počítať najlepšie pokrytie pre časť poľa. Pre prvok \(i\) budeme chcieť vypočítať hodnoty \(B\) (beriem) a \(N\) (neberiem). Hodnota \(B[i]\) nám hovorí, aký najväčší súčet vieme dostať pre nejaké pokrytie prvých \(i\) prvkov, pričom prvok \(i\) sa v pokrytí určite nachádza. Naopak, hodnota \(N\) nám hovorí, aký najväčší súčet môžeme dostať pre prvých \(i\) prvkov, ak sa v prvok \(i\) v pokrytí určite nenachádza. Ako vieme tieto hodnoty vypočítať?

Predpokladajme, že poznáme hodnoty \(B[i-1]\) a \(N[i-1]\). Vieme, že pri pokrytí, kde určite berieme \(i\)-tý prvok, musí byť \(i-1\)vý prvok nezobraný, ale zároveň chceme prvých \(i-1\) prvkov vybrať optimálne. To však vieme, poznáme predsa hodnotu \(N[i-1]\). Teda vieme povedať, že \(B[i] = N[i-1] + hodnota[i]\). Podobne vieme vypočítať \(N[i]\). Vieme totiž, že ak určite neberieme \(i\)-tý prvok, môžeme si prvých \(i-1\) prvkov navoliť ľubovoľne, tak aby boli optimálne. Teda \(N[i] = max(B[i-1],N[i-1])\).

Teda sme si ukázali, že vieme hodnoty \(B[i]\) a \(N[i]\) vypočítať iba s vedomosťou hodnôt \(B[i-1]\) a \(N[i-1]\). Vieme potom povedať, že \(B[0] = hodnota(0)\) a \(N[0] = 0\). No ale z týchto dvoch hodnôt vieme vypočítať hodnoty \(B\) a \(N\) pre všetky prvky v poli, pretože z hodnôt pre prvok \(0\) si vieme vypočítať hodnoty pre prvok \(1\), z tých pre prvok \(2\)… a tak ďalej. Pre každé políčko tiež vypočítame iba dve rovnice, čiže časová zložitosť programu bude \(O(n)\).

Optimálne riešenie - dynamika na stromoch

Čo však s riešením na plný počet bodov? Zakoreňme si strom, a z predošlého odseku si odnesme jednu kľúčovú myšlienku - aj v strome vieme totiž efektívne rátať hodnoty \(B\) a \(N\), ktoré však budú mať v strome trochu lepšiu definíciu. \(B[X]\) bude najlepšie pokrytie podstromu vrcholu \(X\) také, že \(X\) berieme (teda sa nachádza v pokrytí). \(N[X]\) bude podobne najlepšie pokrytie podstromu vrcholu \(X\) také, že \(X\) neberieme (teda sa v pokrytí nenachádza). Poďme si teda tiež upraviť vzorček pre dynamické programovanie.

Povedzme, že chceme hodnoty \(B\) a \(N\) vypočítať pre nejaký vrchol \(A\), a predpokladajme, že poznáme hodnoty \(B\) a \(N\) pre všetkých jeho synov. Potom ak chceme vypočítať hodnotu \(B[A]\), tak vieme, že pre tento prípad musia byť všetci synovia tohoto vrcholu nezobraní, pretože vrchol \(A\) zobraný je. Preto viem jednoducho sčítať hodnoty \(N\) pre synov vrcholu \(A\), pripočítať k tomu hodnotu \(A\), a tento výsledok bude žiadané \(B[A]\).

\(N[A]\) vieme tiež vyriešiť podobne ako predtým. Opäť platí, že tým, že vrchol \(A\) neberieme, vieme si pre každého jeho syna vybrať to najoptimálnejšie pokrytie, bez žiadnych iných obmedzení. Preto pre každého syna \(S\) vrcholu \(A\) vypočítame hodnotu \(max(B[S],N[S])\), a tieto hodnoty sčítame. To bude hodnota \(N[A]\). Nakoniec si vieme rozmyslieť, že ak vrchol nemá synov, vieme pre neho vypočítať hodnoty \(B\) a \(N\) veľmi jednoducho, a teda pre list \(i\) bude \(B[i] = hodnota(i)\) a \(N[i] = 0\). A ak nejaký vrchol synov má, jeho optimálne hodnoty \(B\) a \(N\) vieme vypočítať vyššie popísaným spôsobom.

Ako to nakódiť? Ukáže sa, že pomerne jednoducho. Stačí spustiť funkciu \(DFS\), ktorá pre zavolanie do nejakého vrcholu vráti dve hodnoty - \(B\) a \(N\) tohoto vrcholu. Tieto hodnoty spočítame pekne rekurzívne, až kým v koreni nedostaneme výsledok.

A nakoniec: akú časovú zložitosť bude mať toto riešenie? \(DFS\) funkcia sa zavolá do každého vrcholu raz, pričom v každom vrchole bude rekurzívne dostávať hodnoty \(B\) a \(N\) pre synov tohoto vrcholu. Tieto hodnoty si iba upravíme a sčítame ako popísané vyššie. Náš algoritmus bude mať teda časovú zložitosť \(O(n)\).

import sys
sys.setrecursionlimit(10**6)

pct = int(input())
uzitocnost = list(map(int,input().split()))
graf = [[] for _ in range(pct)]

def dfs(vtx, parent):
    on = uzitocnost[vtx]
    off = 0
    for to in graf[vtx]:
        if to != parent:
            x = dfs(to, vtx)
            on += x[0]
            off += max(x[0], x[1])
    return [off, on]

for i in range(pct-1):
    frm, to = list(map(int,input().split()))
    graf[frm].append(to)
    graf[to].append(frm)
    
f = dfs(0,0)
print(max(f[0],f[1]))

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<ll> uzitocnost;
vector<vector<int>> graf;

pair <ll, ll> dfsko(int vtx, int parent) {
    ll zapnuty = uzitocnost[vtx];
    ll vypnuty = 0;

    for (int i = 0; i < graf[vtx].size(); i++)
    {
        int to = graf[vtx][i];
        if (to != parent)
        {
            pair <ll,ll> vals = dfsko(to, vtx);
            zapnuty += vals.first;
            vypnuty += max(vals.first, vals.second);
        }
        
    }
    
    return {vypnuty, zapnuty};
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int N;
    cin >> N;

    uzitocnost.resize(N);
    graf.resize(N);

    for (int i = 0; i < N; i++)
    {
        ll x; cin >> x;
        uzitocnost[i] = x;
    }
    
    
    for (int i = 0; i < N-1; i++)
    {
        int from, to;
        cin >> from >> to;
        graf[to].push_back(from);
        graf[from].push_back(to);
    }
    
    pair <ll,ll> vysledok = dfsko(0,0);
    cout << max(vysledok.first, vysledok.second) << endl;
}