1 /**************************************************************  2     Problem: 1803  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:552 ms  7     Memory:28936 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <algorithm> 12   13 using namespace std; 14 const int N = 100005; 15 const int M = 20 * N; 16   17 struct data { 18     int key, w; 19     data() {} 20     data(int _k, int _w) : key(_k), w(_w) {} 21       22     inline bool operator < (const data &x) const { 23         return key < x.key; 24     } 25 } a[N]; 26   27 struct edge { 28     int next, to; 29     edge() {} 30     edge(int _n, int _t) : next(_n), to(_t) {} 31 } e[N << 1]; 32   33 struct tree_node { 34     int fa, v, st, ed; 35 } tr[N]; 36   37 struct seg_node { 38     int lson, rson, cnt; 39 } seg[M]; 40   41 int n; 42 int tot, first[N]; 43 int cnt_seq, cnt_seg; 44 int root[N]; 45   46 inline int read() { 47     int x = 0; 48     char ch = getchar(); 49     while (ch < ‘0‘ || ‘9‘ < ch) 50         ch = getchar(); 51     while (‘0‘ <= ch && ch <= ‘9‘) { 52         x = x * 10 + ch - ‘0‘; 53         ch = getchar(); 54     } 55     return x; 56 } 57   58 void Add_Edges(int x, int y) { 59     e[++tot] = edge(first[x], y), first[x] = tot; 60     e[++tot] = edge(first[y], x), first[y] = tot; 61 } 62   63 #define mid (l + r >> 1) 64 void modify(int &p, int l, int r, int pos) { 65     seg[++cnt_seg] = seg[p], p = cnt_seg, ++seg[p].cnt; 66     if (l == r) return; 67     if (pos <= mid) modify(seg[p].lson, l, mid, pos); 68     else modify(seg[p].rson, mid + 1, r, pos); 69 } 70   71 int query(int i, int j, int rank) { 72     i = root[i], j = root[j]; 73     int l = 1, r = n; 74     while (l != r) { 75         if (seg[seg[j].lson].cnt - seg[seg[i].lson].cnt >= rank) 76             r = mid, i = seg[i].lson, j = seg[j].lson; 77         else { 78             rank -= seg[seg[j].lson].cnt - seg[seg[i].lson].cnt; 79             l = mid + 1, i = seg[i].rson, j = seg[j].rson; 80         } 81     } 82     return l; 83 } 84 #undef mid 85   86 void dfs(int p) { 87     int x, y; 88     tr[p].st = ++cnt_seq, root[cnt_seq] = root[cnt_seq - 1]; 89     modify(root[cnt_seq], 1, n, tr[p].v); 90     for (x = first[p]; x; x = e[x].next) 91         if ((y = e[x].to) != tr[p].fa) { 92             tr[y].fa = p; 93             dfs(y); 94         } 95     tr[p].ed = cnt_seq; 96 } 97   98 int main() { 99     int i, k, Q;100     n = read();101     for (i = 1; i <= n; ++i)102         a[i] = data(read(), i);103     sort(a + 1, a + n + 1);104     for (i = 1; i <= n; ++i)105         tr[a[i].w].v = i;106     for (i = 1; i < n; ++i)107         Add_Edges(read(), read());108     dfs(1);109  110     Q = read();111     while (Q--) {112         i = read(), k = read();113         printf("%d\n", a[query(tr[i].st - 1, tr[i].ed, k)].w);114     }115     return 0;116 }