Polish version    English version  
  Historia OI -> IX OI 2001/2002 -> Zadania


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
Terminarz
Zadania
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
II Etap
Przepisy
Dla zawodnikow
Przydatne zasoby
Statystyki
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
IX Olimpiada Informatyczna 2001/2002

Zadanie: kom
Autor: Tomasz Waleń
Komiwojażer Bajtazar

Zawody I stopnia  
Plik źródłowy: kom.??? (np. pas, c, cpp)
Plik wykonywalny: kom.exe
Plik wejściowy: kom.in
Plik wyjściowy: kom.out

Komiwojażer Bajtazar ciężko pracuje podróżując po Bajtocji. W dawnych czasach komiwojażerowie sami mogli wybierać miasta, które chcieli odwiedzić i kolejność w jakiej to czynili, jednak te czasy minęły już bezpowrotnie. Z chwilą utworzenia Centralnego Urzędu d/s Kontroli Komiwojażerów, każdy komiwojażer otrzymuje z Urzędu listę miast, które może odwiedzić i kolejność w jakiej powinien to uczynić. Jak to zazwyczaj bywa z centralnymi urzędami, narzucona kolejność odwiedzania miast nie ma zbyt dużo wspólnego z kolejnością optymalną. Przed wyruszeniem w trasę Bajtazar chciałby przynajmniej dowiedzieć się, ile czasu zajmie mu odwiedzenie wszystkich miast - obliczenie tego jest Twoim zadaniem.

Miasta w Bajtocji są ponumerowane od 1 do n. Numer 1 ma stolica Bajtocji, z niej właśnie rozpoczyna podróż Bajtazar. Miasta połączone są siecią dróg dwukierunkowych. Podróż między dwoma miastami bezpośrednio połączonymi drogą zawsze zajmuje 1 jednostkę czasu. Ze stolicy można dotrzeć do wszystkich pozostałych miast Bajtocji. Jednak sieć dróg została zaprojektowana bardzo oszczędnie, stąd drogi nigdy nie tworzą cykli.

Zadanie

Napisz program, który:

  • wczyta z pliku wejściowego kom.in opis sieci dróg Bajtocji oraz listę miast, które musi odwiedzić Bajtazar,
  • obliczy sumaryczny czas podróży Bajtazara,
  • zapisze go w pliku wyjściowym kom.out.

Wejście

W pierwszym wierszu pliku tekstowego kom.in zapisana jest jedna liczba całkowita n równa liczbie miast w Bajtocji, 1<=n<=30 000. W kolejnych n-1 wierszach opisana jest sieć dróg - w każdym z tych wierszy są zapisane dwie liczby całkowite a i b (1<=a, b<=n; a<>b), oznaczające, że miasta a i b połączone są drogą. W wierszu o numerze n+1 zapisana jest jedna liczba całkowita m równa liczbie miast, które powinien odwiedzić Bajtazar, 1<=m<=5 000. W następnych m wierszach zapisano numery kolejnych miast na trasie podróży Bajtazara - po jednej liczbie w wierszu.

Wyjście

W pierwszym i jedynym wierszu pliku tekstowego kom.out powinna zostać zapisana jedna liczba całkowita równa łącznemu czasowi podróży Bajtazara.

Przykład

Dla pliku wejściowego kom.in:

5
1 2
1 5
3 5
4 5
4
1
3
2
5
poprawną odpowiedzią jest plik wyjściowy kom.out:
7



Wersja do druku