| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 6 초 | 512 MB | 8 | 8 | 6 | 100.000% |
Zadano je stablo: neusmjeren i povezan graf s n vrhova i n − 1 bridova. Vrhovi su označeni brojevima 1, 2, . . . , n.
Zadano je q upita. U svakom upitu odabiremo neki podskup vrhova stabla P = {v1, v2, . . . , vk} i pitamo koliko se bridova nalazi u najmanjem razapinjujućem stablu skupa P? Drugim riječima, koliko bridova pripada barem jednom putu između nekih vrhova skupa P? Pronadite odgovore na sve upite.
U prvom redu nalazi se prirodan broj n (2 ≤ n ≤ 1 000 000), broj vrhova stabla. U svakom od sljedećih n − 1 redova nalaze se dva različita prirodna broja a, b (1 ≤ a, b ≤ n) koji označavaju da su vrhovi a i b povezani bridom.
U sljedećem redu nalazi se prirodan broj q (1 ≤ q ≤ 60 000), broj upita. U svakom od sljedećih q redova nalazi se najprije prirodan broj k (k ≥ 2), veličina skupa, a potom k različitih prirodnih brojeva između 1 i n koji predstavljaju vrhove skupa iz teksta zadatka. Zbroj veličina k za sve upite bit će najviše 300 000.
Za svaki upit u zaseban redak ispišite traženi broj bridova.
5 1 2 2 3 3 4 4 5 4 2 1 2 2 3 5 2 1 5 3 1 3 5
1 2 4 4
10 1 2 2 4 5 2 6 3 3 1 6 7 9 7 8 6 8 10 5 2 4 5 3 4 5 6 4 2 4 7 10 4 4 5 9 10 9 1 2 3 5 6 7 8 9 10
2 5 7 9 8