萌新妹子求助 18分 又T 又WA

代码很长 大致思路如下：

类似于CF1009F的长链剖分做法 考虑用长链剖分维护一下某个点的dp数组 然后把询问离线下来 每次做该点的dp数组的前缀和 用的是vector版

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n,q,head[300005],pnt[600005],nxt[600005],E = 0;
int dep[300005],siz[300005],son[300005],fa[300005],d[300005],ans[300005],lazy[300005];
std::vector<int> dp[300005];
std::vector<pair<int,int> > que[300005];
struct Question
{
    int p,k,id;
}a[300005];

bool cmp1(Question a,Question b)
{
    return a.k < b.k;
}

bool cmp2(Question a,Question b)
{
    return a.id < b.id;
}

void add_edge(int u,int v)
{
    pnt[E] = v;
    nxt[E] = head[u];
    head[u] = E++;
}

void dfs1(int u,int f)
{
    d[u] = dep[f] + 1;
    dep[u] = dep[f] + 1;
    son[u] = -1;
    fa[u] = f;
    siz[u] = 1;
    for (int i = head[u]; i != -1; i = nxt[i])
    {
        int v = pnt[i];
        if (v == for) continue;
        dfs1(v,u);
        siz[u] += siz[v];
        d[u] = max(d[u],d[v]);
        if (son[u] == -1 || d[v] > d[son[u]]) son[u] = v;
    }
}

void dfs2(int u,int tp)
{
    if (son[u] == -1)
    {
        dp[u].push_back(0);
        for (int i = 0; i < que[u].size(); i++)
        {
            ans[que[u][i].second] = 0;
        }
        return ;
    }
    dfs2(son[u],tp);
    dp[u].swap(dp[son[u]]);
    for (int i = head[u]; i != -1; i = nxt[i])
    {
        int v = pnt[i];
        if (v == son[u] || v == fa[u]) continue;
        dfs2(v,v);
        for (int j = dp[v].size() - 1; j >= 0; j--)
        {
            dp[u][dp[u].size() - j - 1] += dp[v][j];
        }
    }
    if (!que[u].size()) return (void) dp[u].push_back(siz[u] - 1);;
    int res = 0;
    for (int i = 1; i <= que[u][0].first; i++)
    {
        res += dp[u][dp[u].size() - i];
    }
    ans[que[u][0].second] = res;
    for (int i = 1; i < que[u].size(); i++)
    {
        for (int j = que[u][i - 1].first + 1; j <= que[u][i].first; j++)
        {
            res += dp[u][dp[u].size() - j];
        }
        ans[que[u][i].second] = res;
    }
    dp[u].push_back(siz[u] - 1);
}

signed main()
{
    memset(head,-1,sizeof(head));
    scanf("%lld%lld",&n,&q);
    for (int i = 1; i < n; i++)
    {
        int u,v;
        scanf("%lld%lld",&u,&v);
        add_edge(u,v);
        add_edge(v,u);
    }
    dfs1(1,0);
    for (int i = 1; i <= q; i++)
    {
        scanf("%lld%lld",&a[i].p,&a[i].k);
        a[i].id = i;
    }
    sort(a + 1,a + q + 1,cmp1);
    for (int i = 1; i <= q; i++)
    {
        que[a[i].p].push_back(make_pair(min(a[i].k,d[a[i].p] - dep[a[i].p]),a[i].id));
    }
    dfs2(1,1);
    sort(a + 1,a + q + 1,cmp2);
    for (int i = 1; i <= q; i++)
    {
        printf("%lld\n",ans[i] + min(dep[a[i].p] - 1,a[i].k) * (siz[a[i].p] - 1));
    }
    return 0;
}