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

---

输入格式

The first line contains one integer n (1 <= 1="" n="" <="10^5)." the="" next="" line="" contains="" integers="" li="" (0="" which="" denotes="" label="" of="" i-th="" node.="" each="" following="" -="" lines="" two="" u,="" v.="" they="" denote="" there="" is="" an="" edge="" between="" node="" u="" and="" root="" tree.="" one="" integer="" m="" (1="" number="" queries.="" x,="" k.="" (k="" total="" in="" subtree="" x)="" p="">

---

输出格式

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

---

提示

Amber的play with tree系列的题....

---

题目来源

没有写明来源