PT07J - Query on a tree III
题意翻译
你被给定一棵带点权的 $n$ 个点的有根树,点从 $1$ 到 $n$ 编号。
定义查询 $q(x,k)$:寻找以 $x$ 为根的子树中的第 $k$ 小点的编号(从小到大排序第 $k$ 个点)。
保证没有两个相同的点权。
输入格式:第一行为整数 $n$,第二行为点权,接下来 $n-1$ 行为树边,接下来一行为整数 $m$,下面 $m$ 行为两个整数 $x,k$,代表查询 $q(x,k)$。
输出格式:$m$ 行,输出每次查询的结果。
题目描述
You are given a node-labeled rooted tree with _n_ nodes.
Define the query (_x_, _k_): Find the node whose label is _k_-th largest in the subtree of the node _x_. Assume no two nodes have the same labels.
输入输出格式
输入格式
The first line contains one integer _n_ (1 <= _n_ <= 10 $ ^{5} $ ). The next line contains _n_ integers _l $ _{i} $_ (0 <= _l $ _{i} $_ <= 10 $ ^{9} $ ) which denotes the label of the _i_-th node.
Each line of the following _n_ - 1 lines contains two integers _u_, _v_. They denote there is an edge between node _u_ and node _v_. Node 1 is the root of the tree.
The next line contains one integer _m_ (1 <= _m_ <= 10 $ ^{4} $ ) which denotes the number of the queries. Each line of the next _m_ contains two integers _x_, _k_. (_k_ <= the total node number in the subtree of _x_)
输出格式
For each query (_x_, _k_), output the index of the node whose label is the _k_-th largest in the subtree of the node _x_.
输入输出样例
输入样例 #1
5
1 3 5 2 7
1 2
2 3
1 4
3 5
4
2 3
4 1
3 2
3 2
输出样例 #1
5
4
5
5