PT07J - Query on a tree III


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.

Input

The first line contains one integer n (1 <= n <= 105). The next line contains n integers li (0 <= li <= 109) 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 <= 104) 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)

Output

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.

Example

Input:
5
1 3 5 2 7
1 2
2 3
1 4
3 5
4
2 3
4 1
3 2
3 2

Output:
5
4
5
5

hide comments
coolboy19521: 2024-10-23 18:37:22

Pretty Ohio. I submitted Mo + Ordered set.

kevi_: 2015-10-06 14:41:09

(n+m)logn 1s passed, with no stl.

李子通: 2014-12-15 12:30:46

I used Mo's algorithm and made blocks based on values.O(m*(sqrt(n)+sqrt(m))).
It was accepted.Because its constant is really small.
13170892 2014-12-15 12:26:34 Query on a tree III accepted
edit run 0.38 12M
C++
4.3.2

Raghuram: 2014-07-15 17:55:27

nlogn +mlogn = tle, with the dirtiest IO optimizations and no stl

Last edit: 2014-07-15 17:57:47
Hussain Kara Fallah: 2014-03-11 01:21:39

Actually Aced log^2 for query
buuut no STL -_-

adze: 2014-01-11 12:43:11

All test cases indicate k'th smallest. Please clarify.

vit: 2013-09-07 15:53:52

nlogn - tle, i <3 this OJ

Zhouxing Shi: 2013-04-26 23:47:45

kth largest or kth smallest?

kipoujr: 2012-01-15 11:50:41

Just changed my c++ vectors with malloc, and passed the time limit.

Govardhan Reddy M: 2011-04-01 17:03:21

cant understand the role of labels ??


Added by:Thanh-Vy Hua
Date:2007-04-07
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Co-author Amber