题解：
我很喜欢这道题。
因为A是给定的，所以实质是求二元组的个数。我们以A（即给定的P）作为基点寻找答案，那么情况分两类。一种是B为A的父亲，另一种是A为B的父亲。
第一种情况很好处理，写法见代码，懒得讲，反正很简单的。
第二种情况的话，按Dfs序建主席树，用主席树维护下标为Dep的序列，每次用Size-1（因为不能取本身；Size[i]即为以i为根的子树节点数）去更新，
询问的时候在以A为根的子树中查找Dep[A]+1~Dep[A]+K的和即可。
不思考自然是看不懂的。
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
inline ll rd(){
ll x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return f*x;
}
const int maxn=(3e5)+,maxq=(3e5)+;
int N,Q,num_edge=,edge_head[maxn],U,V,Le[maxn],Ri[maxn],P,root[maxn],num_treenode=,maxdep;
int Dfn[maxn],num_dfn=;
struct Edge{int to,nx;}edge[maxn<<];
ll Dep[maxn],Size[maxn],K,w,ans;
inline void Add_edge(int from,int to){
edge[++num_edge].nx=edge_head[from];
edge[num_edge].to=to;
edge_head[from]=num_edge;
return;
}
struct Tree{int l,r,ls,rs;ll sum;}t[(maxn<<)+(maxn*)];
inline void Build(int x,int l,int r){//建以深度为下标的主席树
t[x].l=l;t[x].r=r;int mid=(l+r)>>;
if(l==r)return;
Build(t[x].ls=++num_treenode,l,mid);
Build(t[x].rs=++num_treenode,mid+,r);
return;
}
inline void Dfs(int x,int fa){
Dfn[++num_dfn]=x;
Le[x]=num_dfn;
Dep[x]=Dep[fa]+;
maxdep=max(maxdep,Dep[x]);
Size[x]=;
for(int i=edge_head[x];i;i=edge[i].nx){
int y=edge[i].to;
if(y!=fa){
Dfs(y,x);
Size[x]+=Size[y];
}
}
Ri[x]=num_dfn;
return;
}
inline void Update(int u,int x,int q,int s){
int l=t[u].l,r=t[u].r,mid=(l+r)>>;
t[x].l=l;t[x].r=r;
if(l==r&&l==q){t[x].sum=t[u].sum+s; return;}
if(q<=mid){
t[x].rs=t[u].rs;
Update(t[u].ls,t[x].ls=++num_treenode,q,s);
}
else{
t[x].ls=t[u].ls;
Update(t[u].rs,t[x].rs=++num_treenode,q,s);
}
t[x].sum=t[t[x].ls].sum+t[t[x].rs].sum;
return;
}
inline void Query(int u,int x,int ql,int qr){
int l=t[u].l,r=t[u].r,mid=(l+r)>>;
if(ql<=l&&r<=qr){
ans=ans+t[x].sum-t[u].sum;
return;
}
if(ql<=mid)Query(t[u].ls,t[x].ls,ql,qr);
if(qr>mid) Query(t[u].rs,t[x].rs,ql,qr);
return;
}
int main(){
N=rd();Q=rd();
for(int i=;i<N;i++){
U=rd();V=rd();
Add_edge(U,V);
Add_edge(V,U);
}
Dep[]=-;//由于我的写法的原因，把根节点的深度设为0
Dfs(,);
Build(root[]=++num_treenode,,maxdep+);
Dfn[]=;
for(int i=;i<=num_dfn;i++)
Update(root[Dfn[i-]],root[Dfn[i]]=++num_treenode,Dep[Dfn[i]],Size[Dfn[i]]-);
while(Q--){
P=rd();K=rd();
ans=;
//先往父亲找
if(Dep[P]>=K)w=K;else w=Dep[P];
ans+=w*(Size[P]-);
//往儿子找
Query(root[P],root[Dfn[Ri[P]]],Dep[P]+,Dep[P]+K);
printf("%lld\n",ans);
}
return ;
}
By:AlenaNuna