Piękny Podział#523

Piękny Podział

1,5 sekundy
256 megabajtów
Bardzo trudne

Pan IP znalazł w swoim ogrodzie graf. Po pewnym czasie zrozumiał, że ten graf to drzewo! Co więcej, do każdego wierzchołka przypisany był parametr piękna a_i!

Chce ozdobić swój pokój tym drzewem, ale ponieważ użycie go w całości może być brzydkie, pokroi je na mniejsze części (składowe), wykonując następujące czynności dokładnie raz:

Załóżmy, że po pokrojeniu pozostało składowych.

Definiujemy centroid składowej o rozmiarze jako wierzchołek o największej wartości a_v spośród wszystkich wierzchołków, które spełniają następujący warunek:

Niech c_1, c_2, \dots, c_k będą centroidami powstałych składowych. Piękno takiego podziału oblicza się jako suma a_{c_1} + a_{c_2} + \dots + a_{c_k}.

Znajdź dowolny wierzchołek , który maksymalizuje piękno podziału, i oblicz osiągnięte piękno!

Dane wejściowe

Pierwsza linia zawiera jedną liczbę całkowitą (3 \le n \le 3 \cdot 10^5) — liczbę wierzchołków w drzewie.

Druga linia zawiera liczb całkowitych a_1, a_2, \dots, a_n (1 \le a_i \le 10^9) — parametry piękna wierzchołków.

Następne n-1 linii zawierają opis drzewa: i+2-ta linia wejścia zawiera dwie liczby całkowite u_i i v_i (1 \le u_i, v_i \le n) — -ta krawędź drzewa.

Jest gwarantowane, że dane wejściowe opisują prawidłowe drzewo.

Dane wyjściowe

Wypisz dwie liczby całkowite i  — indeks wierzchołka użytego w podziale, który osiąga maksymalne piękno, oraz wartość piękna tego podziału.

Przykłady

Przykład 1

Loading
Loading

Przykład 2

Loading
Loading

Uwaga

W pierwszym przykładzie, dla każdego wyboru wierzchołka podziału:

  • u = 1, centroidy dwóch składowych to i , z pięknem 2+3 = 5.

  • u = 2, trzy centroidy to i , z pięknem 4+5+3 = 12.

  • u = 3, trzy centroidy to i , z całkowitym pięknem 6+7+2 = 15.

  • Dla u=4,5, pojedynczy centroid to z pięknem .

  • Dla u=6,7, pojedynczy centroid to z pięknem .

W drugim przykładzie, krojąc przy wierzchołku , powstają trzy składowe: \{1\}, \{4\}, \{2,5,6\} z centroidami i pięknem 4+1+6=11.

Punktacja

  1. ( punktów): a_i = 1 dla wszystkich ;

  2. ( punktów): u_i = i; v_i = i+1;

  3. ( punktów): n \le 50;

  4. ( punktów): n \le 10^3;

  5. ( punktów): n = 2^k-1; u_i = \lfloor \frac{i+1}{2} \rfloor; v_i = i+1;

  6. ( punktów): brak dodatkowych ograniczeń.