题意

给定一棵树，每个节点有一个权值 $a[i]$，需要支持查询某个子树中第 $k$ 小的权值。

思路

本题可以通过多种数据结构与算法解决，核心在于如何高效合并子树信息并支持第 $k$ 小查询。

算法步骤

方法一：$O(n \log n)$ 或 $O(n \log^2 n)$

1. 使用二叉搜索树（BST）维护每个节点的子树信息。
2. 在 DFS 过程中，将子节点的 BST 按秩合并到父节点的 BST 中。
3. 使用支持 $O(n)$ 合并的 BST（如 Treap 或 Splay 树）可达到 $O(n \log n)$ 的复杂度；若使用普通 BST 合并，则复杂度为 $O(n \log^2 n)$。

方法二：$O(n \sqrt{n})$

1. 对树进行 DFS，将子树转化为区间问题。
2. 问题转化为：给定数组 $a[i]$，查询区间 $[l, r]$ 中第 $k$ 小的数。
3. 使用分块或莫队等 $O(\sqrt{n})$ 级别的数据结构处理区间第 $k$ 小查询。

复杂度分析

• 方法一：$O(n \log n)$ 或 $O(n \log^2 n)$，空间复杂度 $O(n)$。
• 方法二：$O(n \sqrt{n})$，空间复杂度 $O(n)$。

代码说明

• 方法一需要实现支持按秩合并的 BST，并在 DFS 过程中动态合并子树信息。
• 方法二需要先通过 DFS 将树结构转化为区间，再使用分块或莫队算法处理区间第 $k$ 小查询。

#include <bits/stdc++.h>
const int MaxN = 100010;
struct node
{
    int val, dfn, r, id;
};
struct query
{
    int l, r;
    int pos, id, k;
};
struct edge
{
    int next, to;
};
node a[MaxN];
query q[MaxN];
edge e[MaxN << 1];
int n, m, cnt, dfscnt, size;
int head[MaxN], ans[MaxN], sum[MaxN], val[MaxN];
inline int comp(node a, node b) { return a.dfn < b.dfn; }
inline int cmp(query a, query b)
{
    if (a.pos != b.pos)
        return a.pos < b.pos;
    return a.r < b.r;
}
inline void add_edge(int u, int v)
{
    ++cnt;
    e[cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}
inline void dfs(int u)
{
    a[u].dfn = ++dfscnt;
    for (int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if (!a[v].dfn)
            dfs(v);
    }
    a[u].r = dfscnt;
}
inline int read()
{
    int x = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0')
        ch = getchar();
    while (ch <= '9' && ch >= '0')
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x;
}
inline void add(int x) { ++val[a[x].val], ++sum[val[a[x].val]]; }
inline void del(int x) { --sum[val[a[x].val]], --val[a[x].val]; }
inline void solve()
{
    int l = 1, r = 0;
    for (int i = 1; i <= m; i++)
    {
        while (l > q[i].l)
            --l, add(l);
        while (r < q[i].r)
            ++r, add(r);
        while (l < q[i].l)
            del(l), ++l;
        while (r > q[i].r)
            del(r), --r;
        ans[q[i].id] = sum[q[i].k];
    }
}
int main()
{
    n = read(), m = read();
    size = pow(n, 0.55);
    for (int i = 1; i <= n; i++)
        a[i].val = read(), a[i].id = i;
    for (int i = 1; i <= n - 1; i++)
    {
        int u = read(), v = read();
        add_edge(u, v);
        add_edge(v, u);
    }
    dfs(1);
    for (int i = 1; i <= m; i++)
    {
        int v, k;
        v = read(), k = read();
        q[i].l = a[v].dfn, q[i].r = a[v].r, q[i].k = k;
        q[i].id = i, q[i].pos = (q[i].l - 1) / size + 1;
    }
    std::sort(q, q + m + 1, cmp);
    std::sort(a + 1, a + n + 1, comp);
    solve();
    for (int i = 1; i <= m; i++)
        printf("%d\n", ans[i]);
    return 0;
}