“This is a big mistake!”

主席树的迁移

如何把对主席树“能解决区间第 k 大问题”这个印象迁移到这道非常暴力的题目上呢？我们可以把整棵树用 DFS 序来入手（连续性在本题会比离散型更好）。我们可以先用一个 DFS 来记录 DFS 序、Low 数组、子树大小。

然后，我们以深度为权值，子树大小为要维护的信息。以 DFS 序的顺序来计算前缀子树和、创建主席树。具体见代码：

代码

// P3899.cpp
#include <iostream>
#include <cstdio>
#include <vector>
#define ll long long
#define mid ((l + r) >> 1)
using namespace std;
const ll MX_N = 3e5 + 1000;
ll ncnt, dfn[MX_N], low[MX_N], antiDFN[MX_N], ndfn, dep[MX_N], fa[MX_N], n, q, tmpx, tmpy;
ll subtree[MX_N], roots[MX_N];
vector<ll> G[MX_N];
struct node
{
    ll sum, ls, rs;
} nodes[MX_N * (2 << 5)];
ll build(ll l, ll r)
{
    ll p = ++ncnt;
    if (l == r)
        return p;
    nodes[p].ls = build(l, mid), nodes[p].rs = build(mid + 1, r);
    nodes[p].sum = 0;
    return p;
}
ll update(ll l, ll r, ll previous, ll depth, ll ad)
{
    ll curt = ++ncnt;
    nodes[curt].ls = nodes[previous].ls, nodes[curt].rs = nodes[previous].rs;
    nodes[curt].sum = nodes[previous].sum + ad;
    if (l == r && l == depth)
        return curt;
    if (depth <= mid)
        nodes[curt].ls = update(l, mid, nodes[previous].ls, depth, ad);
    else
        nodes[curt].rs = update(mid + 1, r, nodes[previous].rs, depth, ad);
    return curt;
}
ll query(ll ql, ll qr, ll l, ll r, ll p)
{
    if (ql <= l && r <= qr)
        return nodes[p].sum;
    if (mid >= qr)
        return query(ql, qr, l, mid, nodes[p].ls);
    if (mid < ql)
        return query(ql, qr, mid + 1, r, nodes[p].rs);
    return query(ql, qr, l, mid, nodes[p].ls) + query(ql, qr, mid + 1, r, nodes[p].rs);
}
void dfs(ll u)
{
    dfn[u] = ++ndfn, subtree[u]++;
    antiDFN[ndfn] = u, dep[u] = dep[fa[u]] + 1;
    ll siz = G[u].size();
    for (ll i = 0; i < siz; i++)
        if (G[u][i] != fa[u])
            fa[G[u][i]] = u, dfs(G[u][i]), subtree[u] += subtree[G[u][i]];
    low[u] = ndfn;
}
int main()
{
    scanf("%lld%lld", &n, &q);
    for (int i = 0; i < n - 1; i++)
        scanf("%lld%lld", &tmpx, &tmpy), G[tmpx].push_back(tmpy), G[tmpy].push_back(tmpx);
    dfs(1), roots[0] = build(1, n);
    for (int i = 1; i <= n; i++)
        roots[i] = update(1, n, roots[i - 1], dep[antiDFN[i]], subtree[antiDFN[i]] - 1);
    while (q--)
    {
        scanf("%lld%lld", &tmpx, &tmpy);
        ll ret = min(dep[tmpx] - 1, tmpy) * (subtree[tmpx] - 1);
        ll another = query(dep[tmpx], dep[tmpx] + tmpy, 1, n, roots[low[tmpx]]) -
                     query(dep[tmpx], dep[tmpx] + tmpy, 1, n, roots[dfn[tmpx]]);
        printf("%lld\n", ret + another);
    }
    return 0;
}