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_.

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

5
4
5
5