Tetonun Emosiyaları#12449

Tetonun Emosiyaları (Həll təhlili)

Məsələnin müəllifi:	Taras Derkach
Hazırlayan:	Taras Derkach
İzah:	Taras Derkach

Həll

Mərkəzi olaraq seçdiyimiz $v$ təpəsini fiksə edək.

Bundan sonra $v$ təpəsindən məsafəsi tam olaraq $2$ olan bütün təpələr silinir.

Görək hansı bağlı komponentlər qalır.

Birinci komponent həmişə $v$ təpəsinin özünü və onun bütün qonşularını ehtiva edir. Onun cəmini $ce n t e r_{v}$ center_v kimi işarə edək:

ce n t e r_{v} = a_{v} + u \in a d j_{v} \sum a_{u} .

center_v = a_v + \sum_{u \in adj_v} a_u.

Digər komponentlər yalnız silinmiş təpələrin arxasında yarana bilər.

Qoy $u$ təpəsi $v$ təpəsinin qonşusu olsun, $x$ isə $u$ təpəsinin qonşusu olsun və $x \neq = v$ x \ne v.

Onda $x$ təpəsi $v$ təpəsindən tam olaraq $2$ məsafədə yerləşir, buna görə də silinir. $x$ silindikdən sonra onun digər qonşularının arxasında yerləşən komponentlər qala bilər.

Deməli, bizə belə bir qiyməti tez tapmaq lazımdır:

əgər $(x, y)$ kənarı varsa, bu kənarı sildikdə $y$ təpəsi tərəfində yerləşən komponentin cəmi nə qədərdir.

Bu cəmi $s i d e (x, y)$ side(x,y) kimi işarə edək.

Əgər ağacı $1$ təpəsində kökləndirsək, $s i d e (x, y)$ side(x,y) qiymətini alt ağac cəmləri ilə asanlıqla hesablamaq olar:

əgər $y$ təpəsi $x$ təpəsinin övladıdırsa, onda $s i d e (x, y) = s u b t r e e_{y}$ side(x,y) = subtree_y;
əks halda, $s i d e (x, y) = t o t a l - s u b t r e e_{x}$ side(x,y) = total - subtree_x.

Hər $x$ təpəsi üçün bütün qonşular $y$ üzrə $s i d e (x, y)$ side(x,y) qiymətlərinin içindən iki ən kiçik və iki ən böyük qiyməti saxlayacağıq.

Niyə iki? Çünki bəzən ən yaxşı qiyməti götürmək lazımdır, amma konkret bir istiqaməti qadağan etmək lazımdır. Məsələn, silinmiş $x$ təpəsinə baxanda $u$ təpəsinə geri gedən istiqaməti götürmək olmaz, çünki $x$ təpəsinə həmin istiqamətdən gəlmişik.

Sonra hər $u$ təpəsi üçün $u$ təpəsinin hansısa qonşusu $x$ silindikdən sonra yarana bilən komponentlərin ən kiçik və ən böyük cəmlərini saxlayacağıq.

Başqa sözlə, $u$ təpəsinin hər qonşusu $x$ üçün $x$ təpəsinin arxasındakı ən yaxşı komponenti götürürük, amma $u$ təpəsinə geri gedən istiqaməti götürmürük.

Bu hazırlıqdan sonra konkret mərkəzi $v$ təpəsi üçün cavabı tez tapmaq olar.

Əvvəlcə $ce n t e r_{v}$ center_v cəminə malik komponentimiz var.

Sonra $v$ təpəsinin hər qonşusu $u$ üçün $u$ təpəsinin arxasında yerləşən təpələrdən yarana biləcək ən kiçik və ən böyük komponenti götürürük. Bu zaman $v$ təpəsinə geri gedən istiqaməti qadağan etmək lazımdır.

Tapılan bütün komponentlər arasında minimum və maksimum cəmi tapırıq. $v$ təpəsi üçün kontrast belə olur:

ma x S u m - min S u m .

maxSum - minSum.

Cavab bütün $v$ təpələri üzrə bu qiymətin maksimumudur.

Nümunə

Birinci nümunədə optimal olaraq $v = 4$ v = 4 təpəsini seçmək olar.

Onda $2$ təpəsi ondan tam olaraq $2$ məsafədə yerləşir, buna görə də silinir.

Silindikdən sonra iki bağlı komponent qalır:

cəmi $1$ olan ${1}$ komponenti;
cəmi $3 + 4 + 5 = 12$ 3 + 4 + 5 = 12 olan ${3, 4, 5}$ \{3,4,5\} komponenti.

Beləliklə, kontrast belə olur:

12 - 1 = 11.

12 - 1 = 11.

Mürəkkəblik

Alt ağac cəmlərini bir dəfə hesablayırıq, bundan sonra hər təpə üçün onun qonşularına baxırıq.

Hər kənar yalnız sabit sayda dəfə emal olunur.

Buna görə həllin mürəkkəbliyi $O (n)$ -dir.