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

样例输入 #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