记录编号	248360	评测结果	AAAAAAAAAAAAAAWWWWWW
题目名称	[BZOJ3653]谈笑风生	最终得分	70
用户昵称	TenderRun	是否通过	未通过
代码语言	C++	运行时间	7.174 s
提交时间	2016-04-10 13:14:19	内存使用	480.97 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn=9000010;
int cnt,fir[maxn],nxt[maxn<<1],to[maxn<<1];
int tot,ID[maxn],end[maxn],dep[maxn],sz[maxn];
long long sum[maxn];
int ch[maxn][2],rt[maxn],maxd;
void addedge(int a,int b){
	nxt[++cnt]=fir[a];to[cnt]=b;fir[a]=cnt;
}

void DFS(int x){
	sz[x]=1;ID[x]=++tot;maxd=max(maxd,dep[x]);
	for(int i=fir[x];i;i=nxt[i])
		if(!ID[to[i]]){
			dep[to[i]]=dep[x]+1;
			DFS(to[i]);
			sz[x]+=sz[to[i]];
		}
	end[x]=tot;	
}

queue<int>q;
int cntot=0;
void Insert(int pre,int &rt,int l,int r,int g,int d){
	rt=++cntot;
	ch[rt][0]=ch[pre][0];
	ch[rt][1]=ch[pre][1];
	sum[rt]=sum[pre]+d;
	if(l==r)return;
	int mid=(l+r)>>1;
	if(mid>=g)Insert(ch[pre][0],ch[rt][0],l,mid,g,d);
	else Insert(ch[pre][1],ch[rt][1],mid+1,r,g,d);
}

long long Query(int pre,int rt,int l,int r,int a,int b){
	if(l>=a&&r<=b)return sum[rt]-sum[pre];
	int mid=(l+r)>>1,ret=0;
	if(mid>=a)ret=Query(ch[pre][0],ch[rt][0],l,mid,a,b);
	if(mid<b)ret+=Query(ch[pre][1],ch[rt][1],mid+1,r,a,b);	
	return ret;
}
int main(){
	freopen("laugh.in","r",stdin);
	freopen("laugh.out","w",stdout);
	int n,Q;
	scanf("%d%d",&n,&Q);
	for(int i=1,a,b;i<n;i++){
		scanf("%d%d",&a,&b);
		addedge(a,b);
		addedge(b,a);
	}
	dep[1]=1;
	DFS(1);
	q.push(1);
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=fir[x];i;i=nxt[i])
			if(dep[to[i]]==dep[x]+1){
				if(rt[dep[to[i]]])
					Insert(rt[dep[to[i]]],rt[dep[to[i]]],1,n,ID[to[i]],sz[to[i]]-1);
				else
					Insert(rt[dep[x]],rt[dep[to[i]]],1,n,ID[to[i]],sz[to[i]]-1);
				q.push(to[i]);
			}	
	}
	int a,k;
	long long ans;
	while(Q--){
		scanf("%d%d",&a,&k);
		ans=1ll*min(dep[a]-1,k)*(sz[a]-1ll);
		ans+=Query(rt[dep[a]],rt[min(dep[a]+k,maxd)],1,n,ID[a],end[a]);
		printf("%lld\n",ans);
	}	
	return 0;
}