记录编号	454903	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[BZOJ3653]谈笑风生	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	4.124 s
提交时间	2017-09-30 10:57:13	内存使用	95.08 MiB

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
inline int read(){
	int sum(0);
	char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum;
}
struct edge{
	int e;
	edge *n;
}a[600005],*pre[300005];
int tot;
inline void insert(int s,int e){
	a[++tot].e=e;
	a[tot].n=pre[s];
	pre[s]=&a[tot];
}
typedef long long L;
int n,q;
int timee;
int l[300005],r[300005],pos[300005],size[300005],fa[300005],dep[300005];
inline void dfs(int u){
	l[u]=++timee;
	pos[timee]=u;
	size[u]=1;
	for(edge *i=pre[u];i;i=i->n){
		int e(i->e);
		if(e!=fa[u]){
			fa[e]=u;
			dep[e]=dep[u]+1;
			dfs(e);
			size[u]+=size[e];
		}
	}
	r[u]=timee;
}
int mx,cnt;
int rt[300005],lch[6000005],rch[6000005];
L sum[6000005];
inline void update(int &x,int las,int pos,int w,int l,int r){
	x=++cnt;
	lch[x]=lch[las];
	rch[x]=rch[las];
	sum[x]=sum[las]+w;
	if(l==r)
		return;
	int mid((l+r)>>1);
	if(pos<=mid)
		update(lch[x],lch[las],pos,w,l,mid);
	else
		update(rch[x],rch[las],pos,w,mid+1,r);
}
inline L query(int x,int y,int ll,int rr,int l,int r){
	if(ll<=l&&r<=rr)
		return sum[y]-sum[x];
	int mid((l+r)>>1);
	L ret(0);
	if(ll<=mid)
		ret+=query(lch[x],lch[y],ll,rr,l,mid);
	if(mid<rr)
		ret+=query(rch[x],rch[y],ll,rr,mid+1,r);
	return ret;
}
inline int gg(){
	freopen("laugh.in","r",stdin);
	freopen("laugh.out","w",stdout);
	n=read(),q=read();
	for(int i=1;i<n;++i){
		int x(read()),y(read());
		insert(x,y),insert(y,x);
	}
	dfs(1);
	for(int i=1;i<=n;++i)
		mx=max(dep[i],mx);
	for(int i=1;i<=n;++i)
		update(rt[i],rt[i-1],dep[pos[i]],size[pos[i]]-1,0,mx);
	while(q--){
		int x(read()),y(read());
		L ans(0);
		ans+=(L)(size[x]-1)*(L)min(dep[x],y);
//		cout<<x<<' '<<size[x]<<' '<<dep[x]<<' '<<y<<endl;
//		cout<<ans<<endl;
		ans+=query(rt[l[x]],rt[r[x]],dep[x]+1,dep[x]+y,0,mx);
//		cout<<ans<<endl;
//		ans-=query(rt[l[x]-1],dep[x]+1,dep[x]+y,0,mx);
//		cout<<ans<<endl;
		printf("%lld\n",ans);
	}
}
int K(gg());
int main(){;}