( ext{Solution:})
题意很清楚：维护有序三元组 ((a,b,c),a,k) 已知，使得 (a,bin ancestor_c, ext{dis(a,b)}leq k.)
观察到 (c) 的祖先一定在一条链上。分类讨论一下：
-
若 (dep_b<dep_c) 则与它们配对的 (c) 的数目等于 (siz[a]-1.)
-
若 (dep_b>dep_c) 则与它们配对的 (c) 的数目等于 (sum siz[b]-1.)
于是考虑维护这两个东西。由于 (a,k) 已知，那么我们就可以将第二种情况转化成：维护深度区间在 ([dep_a+1,dep_a+k]) 的节点 (siz) 和。
那这东西就很显然可以用线段树合并来维护了：每一个点建立以深度为序的线段树，单点修改，区间查询。
时间复杂度 (O(nlog n).) 空间复杂度也是 (O(nlog n).) 注意答案会爆 ( ext{int}).
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=6e5+10;
const int MAXN=8e6+10;
int Maxdep,node;
vector<int>vec[N],pos[N];
long long ans[N];
inline int read() {
int s=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch)) {
s=s*10-48+ch;
ch=getchar();
}
return s;
}
inline int Max(int x,int y){return x>y?x:y;}
inline int Min(int x,int y){return x<y?x:y;}
int sum[MAXN],ls[MAXN],rs[MAXN],rub[MAXN<<1],ttop;
int siz[MAXN],dep[MAXN],pa[MAXN],head[MAXN],tot;
int rt[MAXN],n,q;
struct E {
int nxt,to;
} e[N<<1];
inline void add(int x,int y) {
e[++tot]=(E) {
head[x],y
};
head[x]=tot;
}
inline int bd(){
if(ttop)return rub[ttop--];
return ++node;
}
void del(int x){
ls[x]=sum[x]=rs[x]=0;
rub[++ttop]=x;
}
inline void pushup(int x){sum[x]=sum[ls[x]]+sum[rs[x]];}
int merge(int x,int y,int l,int r){
if(!x||!y)return x+y;
if(l==r){
sum[x]+=sum[y];
del(y);
return x;
}
int mid=(l+r)>>1;
ls[x]=merge(ls[x],ls[y],l,mid);
rs[x]=merge(rs[x],rs[y],mid+1,r);
pushup(x);return x;
}
void dfs(int x,int fa){
pa[x]=fa;
dep[x]=dep[fa]+1;
Maxdep=Max(Maxdep,dep[x]);
siz[x]=1;
for(int i=head[x];i;i=e[i].nxt){
int j=e[i].to;
if(j==fa)continue;
dfs(j,x);siz[x]+=siz[j];
}
}
void change(int &x,int L,int R,int pos,int v){
if(!x)x=++node;
if(L==R){
sum[x]+=v;
return;
}
int mid=(L+R)>>1;
if(pos<=mid)change(ls[x],L,mid,pos,v);
else change(rs[x],mid+1,R,pos,v);
pushup(x);
}
int query(int x,int L,int R,int l,int r){
if(L>=l&&R<=r)return sum[x];
int mid=(L+R)>>1,res=0;
if(l<=mid)res=query(ls[x],L,mid,l,r);
if(mid<r)res+=query(rs[x],mid+1,R,l,r);
return res;
}
void dfs_merge(int x){
change(rt[x],1,Maxdep,dep[x],siz[x]-1);
for(int i=head[x];i;i=e[i].nxt){
int j=e[i].to;
if(j==pa[x])continue;
dfs_merge(j);
rt[x]=merge(rt[x],rt[j],1,Maxdep);
}
for(int i=0;i<(int)vec[x].size();++i){
int L=dep[x]+1,R=dep[x]+vec[x][i];
// cout<<x<<":["<<L<<" "<<R<<"]"<<endl;
ans[pos[x][i]]=1ll*query(rt[x],1,Maxdep,L,R);
ans[pos[x][i]]+=1ll*Min(dep[x]-1,vec[x][i])*(siz[x]-1);
// printf("ans:%d
",ans[pos[x][i]]);
}
}
void Debug(){
for(int i=1;i<=n;++i)printf("%lld:siz:%lld dep:%lld pa:%lld
",i,siz[i],dep[i],pa[i]);
}
signed main(){
n=read();q=read();
for(int i=1;i<n;++i){
int x=read(),y=read();
add(x,y);add(y,x);
}
dfs(1,0);
// Debug();
for(int i=1;i<=q;++i){
int p=read(),k=read();
vec[p].push_back(k);
pos[p].push_back(i);
}
dfs_merge(1);
for(int i=1;i<=q;++i)printf("%lld
",ans[i]);
return 0;
}