Təcrübələr#8724
Şirkət X-in N əməkdaşı var. Şirkət ciddi bir iyerarxik ağac strukturu ilə idarə olunur – CEO (Baş İcraçı Direktor) ən yuxarıda (ağacın kökü) dayanır və onun bir neçə birbaşa tabeliyində olan işçiləri var. Bu işçilərin də öz tabeliyində olan işçiləri var və bu belə davam edir, ta ki heç bir tabeliyində işçisi olmayan adi işçilərə (ağacın yarpaqları) çatana qədər. İşçilər 1-dən N-ə qədər tam ədədlərlə nömrələnib. CEO-nun nömrəsi 1-dir, lakin digər nömrələr iyerarxiya ilə əlaqəli deyil. Hər bir işçinin müəyyən bir təcrübəsi var – i-ci işçinin təcrübəsi, qeyri-mənfi tam ədəd W[i] ilə göstərilir.
Şirkətin tamamlamalı olduğu çox sayda qrup layihəsi var və rəhbərlik bütün işçiləri müxtəlif qruplara (komandalara) bölmək qərarına gəlib ki, aşağıdakı şərtlər təmin olunsun:
Hər bir komanda ən azı bir nəfərdən ibarət olmalıdır və hər bir şəxs dəqiq bir komandaya aid olmalıdır.
Hər bir komanda yalnız bir-birinin ardıcıl tabeliyində olan şəxslərdən ibarət olmalıdır. İşçilər qrupu j[1], j[2], j[3], j[4] … etibarlı bir komandadırsa, j[2] birbaşa j[1]-in tabeliyindədir, j[3] birbaşa j[2]-nin tabeliyindədir, j[4] birbaşa j[3]-ün tabeliyindədir və s.
Rəhbərlik bilir ki, bir qrup layihəsi tamamlandıqdan sonra, layihəyə təyin olunan qrupun ümumi təcrübəsi Wmax - Wmin qədər artır, burada Wmax qrup üzvləri arasında ən yüksək təcrübədir və Wmin ən aşağı təcrübədir. Şirkət üçün ümumi təcrübə artımı bütün komandaların təcrübə artımlarının cəminə bərabərdir. Rəhbərlik, yuxarıda qeyd olunan iki şərtə uyğun olaraq, işçiləri ən yaxşı mümkün komandalar konfiqurasiyasına bölməklə şirkət üçün ümumi təcrübə artımını maksimuma çatdırmaq istəyir.
Şirkət üçün mümkün olan maksimum təcrübə artımını hesablamaq üçün bir proqram yazın.
Standart girişin ilk sətri şirkətdəki işçilərin sayı olan tək tam ədəd N-i ehtiva edir (1 ≤ N ≤ 10^5).
İkinci sətir şirkətin hər bir işçisinin təcrübəsini göstərən N boşluqla ayrılmış qeyri-mənfi tam ədədləri W[1], W[2], ..., W[N] ehtiva edir (0 ≤ W[i] ≤ 10^9).
Sonra N-1 sətir gəlir, hər biri boşluqla ayrılmış u və v tam ədədlərini ehtiva edir. Bu ədədlər şirkətdəki tabelik əlaqələrini göstərir – v nömrəli işçi u nömrəli işçinin birbaşa tabeliyindədir.
Proqram standart çıxışa bir tam ədəd çap etməlidir – şirkət üçün maksimum ümumi təcrübə artımı.
Ümumi təcrübə artımını maksimuma çatdıran mümkün konfiqurasiyalardan biri {1, 5, 3}, {6, 2, 4}, {7}.
Eyni maksimal ümumi təcrübə artımı ilə başqa bir konfiqurasiya da var – {1, 5}, {3}, {6, 2, 4}, {7}.
Nümunə 1