5. Bezkonkurenčná manufaktúra vzorové riešenie

7
0 1
1 2
2 3
2 4
4 5
4 6

11 5

Zadanie úlohy nám popisuje graf v tvare stromu a nariaďuje nájsť určitý kritický vrchol. Tento vrchol sa nachádza na ceste medzi najväčším počtom dvojíc. Otázkou je, koľko dvojíc to je (nazvime túto vlastnosť dôležitosť) a koľko dvojíc to bude, ak môžeme pridať jednu dodatočnú hranu (dôležitosť s dodatočnou hranou). Otázka na koľkých cestách sa nachádza vrchol je ekvivalentná otázke, koľko ciest sa preruší keď ho odstránime.

Triviálny bruteforce

Na začiatok navrhnime kľudne aj pomalé riešenie, ktoré nám však dá aspoň správny výsledok. Pre odpoveď na prvú otázku, môžeme skúsiť odstrániť každý možný vrchol a potom pre každú možnú dvojicu spustiť prehľadávací algoritmus (DFS, BFS, …), ktorý nám povie, či sú tieto dva vrcholy spojené. Keďže pred odstránením kritického vrcholu nutne spojené museli byť, počet dvojíc čo spojené nebudú bude dôležitosť tohoto vrcholu. Vrchol s najvyššou dôležitosťou je potom kritický vrchol. Toto vieme spraviť v čase \(O(N^4)\), keďže pre každý vrchol a každú dvojicu spustíme prehľadávanie v \(O(N)\).

Jednoduché vylepšenie bude spustiť prehľadávanie nie pre každú dvojicu, ale iba pre každý vrchol, keďže počas jedného vyhľadávania nájdeme všetky dosiahnuteľné vrcholy. Dostávame sa teda k časovej zložitosti \(O(N^3)\) na zodpovedanie prvej otázky.

Pri zodpovedaní druhej otázky už poznáme kritický vrchol. Môžeme teda napríklad pre každú dvojicu vrcholov skúsiť pridať hranu a znova zistiť dôležitosť vrchola v čase \(O(N^2)\), čím by sme získali celkovú časovú zložitosť \(O(N^4)\).

Netriviálny bruteforce

Zamyslime sa, čo sa stane, ak odstránime tento kritický vrchol. Strom sa rozpadne na niekoľko súvislých komponentov, ich počet bude rovný počtu susedov kritického vrcholu. Samozrejme, z definície súvislého komponentu, všetky dvojice vrcholov v rámci jednotlivých komponentoch medzi sebou naďalej budú mať cestu (Mohli sme si všimnúť, že keď sme pri zodpovedaní prvej otázky robili prehľadávanie, veľa vrcholov malo rovnaký počet dosiahnuteľných vrcholov, keďže boli v tom istom komponente. Ďalšie vylepšenie je teda púštať prehľadávanie iba pre ešte nenavštívené vrcholy). Cesty, ktoré sa odstránením kritického vrcholu narušia budú teda nutne iba cesty medzi vrcholmi z dvoch rôznych komponentov.

To znamená, že nezáleží na konkrétnych koncových vrcholoch pridávanej hrany, ale iba na tom, ktoré komponenty daná hrana spája. Mohli by sme teda naše doterajšie riešenie zoptimalizovať tak, aby neskúšalo všetky dvojice vrcholov, ale iba všetky dvojice susedov kritického vrcholu. Keďže však môže mať vrchol až \(N-1\) susedov, počet dvojíc susedov je stále \(O(N^2)\), a teda si z pohľadu efektivity nepomôžeme. Predsa nám však toto uvedomenie pomôže.

Cesty, ktoré sa prerušia odstránením kritického vrcholu sú iba cesty medzi vrcholmi z dvoch rôznych komponentov a cesta bude prerušená všetkým takýmto dvojiciam vrcholov. Dôležitosť vrcholu sa teda dá vyjadriť iba na základe veľkosti komponentov jeho susedov. Nech množina susedov kritického vrcholu je \(S\) a \(K_x\) je veľkosť komponentu, v ktorom je sused \(x\), potom dôležitosť daného vrcholu je ¹ \[ {1 \over 2} \sum_{i, j \in S, i \neq j} K_i * K_j \] teda súčin počtu vrcholov v jednom komponente a počtu v vrcholov v druhom komponente pre každú dvojicu komponentov (predelený dvomi, keďže komponent \(A\) a \(B\) boli zarátané pre \(i=A, j=B\) a \(i=B, j=A\)).

