PT07J  Query on a tree III
You are given a nodelabeled rooted tree with n nodes.
Define the query (x, k): Find the node whose label is kth 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 <= 10^{5}). The next line contains n integers l_{i} (0 <= l_{i} <= 10^{9}) which denotes the label of the ith 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)
Output
For each query (x, k), output the index of the node whose label is the kth 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
kevi_:
20151006 14:41:09
(n+m)logn 1s passed, with no stl. 

李子通:
20141215 12:30:46
I used Mo's algorithm and made blocks based on values.O(m*(sqrt(n)+sqrt(m))).


Raghuram:
20140715 17:55:27
nlogn +mlogn = tle, with the dirtiest IO optimizations and no stl Last edit: 20140715 17:57:47 

Hussain Kara Fallah:
20140311 01:21:39
Actually Aced log^2 for query


adze:
20140111 12:43:11
All test cases indicate k'th smallest. Please clarify. 

vit:
20130907 15:53:52
nlogn  tle, i <3 this OJ 

Zhouxing Shi:
20130426 23:47:45
kth largest or kth smallest? 

kipoujr:
20120115 11:50:41
Just changed my c++ vectors with malloc, and passed the time limit. 

Govardhan Reddy M:
20110401 17:03:21
cant understand the role of labels ?? 

Dominik Kempa:
20090605 23:41:11
the time limit is too strict 
Added by:  ThanhVy Hua 
Date:  20070407 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  Coauthor Amber 