問題 L : L 番目の数字

反乱を嗅ぎつけた多くの G○○gle のコーダーが我々を取り押さえにやってきた． かなりの数だ． その中には，東京大学時代に僕らを優しく指導してくれた先輩たちも多く見受けられる． 残念ながら，今では敵同士だ．

wata

「予想以上の数だ…」

(iwi)

「ああ，我々が超高速指数時間アルゴリズムを持っているからと言って，それは彼らにようやく並んだに過ぎない．この数では…」

？？

「心配要らない！君たち，アルゴリズムをこっちに渡すんだ！」

声がした窓の外を見ると，G○○gle の建物に向きあう集団がいた． 黒の生地に赤で I，緑で ○，黄色で M と書かれた T シャツ … 彼らは I○M か！？ そして奇妙なことに，彼らは，向かってくる G○○gle のコーダー達を， キーボードに触れることなく倒していた． どうなっている？

(iwi)

「…！ ついに Wats○n 2 は完成したのか！」

wata

「どういうことだ？」

2011 年，I○M は彼らの高い技術力を活用し， 自然言語で出題されたクイズに高速かつ正確に応答するシステムである Wats○n を完成させ， クイズ番組にてクイズ王と呼ばれてきた人間たちに勝利した． そして 20XX 年の今，Wats○n は， プログラミングコンテストの問題に対し解答のプログラムを作成するシステムとして生まれ変わったのだ．

I○M の登場により，我々を取り囲む人数が減ってゆく．

wata

「チャンスだ！半分は任せられるか？」

(iwi)

「もちろんだ！」

僕は，妄想と決別したことにより，全てを思い出していた． 当然，当時の知識や経験は，今から見ればレベルが低すぎて役に立たない． しかし，一番大切なものを思い出すことができた． それは，プログラミングコンテストを愛する気持ちである． 問題を開く瞬間のワクワク感，サンプルが通った瞬間の盛り上がり， ステータスが更新される瞬間の緊張，勝利の瞬間の喜び．

(iwi)

「必ず kita_masa の復讐を果たし，この狂った世界を終わらせる！」

そして，僕は自信の 1 題を繰り出す． これは，東京大学時代の自分が愛した問題「K 番目の数字」を独自のテクニックにより一般化かつ大規模化した問題である．

問題

グラフが与えられる．

• N 個の頂点があり，頂点に 1 から N の番号が付いている．
• これらの頂点は，N - 1 本の辺によりツリー状に接続されている．
• 各頂点 v には数字 a_v が定まっている．

下図は，与えられるグラフの例である． 各頂点には上部に頂点の番号が，下部にその頂点に定められた数字 (a_v) が書かれている．

与えられるグラフの例

次に，Q 個の以下のようなクエリが与えられる．

• 各クエリ q には，頂点 v_q, w_q と整数 l_q が指定される．
• 頂点 v_q から頂点 w_q への経路に含まれる頂点の数字のうち l_q 番目に小さいものを求めよ．
  • 経路は単純なもののみを考える．単純な経路とは，同じ頂点を二度通らない経路のことである．グラフがツリー状であることから，単純な経路は一意である．
  • 経路には両端点（すなわち頂点 v_q, w_q）を含むものとする．

例えば，上図のグラフが与えられている時， (v_q, w_q, l_q) = (1, 6, 3) なるクエリ q に対する答えは 7 である． これは，頂点 1 から頂点 6 への経路には頂点 1, 3, 4, 6 が含まれており， それらに定まった数字 2, 5, 8, 7 の 3 番目めに小さな数字は 7 であることによる．

グラフとクエリを受け取り，結果を出力するプログラムを作成せよ．

6 11
2
4
5
8
9
7
1 3
2 3
3 4
4 5
4 6
1 6 1
1 6 2
1 6 3
1 6 4
1 2 1
1 2 2
1 2 3
2 5 1
2 5 2
2 5 3
2 5 4

2
5
7
8
2
4
5
4
5
8
9