Zmysluplným pridaním hrany vieme spojiť práve dva komponenty. Keďže chceme minimalizovať dôležitosť vrcholu, chceme maximalizovať počet dvojíc vrcholov, ktoré ňou prepojíme. Zjavne chceme teda vybrať dva najväčšie komponenty.

Znovu vieme zoptimalizovať náš aktuálny algoritmus. Na zodpovedanie druhej otázky môžeme ľubovoľným prehľadávaním nájsť veľkosti jednotlivých komponentov pre už nájdený kritický vrchol, vybrať dva najväčšie z nich a znížiť odpoveď prvej otázky o ich súčin. Toto vieme spraviť v lineárnom čase. Celková časová zložitosť bude kvôli zodpovedaniu prvej otázky \(O(N^3)\).

Zjavne je teraz hrdlom fľaše nájdenie kritického vrcholu. Môžeme takéto lineárne hľadanie veľkosti komponentov použiť pre každý vrchol, a teda v čase \(O(N^2)\). Následne by sme pre každý vrchol v čase \(O(s^2)\) kde \(s\) je počet jeho susedov vypočítali jeho dôležitosť. Dá sa ukázať, že aj keď pre \(N\) vrcholov robíme po \(O(s^2)\) operácií, celková časová zložitosť je stále \(O(N^2)\) (dôležité pri analýze časovej zložitosti je, že graf je strom a má teda iba málo hrán).

Optimálne riešenie

Aktuálne máme dva problémy. Hľadanie veľkosti komponentov nám trvá \(O(N^2)\) a počítanie dôležitosti pre vrchol nám trvá \(O(s^2)\). Ani jeden problém však našťastie nie až také ťažké vyriešiť.

Chceme veľkosti komponentov vypočítať na jeden prechod. Spustíme z koreňa DFS prehľadávanie, ktoré nám pre každý vrchol zistí, koľko vrcholov je v jeho podstrome. Robíme to rekurzívne. Pre vrchol, ktorý už nemá deti je odpoveď \(1\), pre vrchol čo má deti je odpoveď súčet výsledkov rekurzívnych volaní na jeho deti plus \(1\). Pre každý vrchol sa vieme pozrieť na veľkosti podstromov jeho detí, čo sú predsa veľkosti komponentov jeho susedov. Chýba nám iba veľkosť jedného komponentu a to komponentu suseda, ktorý je náš rodič. Jeho veľkosť však vieme samozrejme ľahko vypočítať ako počet vrcholov v strome mínus veľkosť podstromu aktuálneho vrcholu. Časová zložitosť tejto časti je teda \(O(N)\).

Druhý problém si zase vyžaduje trochu matematiky. Pozrime sa na vzorec, podľa ktorého sme to počítali doteraz a skúsme ho upraviť.

\[\begin{align*} &{1 \over 2} \sum_{i, j \in S, i \neq j} K_i * K_j \\ &{1 \over 2} \sum_{i\in S} \sum_{j \in S, i \neq j} K_i * K_j \\ &{1 \over 2} \sum_{i \in S} (K_i *\sum_{j \in S, i \neq j} K_j) \\ &{1 \over 2} \sum_{i \in S} K_i * (-K_i +\sum_{j \in S} K_j) \\ &{1 \over 2} \sum_{i \in S} K_i * (-K_i + (N - 1)) \\ &{1 \over 2} \sum_{i \in S} (K_i * (N - 1) - K_i^2) \\ &{1 \over 2} (\sum_{i\in S} K_i * (N - 1) - \sum_{i \in S} K_i^2) \\ &{1 \over 2} ((N - 1) *\sum_{i \in S} K_i - \sum_{i \in S} K_i^2) \\ &{1 \over 2} ((N - 1)^2 -\sum_{i \in S} K_i^2) \end{align*}\]

