← 返回题目列表

AtCoder · abc239_e

H. 子树第 K 个最大值

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

分数: 500 点

问题陈述

我们有一棵有根树 N 顶点。 顶点已编号 1 通过 N,根为 Vertex 1.
的 i第一条边连接顶点 A_i 和 B_i.
顶点 i 有一个整数 上面写着 X_i 。

你被给予 Q 查询。 对于 i-第一个查询,给定一对整数 (V_i,K_i),回答以下问题。

  • 问题:以Vertex为根的子树中顶点上写入的整数之间 V_i,找到 K_i- 第一个最大值。

约束

  • 2 \leq N \leq 10^5
  • 0\leq X_i\leq 10^9
  • 1\leq A_i,B_i\leq N
  • 1\leq Q \leq 10^5
  • 1\leq V_i\leq N
  • 1\leq K_i\leq 20
  • 给定的图是一棵树。
  • 以顶点为根的子树 V_i 有 K_i 或更多顶点。
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N Q
X_1 \ldots X_N
A_1 B_1
\vdots
A_{N-1} B_{N-1}
V_1 K_1
\vdots
V_Q K_Q

输出

打印 Q 行。 的 i- 第行应包含对 i第一个查询。


示例输入 1

5 2
1 2 3 4 5
1 4
2 1
2 5
3 2
1 2
2 1

示例输出 1

4
5

此输入中给出的树如下所示。

figure

对于 1-st 查询,以 Vertex 为根的子树中的顶点 1 是顶点 1, 2, 3, 4,和 5,所以打印 2-这些顶点上写入的数字的最大值, 4.
对于 2-nd查询,以Vertex为根的子树中的顶点 2 是顶点 2, 3,和 5,所以打印 1-这些顶点上写入的数字的最大值, 5.


示例输入 2

6 2
10 10 10 9 8 8
1 4
2 1
2 5
3 2
6 4
1 4
2 2

示例输出 2

9
10

示例输入 3

4 4
1 10 100 1000
1 2
2 3
3 4
1 4
2 3
3 2
4 1

示例输出 3

1
10
100
1000