记录编号	247402	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[BZOJ3653]谈笑风生	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	19.953 s
提交时间	2016-04-08 21:42:19	内存使用	216.61 MiB

#include<cstdio>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
const int SIZEN=300010;
typedef long long LL;
int N,M;
vector<int> s[SIZEN];
int root[SIZEN],first[SIZEN],en[SIZEN],fa[SIZEN]={0};
int dep[SIZEN],siz[SIZEN];
int pos=0;
class miku
{
public:
	int l,r;
	int lson,rson;
	LL sum;
}tr[SIZEN*30];
void read()
{
	scanf("%d%d",&N,&M);
	int fr,to;
	for(int i=1;i<N;i++) 
	{
		scanf("%d%d",&fr,&to);
		s[fr].push_back(to);
		s[to].push_back(fr);
	}
}
int tot=0;
void dfs(int x)
{
	dep[x]=dep[fa[x]]+1;siz[x]=1;
	first[x]=++tot;
	for(int i=0;i<s[x].size();i++)
	{
		int v=s[x][i];
		if(v==fa[x]) continue;
		fa[v]=x;
		dfs(v);
		siz[x]+=siz[v];
	}
	en[x]=tot;
}
queue<int> Q;
int built(int l,int r)
{
	if(l>r) return -1;
	int x=++pos;
	int mid=(l+r)/2;
	tr[x].l=l;tr[x].r=r;
	tr[x].lson=tr[x].rson=-1;
	if(l<r)
	{
		tr[x].lson=built(l,mid);
		tr[x].rson=built(mid+1,r);
	}
	return x;
}
int change(int rt,int g)
{
	if(rt==-1) return -1;
	int x=++pos;
	tr[x]=tr[rt];
	tr[x].sum+=siz[g]-1;
	int mid=(tr[x].l+tr[x].r)/2;
	if(mid<first[g]) tr[x].rson=change(tr[x].rson,g);
	else tr[x].lson=change(tr[x].lson,g);
	return x;
}
int maxd=0;
void prepare()
{
	dfs(1);
	Q.push(1);
	root[1]=built(1,N);
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();maxd=max(maxd,dep[x]);
		if(!root[dep[x]]) root[dep[x]]=change(root[dep[x]-1],x);
		else root[dep[x]]=change(root[dep[x]],x);
		for(int i=0;i<s[x].size();i++)
		{
			int v=s[x][i];
			if(dep[v]!=dep[x]+1) continue;
			Q.push(v);
		}
	}
}
LL query(int rt,int t,int l,int r)
{
	if(tr[rt].r<l||tr[rt].l>r) return 0;
	if(l<=tr[rt].l&&tr[rt].r<=r) return tr[rt].sum-tr[t].sum;
	LL re=0;
	re=query(tr[rt].lson,tr[t].lson,l,r)+query(tr[rt].rson,tr[t].rson,l,r);
	return re;
}
void work()
{
	int a,k;
	LL ans=0;
	for(int i=1;i<=M;i++)
	{
		scanf("%d%d",&a,&k);
		ans=1ll*min(k,dep[a]-1)*(siz[a]-1);
		ans+=query(root[min(dep[a]+k,maxd)],root[dep[a]],first[a],en[a]);
		printf("%lld\n",ans);
	}
}
int main()
{
	freopen("laugh.in","r",stdin);
	freopen("laugh.out","w",stdout);
	read();
	prepare();
	//for(int i=1;i<=maxd;i++) cout<<root[i]<<" ";
	//cout<<endl;
	work();
	return 0;
}