既然题目的名字是谈笑风生主图当然也要是谈笑风生啦QwQ
BZOJ原题地址
洛谷原题地址
思路
求位于同一条链上的三个点，使前两个点之间的距离小于等于k。
对于给定的 a 和 k，当 b 在 a 上方，显然答案是min(depth[a]-1,k)*(siz[a]-1)；当 b 在 a 的下方，显然是求 a 的子树的前 k 层的每个节点的子树大小（不含其本身）之和。
可以用 DFS 序建主席树维护一定深度下子树大小之和。
代码
#include <bits/stdc++.h>
#define mid ((l+r)>>1)
#define maxn 300010
#define ll long long
using namespace std;
int read(){
int x=0,flag=1;char ch=getchar();
while(!isdigit(ch)&&ch!='-') ch=getchar();
if (ch=='-') flag=-1,ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-'0'),ch=getchar();
return x*flag;
}
struct Edge{
int to,next;
Edge(int a=0,int b=0){
to=a,next=b;
}
}l[maxn*2];
int head[maxn],ind,cnt,n,q,t1,t2;
int dfn[maxn][2],id[maxn];
int rt[maxn],ls[maxn<<7],rs[maxn<<7];
ll t[maxn<<7],d[maxn],siz[maxn];
void Add(int a,int b){
l[++cnt]=Edge(b,head[a]);
head[a]=cnt;
}
void Dfs(int u,int f){
d[u]=d[f]+1;siz[u]=1;
dfn[u][0]=++ind;id[ind]=u;
for (int i=head[u];i;i=l[i].next){
int v=l[i].to;if (v==f) continue;
Dfs(v,u);siz[u]+=siz[v];
}
dfn[u][1]=ind;
}
void Update(int &p,int pre,int l,int r,int x,int v){
p=++cnt;t[p]=t[pre]+v;
if (l==r) return;
if (mid>=x) rs[p]=rs[pre],Update(ls[p],ls[pre],l,mid,x,v);
else ls[p]=ls[pre],Update(rs[p],rs[pre],mid+1,r,x,v);
}
ll Query(int p,int l,int r,int L,int R){
if (L<=l&&r<=R) return t[p];
if (mid>=R) return Query(ls[p],l,mid,L,R);
if (mid<L) return Query(rs[p],mid+1,r,L,R);
return Query(ls[p],l,mid,L,R)+Query(rs[p],mid+1,r,L,R);
}
ll Solve(int x,int y){
ll res=min(d[x]-1,y)*(siz[x]-1);
int l=dfn[x][0],r=dfn[x][1];
ll tmp=Query(rt[r],1,n,d[x],d[x]+y)-
Query(rt[l],1,n,d[x],d[x]+y);
return res+tmp;
}
int main(){
n=read(),q=read();
for (int i=1;i<n;i++)
t1=read(),t2=read(),
Add(t1,t2),Add(t2,t1);
Dfs(1,0);
for (int i=1;i<=n;++i)
Update(rt[i],rt[i-1],1,n,d[id[i]],siz[id[i]]-1);
for (int i=1;i<=q;i++){
t1=read(),t2=read();
printf("%lld\n",Solve(t1,t2));
}
return 0;
}