许多嗅到叛乱气息的 G○○gle 程序员前来抓捕我们。数量相当可观。 其中不少人曾是东京大学时期温柔指导我们的前辈。 可惜,现在我们已是敌人。
- 瓦塔
- “比预想的还多…”
- (毛利部落)
- “啊,虽然我们拥有超高速指数时间算法,但这最多也只是刚好追上他们而已。以这种数量来说…”
- ??
- “不用担心!你们,把算法交给我们!”
我向窗外望去,看到一群人面对着 G○○gle 的大楼。 黑色布料的 T 恤上用红色写着 I、绿色写着 ○、黄色写着 M……他们是 I○M!? 而奇怪的是,他们击败了迎面而来的 G○○gle 程序员,却连键盘都没碰。 这是怎么回事?
- (毛利部落)
- 「…!终于 Wats○n 2 完成了吗!」
- 瓦塔
- 「这是怎么回事?」
2011 年,I○M 利用他们高超的技术力,完成了 Wats○n 系统,这是一套能够以自然语言高速且准确回答问题的系统,并在知识竞赛节目中战胜了被称为“竞猜王”的人类。从而,在 20XX 年的现在,Wats○n 作为一个可以针对编程竞赛题生成解答程序的系统重生了。
随着 I○M 的登场,围绕着我们的人员正在减少。
- 瓦塔
- 「这是个机会!一半可以交给你负责吗?」
- (毛利部落)
- 「当然可以!」
我因为与妄想决裂,回忆起了一切。 当然,当时的知识和经验,从现在来看,水平太低,毫无用处。 但是,我能够回忆起最重要的东西。 那就是,对编程比赛的热爱。 打开题目的那一刻的激动,样例通过的瞬间的兴奋,状态更新的瞬间的紧张,胜利的那一刻的喜悦。
- (毛利部落)
- “一定要报复 kita_masa,结束这个疯狂的世界!”
然后,我推出了自己自信的题目。 这是我在东京大学时代最爱的题目“K 第几位数字”,通过独特技巧进行了泛化和大规模化的题目。
問題
给出一个图。
- N 图中有 个顶点,每个顶点都有 1 减去 N 编号。
- 这些顶点是,N - 1 图的边以树状连接。
- 各頂点 v 上确定了数字 av 。
下图是给定图的例子。 每个顶点上方标有顶点编号,下方标有该顶点的确定数字(av)被写入。 从
[原题图片已从来源服务器移除:/img/problems/8/images/l_th_fig1.png]
给定图的例子
接下来, 请输出Q 会给出以下这样的查询若干。
- 每个查询 分别为 q 中,指定顶点 vq, wq 和整数 可以获得第 lq 。
- 頂点 vq 到顶点 wq 到 lq 的路径中包含的顶点数字中,求第
- 小的数字。 路径仅考虑简单路径。简单路径是指不经过同一顶点两次的路径。由于图是树状的,简单路径是唯一的。
- 路径应包含两端点(即顶点). vq, wq例如,当给定上图的图时,
对应查询 (vq, wq, lq) = (1, 6, 3) 的答案是 7. q 这是因为,从顶点 1 到顶点 6 的路径中包含顶点 1、3、4、6, 而这些顶点对应的数字 2、5、8、7 中第三小的数字是 7.
编写一个程序,接收图和查询作为输入,并输出结果.
入力
输入的第一行包含两个整数 N, Q ,表示顶点数和查询数.
继续 N 接下来的行表示每个顶点所持有的数字. v 其中,第 xv 行写有一个整数, v 表示顶点所持有的数字.
继续 N - 1 行表示边的信息。 这些行中 e 行是两个整数 ae, be 被写入, 它们表示由边 e 连接的两个顶点。
继续 Q 行表示查询的信息。 这些行中的第 q 行写有三个整数 vq, wq, lq , 它们表示查询 q 的信息。 在第
出力
输出是 由 Q 行组成。q 行中,查询 q 的答案。
输入相关的约束
- 1 ≤ N, Q ≤ 105
- 1 ≤ xv ≤ 109
- 1 ≤ ae, be ≤ N
- 1 ≤ vq, wq ≤ N
- 頂点 vq 到顶点 wq 的路径上存在至少 lq 个顶点。
入出力例
入力例:
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