Query on a tree III

19.02.2010 - Wiktor Janas
TrudnośćTrudnośćTrudnośćTrudność

 


Mediana

Limit czasowy 1s, limit pamięciowy : 32MB

Dany jest ciąg $ n $ liczb całkowitych. Twoim zadaniem jest znalezienie w nim $ k $-tej liczby w porządku niemalejącym.

Wejście:

W pierwszej linii wejścia dana jest liczba $ t $ - ilość testów ($ 1 \leq t \leq 100 $). Następnie danych jest $ t $ linii. W każdej linii znajdują się liczby $ n, k $ ($ 1 \leq k \leq n \leq 100000 $), a następnie $ n $ liczb całkowitych (co do modułu nie większych od dwóch miliardów).

Wyjście:

Dla każdego testu należy wypisać $ k $-tą liczbę w porządku niemalejącym.

 

Przykład:

Wejście:

2
6 3 -4 5 66 -2 3 11
8 6 87 23 -13 87 42 100 0 23

Wyjście:

3
87


Preorder

Limit czasowy 1s, limit pamięciowy : 32MB

Dane jest ukorzenione drzewo z etykietowanymi wierzchołkami. Należy wypisać etykiety wierzchołków w porządku pre-order.

Wejście:

W pierwszej linii wejścia dana jest liczba $ n $ - ilość wierzchołków drzewa ($ 1 \leq n \leq 100000 $). W drugiej linii dane jest $ n $ liczb - są to etykiety wierzchołków. Nastęnie danych jest $ n-1 $ linii, każda z nich zawiera dwie liczby $ a_i $, $ b_i $ ($ 1 \leq a_i, b_i \leq n $). Oznaczają one, że istnieje krawędź między wierzchołkami $ a_i $ oraz $ b_i $. Wszystkie krawędzie na wejściu będą różne. Korzeniem drzewa jest wierzchołek o numerze 1.

Wyjście:

Należy wypisać $ n $ liczb - etykiety kolejnych wierzchołków w porządku pre-order.

 

Przykład:

Wejście:

5
23 56 15 83 27
1 3
2 3
4 5
1 5

Wyjście:

23 15 56 27 83


Query on a Tree III

Limit czasowy 5s, limit pamięciowy : 32MB

Dane jest ukorzenione drzewo o etykietowanych wierzchołkach. Należy odpowiadać na zapytania postaci "podaj numer wierzchołka o $ k $-tej co do wielkości etykiecie w poddrzewie wierzchołka $ v $".

Wejście:

W pierwszej linii dana jest liczba $ n $ ($ 1 \leq n \leq 100000 $) - ilość wierzchołków drzewa. Następnie danych jest $ n $ liczb całkowitych - są to etykiety kolejnych wierzchołków. Następnie danych jest $ n-1 $ linii, z których każda zawiera dwie liczby $ a_i $, $ b_i $ ($ 1 \leq a_i, b_i \leq n $), które oznaczają, że istnieje krawędź pomiedzy wierzchołkami $ a_i $ oraz $ b_i $. Krawędzie nie powtarzają się. Korzeniem drzewa jest wierzchołek o numerze 1. Następnie dana jest liczba $ q $ ($ 1 \leq q \leq 10000 $) oznaczająca ilość zapytań. Dalej danych jest $ q $ linii, z których każda zawiera dwie liczby $ v_i $, $ k_i $. Oznaczają one zapytanie o $ k_i $-ty wierzchołek w poddrzewie wierzchołka $ v_i $.

Wyjście:

Dla każdego zapytania należy wypisać szukany numer wierzchołka

 

Przykład:

Wejście:

5
2 4 65 1 87
4 2
1 3
1 2
2 5
2
3 1
5 1

Wyjście:

3
5

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
0
Twoja ocena: Brak

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com