102394: [AtCoder]ABC239 E - Subtree K-th Max
Description
Score : $500$ points
Problem Statement
We have a rooted tree with $N$ vertices. The vertices are numbered $1$ through $N$, and the root is Vertex $1$.
The $i$-th edge connects Vertices $A_i$ and $B_i$.
Vertex $i$ has an integer $X_i$ written on it.
You are given $Q$ queries. For the $i$-th query, given a pair of integers $(V_i,K_i)$, answer the following question.
- Question: among the integers written on the vertices in the subtree rooted at Vertex $V_i$, find the $K_i$-th largest value.
Constraints
- $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$
- The given graph is a tree.
- The subtree rooted at Vertex $V_i$ has $K_i$ or more vertices.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$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$
Output
Print $Q$ lines. The $i$-th line should contain the response to the $i$-th query.
Sample Input 1
5 2 1 2 3 4 5 1 4 2 1 2 5 3 2 1 2 2 1
Sample Output 1
4 5
The tree given in this input is shown below.
For the $1$-st query, the vertices in the subtree rooted at Vertex $1$ are Vertices $1, 2, 3, 4$, and $5$, so print the $2$-nd largest value of the numbers written on these vertices, $4$.
For the $2$-nd query, the vertices in the subtree rooted at Vertex $2$ are Vertices $2, 3$, and $5$, so print the $1$-st largest value of the numbers written on these vertices, $5$.
Sample Input 2
6 2 10 10 10 9 8 8 1 4 2 1 2 5 3 2 6 4 1 4 2 2
Sample Output 2
9 10
Sample Input 3
4 4 1 10 100 1000 1 2 2 3 3 4 1 4 2 3 3 2 4 1
Sample Output 3
1 10 100 1000
Input
题意翻译
给定一棵 $n$ 个节点的树,每个节点的权值为 $x_i$。 现有 $Q$ 个询问,每个询问给定 $v,k$,求节点 $v$ 的子树第 $k$ 大的数。 $0\le x_i\le10^9,2\le n\le10^5,1\le Q\le10^5,1\le k\le20$。 翻译提供:xiaohaoaibiancheng66Output
分数:500分
问题描述
我们有一个有根树,有N个顶点。顶点编号为1到N,根顶点为1。
第i条边连接顶点A_i和B_i。
顶点i上写有一个整数X_i。
你将得到Q个查询。对于第i个查询,给定一个整数对(V_i, K_i),回答以下问题。
- 问题:在以顶点V_i为根的子树中,找出第K_i个最大的值。
限制条件
- 2 <= N <= 10^5
- 0<= X_i <= 10^9
- 1<= A_i, B_i <= N
- 1<= Q <= 10^5
- 1<= V_i <= N
- 1<= K_i <= 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
在本输入中给出的树如下所示。
对于第1个查询,以顶点1为根的子树中的顶点为顶点1、2、3、4和5,所以打印写在这些顶点上的数的第2个最大值,即4。
对于第2个查询,以顶点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