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