传送门

你们搞的这道题啊，exciting。

首先，看到标题我们就知道用什么算法实现，于是我们使用主席树。

容易发现，a,ba,b和cc都在同一条到根节点的链上面，而且cc是这条链最下面的节点，但是a,ba,b关系未知。

于是分类讨论：

1.b∈anc(a)1.b \in anc(a)，发现c∈subtree(a),dis(a,b)≤kc \in subtree(a),dis(a,b) \le k，发现cc有sz[a]−1sz[a]-1种选择，bb有min⁡(k,dep[a]−1)\min(k,dep[a]-1)，这里dep[rt]=1dep[rt]=1

于是乘法原理相乘即可。

(sz[u]-1)*min(k,dep[u]-1)

2.a∈anc(b)2.a \in anc(b)，这种情况比较复杂，

注意到dis(a,b)≤kdis(a,b) \le k，所以bb能够选择的区域类似于红色区域。

选择好bb以后，发现c∈subtree(b)c \in subtree(b)于是每选择一个bb会对答案产生sz[b]−1sz[b]-1的贡献。

于是答案即是∑u,dep[u]∈[dep[a],dep[a]+k](sz[u]−1)\sum _{u ,dep[u] \in [dep[a],dep[a]+k]}(sz[u]-1)

考虑每个节点开一棵主席树，对于下标为dd的位置，维护∑u,dep[u]=d(sz[u]−1)\sum _{u,dep[u]=d} (sz[u]-1)，于是每次查询区间求和即可。

代码：

#include <bits/stdc++.h>
#define MAXN 300005
#define LOG 55
#define int long long
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
int rt[MAXN];
namespace SegmentTree{
    struct node{
        int l,r;
        int val;
    }tree[MAXN*LOG];
    #define lc(i) tree[i].l
    #define rc(i) tree[i].r   
    inline void pushup(int i,int lson,int rson){
        tree[i].val=tree[lson].val+tree[rson].val;
    }
    int tot;
    void Update(int &i,int l,int r,int index,int val){
        if (!i) i=++tot;
        if (l==r) return tree[i].val+=val,void();
        int mid=(l+r)>>1;
        if (index<=mid) Update(lc(i),l,mid,index,val);
        else Update(rc(i),mid+1,r,index,val);
        pushup(i,lc(i),rc(i));
    }
    int Query(int i,int l,int r,int L,int R){
        if (!i) return 0;
        if (L<=l&&r<=R) return tree[i].val;
        int mid=(l+r)>>1,ans=0;
        if (L<=mid) ans+=Query(lc(i),l,mid,L,R);
        if (mid<R) ans+=Query(rc(i),mid+1,r,L,R);
        return ans;
    }
    void Merge(int &rt,int x,int y){//注意Merge要新建节点
        if (!x||!y) return rt=x+y,void();
        pushup(rt=++tot,x,y);
        Merge(lc(rt),lc(x),lc(y));
        Merge(rc(rt),rc(x),rc(y));
    }
}
using namespace SegmentTree;
vector<int>G[MAXN];
inline void AddEdge(int u,int v){
    G[u].push_back(v);
}
int sz[MAXN],dep[MAXN],n,q;
void dfs(int u,int father){
    dep[u]=dep[father]+1;
    sz[u]=1;
    for (register int i=0;i<G[u].size();++i){
        int v=G[u][i];
        if (v!=father) {
            dfs(v,u);
            sz[u]+=sz[v];
        }
    }
    Update(rt[u],1,n,dep[u],sz[u]-1);
    if (father) Merge(rt[father],rt[father],rt[u]);
}
#undef int
int main(){
#define int long long
    n=read(),q=read();
    for (register int i=1;i<n;++i){
        int u=read(),v=read();
        AddEdge(u,v);
        AddEdge(v,u);
    }
    dfs(1,0);
    while (q--){
        int u=read(),k=read();
        printf("%lld\n",Query(rt[u],1,n,dep[u]+1,dep[u]+k)+(sz[u]-1)*min(k,dep[u]-1));
    }
}