Runda 12 [Hard] - Owoce

21.02.2011 - Damian Rusak
TrudnośćTrudność

 

Zadanie tygodnia

runda 12; kategoria Hard

Limit czasowy: 1s; Limit pamięciowy: 64MB


Owoce

Po zakończonych żniwach na polu czas zebrać owoce w sadach. Rolnik Stefan pielęgnuje swoje drzewo owocowe z myślą o triumfie w corocznym Turnieju Najpiększniejszych Drzew Owocowych. Wie, że konkurencja będzie silna, dlatego planuje przystrzyc drzewko, tak, aby wyglądało jak najśliczniej.

Drzewo Stefana ma strukturę drzewa, znaną z Teorii Grafów. Z korzenia drzewa wyrastają gałęzie - Zarówno korzeń jak i koniec każdej gałęzi jest owocem i mogą zeń wyrastać kolejne gałęzie. Stefan może odciąć dowolną liczbę gałęzi - wtedy z drzewa znika każdy owoc i każda gałąź, do którego i której można się było dostać z korzenia poprzez uciętą gałąź. 

Każdy z owoców ma swój (być może ujemny) współczynnik piękna. Piękno drzewa to suma współczynników piękna owoców, do których można dojść po gałęziach z korzenia. Stefan prosi Cię o pomoc - jaki największe piękno drzewa może uzyskać, obcinając pewne gałęzie?

Wejście:

Pierwsza linia wejścia zawiera jedną liczbę całkowitą $ n $ - liczbę owoców w drzewie. ($ 1 \leq n \leq 10^6 $). Owoce ponumerowane są od $ 1 $ do $ n $ - owoc w korzeniu ma liczbę $ 1 $. W kolejnych $ n-1 $ liniach znajdują się pary liczb $ a_{i} $, $ b_{i} $ - oznaczające,że od wierzchołka $ a_{i} $ biegnie gałąź do wierzchołka $ b_{i} $. Drzewo zawsze jest spójne. W kolejnej linii znajduje się $ n $ liczb $ w_{1} $, $ w_{2} $, ..., $ w_{n} $ - współczynników piękna owoców o numerach $ 1 $,$ 2 $,...,$ n $. ($ -10^{6} \leq w_{i} \leq 10^{6} $).

Wyjście:

Jedyna linia wyjścia zawierać powinna jedną liczbę całkowitą - maksymalne piękno drzewa, jakie można uzyskać.

Przykład:

Wejście:

7
1 2
1 3
3 6
2 5 
2 4
6 7
3 -5 4 2 1 -6 7 

Wyjście:

8
Najlepsze rozwiązanie otrzymamy ucinając gałąź prowadzącą z owocu nr $ 1 $ do owocu nr $ 2 $.

 

 

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
PozycjaImię i nazwiskoWynikCzasOwoce
1Marcin Karpinski1009:28:1810
2Wojtek Nadara1010:16:0210
3Przemek Komosa1011:28:4510
4Przemysław Derengowski1011:43:5610
5Wojciech Szałapski1040:43:4610
6Mateusz Wasylkiewicz1053:54:3310
7Damian Straszak1079:45:4110
8Bartek Dudek10107:48:5410
9Michał Zezyk10178:58:0810
10Piotr Bejda10179:10:5510
11Witold Długosz10195:24:1410
12Adam Tażyk10207:57:5710
13Kamil Dębowski10296:43:1210
14Arek Wróbel701:13:397
15Paweł Michalak703:05:067
16Krzysztof Drab733:27:227
17Andrzej Rumiński760:35:587
18Jakub Kołodziej7153:09:307
19Tomasz Jan Drab5268:28:495
20Krzysztof Cirocki3107:53:483
21Arkadiusz Sawicz2149:02:142
0
Twoja ocena: Brak

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com