26678번 - Sen o podboju 다국어

Król Bajtur, władca Bajtocji, właśnie śni o podbiciu Bitocji. W jego śnie, tak jak i w prawdziwym świecie, daleko mu jeszcze do pokonania przeciwnika. Dlatego też zastanawia się, co może zrobić, aby osłabić wrogie państwo. . .

W jego śnie Bitocja składa się z n miast (ponumerowanych liczbami od 1 do n) połączonych n − 1 dwukierunkowymi drogami w taki sposób, że da się przejechać między każdą parą miast, korzystając jedynie z tych dróg. Innymi słowy, mapa Bitocji tworzy drzewo. Jednak Bajtur nie pamięta dokładnie sieci drogowej Bitocji. . . Jego mózg wygenerował więc losową sieć dróg.

Władca doszedł do wniosku, że dobrym pomysłem byłoby wymusić podział Bitocji na k mniejszych państewek. Przez podział Bajtur rozumie potajemne zniszczenie dokładnie k − 1 dróg, co zmusi Bitocję do rozpadu na k państewek, będącymi spójnymi składowymi grafu powstałego po usunięciu wybranych krawędzi.

Królowi nie wystarczy jednak zniszczenie jakichkolwiek k − 1 dróg. Każde miasto Bitocji ma współczynnik militarny równy a_i – również wylosowany przez mózg Bajtura. Bajtur wie, że im mocniejsze militarnie państwo, tym większe zagrożenie dla Bajtocji. A konkretnie: jeśli w danym państewku suma współczynników militarnych należących do niego miast jest równa S, to zagrożenie ze strony tego państewka jest równe S². Całkowite zagrożenie Bajtocji jest równe sumie zagrożeń tworzonych przez każde z k utworzonych państewek.

Teraz Bajtur zwrócił się do Ciebie – swojego wyśnionego (i to dosłownie!) programisty. Pomóż mu i oblicz, jakie minimalne całkowite zagrożenie może spowodować Bitocja po podziale na państewka. Ponieważ Bajtur nie zdecydował się jeszcze na wartość parametru k, oblicz wyniki dla wszystkich k od 1 do n włącznie.

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita t (1 ≤ t ≤ 10) oznaczająca liczbę snów Bajtura przypadków testowych. Dalej następuje opis kolejnych przypadków testowych; każdy z nich jest w tym samym formacie.

W pierwszym wierszu opisu przypadku testowego znajduje się jedna liczba całkowita n (2 ≤ n ≤ 300). W drugim wierszu znajduje się ciąg n liczb całkowitych a₁, a₂, . . . , a_n (1 ≤ a_i ≤ 10⁶). W kolejnych n − 1 wierszach znajduje się opis dróg Bitocji; w i-tym wierszu są dwie liczby całkowite b_i oraz c_i (1 ≤ b_i, c_i ≤ n) oznaczające drogę łączącą miasta o numerach b_i oraz c_i. Graf opisany w każdym przypadku testowym jest drzewem.

Bajtur wygenerował testy, ręcznie wybierając liczbę t (1 ≤ t ≤ 10), przedział liczb całkowitych [n_min, n_max] (2 ≤ n_min ≤ n_max ≤ 300) oraz wartość a_max (1 ≤ a_max ≤ 10⁶). Następnie każdy przypadek testowy został przez niego wygenerowany niezależnie w następujący sposób:

• Liczba miast n jest wybrana losowo i jednostajnie z przedziału [n_min, n_max].
• Każda liczba a₁, a₂, . . . , a_n jest wylosowana niezależnie i jednostajnie z przedziału [1, a_max].
• Generowany jest ciąg liczb naturalnych (p₁, p₂, . . . , p_n−2); każdy element ciągu jest losowany niezależnie i jednostajnie z przedziału [1, n]. Bajtur bierze jako sieć połączeń drzewo, którego kod Prüfera^∗ jest równy (p₁, p₂, . . . , p_n−2).

W dziale Pliki w systemie SIO₂ możesz znaleźć przykładowy generator testów do tego zadania. Generator przyjmuje na swoim wejściu kolejno: ziarno generatora oraz liczby t, n_min, n_max, a_max. Wszystkie testy do tego zadania zostaną wygenerowane kodem mu równoważnym (tj. z inną biblioteką liczb pseudolosowych, niezależną od implementacji kompilatora).

W celu zapewnienia losowości testów, dla każdego testu wartości t, n_min, n_max, a_max zostały wybrane ręcznie, a ziarno generatora zostało wybrane losowo.

^∗https://pl.wikipedia.org/wiki/Kod_Pr%C3%BCfera

Na wyjściu powinno znaleźć się t wierszy opisujących odpowiedzi na kolejne przypadki testowe. Odpowiedź na każdy przypadek testowy powinna znajdować się w oddzielnym wierszu i zawierać n liczb całkowitych (gdzie n jest liczbą miast w danym przypadku testowym); k-ta spośród tych liczb powinna oznaczać minimalne zagrożenie, jakie może stwarzać Bitocja po podziale na k państewek.

Wyjaśnienie przykładu: Powyższy test został wygenerowany kodem dostępnym w dziale Pliki w systemie SIO₂ za pomocą uruchomienia próbnego, dla ziarna 8 122 020 oraz parametrów t = 2, n_min = 5, n_max = 7, a_max = 10.

Dla pierwszego przypadku testowego pierwsza wypisana liczba to (9+1+4+2+6+4+7)² = 1089 i oznacza całkowite zagrożenie stwarzane przez niepodzieloną Bitocję. Druga wypisana liczba odpowiada całkowitemu zagrożeniu w przypadku zniszczenia drogi łączącej miasta 5 i 7; w tej sytuacji zagrożenie wyniesie (9 + 7)² + (1 + 4 + 2 + 6 + 4)² = 545.