Code Submission Evaluation System Login

IOI-leiri 2016

PUUKYSELY9000


Task | Statistics


CSES - PUUKYSELY9000CSES - PUUKYSELY9000

Time limit:4.00 s Memory limit:1024 MB

Syötteenä annetaan puu, jonka jokaisessa solmussa on jokin luku. Tehtäväsi on vastata seuraavanlaisiin kyselyihin: Jos järjestetään polulla solmusta $u$ solmuun $v$ olevat luvut pienimmästä suurimpaan, mikä on järjestyksessä $k$:s luku?

Syöte

Ensimmäisellä rivillä on kaksi lukua $n$ ja $q$, puun solmujen määrä ja kyselyiden määrä. Seuraavalla rivillä on luvut $a_1, \ldots, a_n$, puun solmuissa olevat luvut. Sen jälkeen tulee $n-1$ riviä, joilla on luvut $u_i, v_i$, joka tarkoittaa että puussa on kaari solmujen $u_i$ ja $v_i$ välillä. Sen jälkeen tulee $q$ riviä, joilla on luvut $u_i, v_i, k_i$ eli kysytään mikä on $k$:s luku jos luvut polulla $u_i$:sta $v_i$:hin järjestetään.

Tuloste

Tulosta jokaiseen kyselyyn vastaus.

Rajat
Esimerkki

Syöte:
8 5
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5 1
2 5 2
2 5 3
2 5 4
7 8 2


Tuloste:
2
8
9
105
7