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:
wybierz wierzchołek w drzewie,
usuń z drzewa, pozostawiając kilka spójnych składowych. Pan IP wykorzysta je do dekoracji swojego pokoju.
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:
jeśli zostanie usunięty ze składowej, rozpadnie się na mniejsze składowe o rozmiarach nie większych niż \frac{m}{2}.
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!
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.
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ład 1
Przykład 2
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.
( punktów): a_i = 1 dla wszystkich ;
( punktów): u_i = i; v_i = i+1;
( punktów): n \le 50;
( punktów): n \le 10^3;
( punktów): n = 2^k-1; u_i = \lfloor \frac{i+1}{2} \rfloor; v_i = i+1;
( punktów): brak dodatkowych ograniczeń.