题解 P3899 【[湖南集训]谈笑风生】

link

P3899 [湖南集训]谈笑风生

solve

通过观察我们发现，a是固定不动的，而b距离a不超过k

则b有两种情况。

((i))b在a的上方

则(b)离(a)的距离最大为$ min(deep[a],k)$

(c)就是(a)子树的任意一点。

则对答案的贡献就是$ min(deep[a],k)* (size[a]-1) $

((ii))b是a的下方

那我们b是a子树上距离(a)不超过k也就是深度差不超过k的一个点

(c)就是(b)子树上的一个点

对答案的贡献就是把所有可能的(size[b])加起来

我们以(deep[x])为下标,(size[x])为权值建主席树，就可以统计出(sum)总和了。

注意一点，数据比较大，要开long long

code

#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
const int maxn=600005;
typedef long long LL;
int N,Q,son[maxn],nxt[maxn],lnk[maxn],cnt,deep[maxn],size[maxn],r[maxn],tot,q[maxn],l[maxn],sz,root[maxn];
struct data{
	int l,r;
	LL sum;
}tr[maxn*32];
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
int add_e(int x,int y){son[++cnt]=y;nxt[cnt]=lnk[x];lnk[x]=cnt;}
void dfs(int u,int fa){
	l[u]=++tot;deep[u]=deep[fa]+1;q[tot]=u;size[u]=1;
	for(int j=lnk[u];j;j=nxt[j]){
		if(son[j]==fa)continue;
		dfs(son[j],u);size[u]+=size[son[j]];
	}
	r[u]=tot;
}
void insert(int &x,int l,int r,int pos,int val){
	tr[++sz]=tr[x];x=sz;
	tr[x].sum+=(LL)val;
	if(l==r)return ;
	int mid=(l+r)>>1;
	if(pos<=mid)insert(tr[x].l,l,mid,pos,val);
	else insert(tr[x].r,mid+1,r,pos,val);
}
void update(int x){
	int l=tr[x].l,r=tr[x].r;
	tr[x].sum=tr[l].sum+tr[r].sum;
}
LL query(int i,int j,int l,int r,int ll,int rr){
	if(ll<=l&&r<=rr)return tr[j].sum-tr[i].sum;
	int mid=(l+r)>>1;
	LL ans=0;
	if (ll<=mid)ans+=query(tr[i].l,tr[j].l,l,mid,ll,rr);
	if (rr>mid)ans+=query(tr[i].r,tr[j].r,mid+1,r,ll,rr);
	return ans;
} 
int main(){
	freopen("3653.in","r",stdin);
	freopen("3653.out","w",stdout);
	N=read();Q=read();
	for(int i=1;i<N;i++){
		int x=read(),y=read();
		add_e(x,y);add_e(y,x);
	}
	dfs(1,0);
	for(int i=1;i<=N;i++)root[i]=root[i-1],insert(root[i],1,N,deep[q[i]],size[q[i]]-1);
	for(int i=1;i<=Q;i++){
		int x=read(),k=read();
		LL t=query(root[l[x]],root[r[x]],1,N,deep[x]+1,deep[x]+k);
		int len=min(k,deep[x]-1);
		printf("%lld
",t+(LL)len*(LL)(size[x]-1));
	}
	return 0;
}