Pri úpravách sme použili dve netriviálne úpravy vo forme rovností:

1. \(\sum_{j \in S, i \neq j} K_j = -K_i + \sum_{j\in S} K_j\), teda že súčet veľkostí všetkých susedných komponentov až na komponent suseda \(i\) je súčet všetkých mínus veľkosť toho jedného a
2. \(\sum_{x \in S} K_x = N - 1\), teda že súčet veľkostí všetkých susedných komponentov je počet všetkých vrcholov okrem jedného vrcholu (toho kritického).

No a vidno, že takýto vzorec už zvládame vypočítať v lineárnom čase od počtu susedov pre každý vrchol, čo je dokopy iba dvojnásobok počtu hrán. Celková časová aj pamäťová zložitosť je teda \(O(N)\).

import sys
sys.setrecursionlimit(10 ** 6)

N = int(input())

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

odpovede = [0, 0]

def nechaj_najvacsie(najvacsie_dva, nove):
    return sorted(najvacsie_dva + [nove])[1:]

def dfs(aktualny_vrchol, otec):
    global odpovede

    velkost_podstromu, sucet_stvorcov_velkosti, najvacsie_dva = 1, 0, [0] * 2
    for sused in graf[aktualny_vrchol]:
        if sused == otec:
            continue
        velkost_synovho_podstromu = dfs(sused, aktualny_vrchol)
        velkost_podstromu += velkost_synovho_podstromu
        sucet_stvorcov_velkosti += velkost_synovho_podstromu ** 2
        najvacsie_dva = nechaj_najvacsie(najvacsie_dva, velkost_synovho_podstromu)
    if otec is not None:
        velkost_synovho_podstromu = N - velkost_podstromu
        sucet_stvorcov_velkosti += velkost_synovho_podstromu ** 2
        najvacsie_dva = nechaj_najvacsie(najvacsie_dva, velkost_synovho_podstromu)

    dolezitost = ((N - 1) ** 2 - sucet_stvorcov_velkosti) // 2
    if dolezitost > odpovede[0]:
        odpovede = dolezitost, dolezitost - najvacsie_dva[0] * najvacsie_dva[1]

    return velkost_podstromu

dfs(0, None)
print(*odpovede)

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

ll N;
vector<vector<ll>> graf;
pair<ll, ll> odpovede = {0, 0};

ll sqr(ll x) { return x * x; }

void nechaj_najvacsie(pair<ll, ll>& najvacsie_dva, ll nove) {
    if (nove >= najvacsie_dva.first)
        najvacsie_dva = {nove, najvacsie_dva.first};
    else if (nove > najvacsie_dva.second)
        najvacsie_dva = {najvacsie_dva.first, nove};
}

ll dfs(ll aktualny_vrchol, ll otec) {
    ll velkost_podstromu = 1;
    ll sucet_stvorcov_velkosti = 0;
    pair<ll, ll> najvacsie_dva = {0, 0};
    for (ll sused : graf[aktualny_vrchol]) {
        if (sused == otec)
            continue;
        ll velkost_synovho_podstromu = dfs(sused, aktualny_vrchol);
        velkost_podstromu += velkost_synovho_podstromu;
        sucet_stvorcov_velkosti += sqr(velkost_synovho_podstromu);
        nechaj_najvacsie(najvacsie_dva, velkost_synovho_podstromu);
    }
    if (otec != -1) {
        ll velkost_synovho_podstromu = N - velkost_podstromu;
        sucet_stvorcov_velkosti += sqr(velkost_synovho_podstromu);
        nechaj_najvacsie(najvacsie_dva, velkost_synovho_podstromu);
    }

    ll dolezitost = (sqr(N - 1) - sucet_stvorcov_velkosti) / 2;
    if (dolezitost > odpovede.first)
        odpovede = {dolezitost,
                    dolezitost - najvacsie_dva.first * najvacsie_dva.second};

    return velkost_podstromu;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    graf.resize(N);
    for (ll i = 0; i < N - 1; ++i) {
        ll a, b;
        cin >> a >> b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }

    dfs(0, -1);
    cout << odpovede.first << " " << odpovede.second << "\n";
}