Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
WIESCZ - Wierzchołki na ściezce |
Mamy dany spójny, acykliczny graf. Dla pewnych wierzchołków v chcielibyśmy poznać numer k-tego wierzchołka na ich ścieżce do wierzchołka numer 1.
Wejście
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite n oraz m (1 ≤ n, m ≤ 106), oznaczające kolejno liczbę wierzchołków w grafie oraz liczbę zapytań.
Kolejne n – 1 wierszy zawiera opis krawędzi w grafie. W każdym z nich znajdują się dwie liczby całkowite a i b (1 ≤ a, b≤ n) oznaczające, że krawędź łącząca wierzchołek a i b.
Kolejne m wierszy zawiera opisy kolejnych zapytań, po jednym w wierszu. Opis każdego zapytania składa się z dwóch liczb całkowitych v oraz k (1 ≤ v, k ≤ n), oznaczających, że szukamy numeru k-tego wierzchołka na ścieżce od wierzchołka v do wierzchołka numer 1. Wartość k nie przekracza długości ścieżki pomiędzy wierzchołkiem 1, a v.
Wyjście
W m wierszach wyjścia powinny znaleźć się odpowiedzi na kolejne zapytania, po jednej w wierszu.
Przykład
Dla danych wejściowych:8 4
1 2
1 5
5 7
5 8
4 8
6 8
3 5
6 2
3 1
5 2
6 3
poprawnym wynikiem jest:8
3
1
5
Dodane przez: | Karol Waszczuk |
Data dodania: | 2014-08-13 |
Limit czasu wykonania programu: | 1s |
Limit długości kodu źródłowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: ASM64 GOSU |