← 返回题目列表

AtCoder · utpc2011_12

L. 第L号

中文机器翻译题面 查看原题

许多嗅到叛乱气息的 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