题目地址：洛谷：【SP1487】PT07J – Query on a tree III – 洛谷、SPOJ：SPOJ.com – Problem PT07J

SPOJ QTREE系列：

• [SPOJ-QTREE]Query on a tree 题解（树链剖分）
• [SPOJ-QTREE2]Query on a tree II 题解（树链剖分）
• [SPOJ-PT07J]Query on a tree III 题解（主席树）
• [SPOJ-QTREE3]Query on a tree again! 题解（树链剖分）
• [SPOJ-QTREE4]Query on a tree IV 题解（点分治/边分治）
• [SPOJ-QTREE5]Query on a tree V 题解（边分治）
• [SPOJ-QTREE6]Query on a tree VI 题解（LCT）
• [SPOJ-QTREE7]Query on a tree VII 题解（LCT）

题目描述

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.
给一棵带点权的以1为根的有根树，查询某子树内点权第k小值。

输入输出格式

输入格式：
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)

输出格式：
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.

输入输出样例

输入样例#1：

5
1 3 5 2 7
1 2
2 3
1 4
3 5
4
2 3
4 1
3 2
3 2

输出样例#1：

5
4
5
5

题解

DFS序+主席树。主席树的叶子节点可以存一下DFS序号，这样方便查。

代码

// Code by KSkun, 2018/3
#include <cstdio>

#include <vector>
#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005;

std::vector<int> gra[MAXN];

int dfn[MAXN], ptn[MAXN], siz[MAXN], clk;

inline void dfs(int u, int fa) {
    dfn[u] = ++clk;
    ptn[dfn[u]] = u;
    siz[u] = 1;
    for(int v : gra[u]) {
        if(v == fa) continue;
        dfs(v, u);
        siz[u] += siz[v];
    }
}

struct SGT {
    struct SGTNode {
        int lch, rch, val, dfn;
    } tr[MAXN * 20];
    int rt[MAXN], cnt = 0;

    inline void insert(int &o, int l, int r, int x, int dfn) {
        tr[++cnt] = tr[o]; o = cnt;
        tr[o].val++;
        if(l == r) {
            tr[o].dfn = dfn;
            return;
        }
        int mid = (l + r) >> 1;
        if(x <= mid) insert(tr[o].lch, l, mid, x, dfn);
        else insert(tr[o].rch, mid + 1, r, x, dfn);
    }

    inline int query(int o1, int o2, int l, int r, int k) {
        if(l == r) return ptn[tr[o2].dfn];
        int mid = (l + r) >> 1;
        if(k <= tr[tr[o2].lch].val - tr[tr[o1].lch].val) {
            return query(tr[o1].lch, tr[o2].lch, l, mid, k);
        } else {
            k -= tr[tr[o2].lch].val - tr[tr[o1].lch].val;
            return query(tr[o1].rch, tr[o2].rch, mid + 1, r, k);
        }
    }
} sgt;

int n, m, w[MAXN], ut, vt, xt, kt;
std::vector<int> tmp;

int main() {
    n = readint();
    tmp.push_back(-1);
    for(int i = 1; i <= n; i++) {
        w[i] = readint();
        tmp.push_back(w[i]);
    }
    std::sort(tmp.begin(), tmp.end());
    tmp.erase(std::unique(tmp.begin(), tmp.end()), tmp.end());
    int N = tmp.size() - 1;
    for(int i = 1; i <= n; i++) {
        w[i] = std::lower_bound(tmp.begin(), tmp.end(), w[i]) - tmp.begin();
    }
    for(int i = 1; i < n; i++) {
        ut = readint(); vt = readint();
        gra[ut].push_back(vt);
        gra[vt].push_back(ut);
    }
    dfs(1, 0);
    for(int i = 1; i <= n; i++) {
        sgt.rt[i] = sgt.rt[i - 1];
        sgt.insert(sgt.rt[i], 1, N, w[ptn[i]], i);
    }
    m = readint();
    while(m--) {
        xt = readint(); kt = readint();
        printf("%d\n", sgt.query(sgt.rt[dfn[xt] - 1], sgt.rt[dfn[xt] + siz[xt] - 1], 
            1, N, kt));
    }
    return 0;
}