记录编号	419992	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[BZOJ3653]谈笑风生	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	5.370 s
提交时间	2017-07-03 18:20:13	内存使用	480.94 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e6+10,M=3e7+10;
struct node{int l,r;ll v;}nd[M];
int root[N],id;
int add(int x,int l,int r,int p,int d){
	int now=++id;
	nd[now]=nd[x];
	nd[now].v+=d;
	if (l==r) return now;
	int mid=(l+r)>>1;
	if (p>mid) nd[now].r=add(nd[x].r,mid+1,r,p,d);
		else nd[now].l=add(nd[x].l,l,mid,p,d);
	return now; 
}
ll query(int x,int l,int r,int L,int R){
	if (l>=L&&r<=R) return nd[x].v;
	int mid=(l+r)>>1;ll ans=0;
	if (L<=mid) ans+=query(nd[x].l,l,mid,L,R);
	if (R>mid) ans+=query(nd[x].r,mid+1,r,L,R);
	return ans;
}
int merge(int x,int y,int l,int r){
	if (!x||!y) return x|y;
	int now=++id;
	nd[now].v=nd[x].v+nd[y].v;
	if (l==r) return now;
	int mid=(l+r)>>1;
	nd[now].l=merge(nd[x].l,nd[y].l,l,mid);
	nd[now].r=merge(nd[x].r,nd[y].r,mid+1,r);
	return now;
}
int n,q,w[N],head[N],next[N];
void add(int f,int t){
	static int cnt=0;
	w[++cnt]=t;
	next[cnt]=head[f];
	head[f]=cnt;
}
int dep[N],size[N];
void dfs(int x,int fa){
	size[x]=1;
	for (int i=head[x];i;i=next[i]){
		int v=w[i];
		if (v==fa) continue;
		dep[v]=dep[x]+1;
		dfs(v,x);
		size[x]+=size[v];
		root[x]=merge(root[x],root[v],1,n);
	}
	root[x]=add(root[x],1,n,dep[x],size[x]-1);
}
int read(){
	int x=0;char ch=getchar();
	while (ch>'9'||ch<'0') ch=getchar();
	while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x;
}
int main()
{
	freopen("laugh.in","r",stdin);
	freopen("laugh.out","w",stdout);
	scanf("%d%d",&n,&q);
	for (int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);add(v,u);
	}
	dep[1]=1;dfs(1,0);
	for (int i=1;i<=q;i++){
		int p,k;
		scanf("%d%d",&p,&k);
		ll ans=ll(size[p]-1)*min(k,dep[p]-1);
		if (dep[p]<n) ans+=query(root[p],1,n,dep[p]+1,min(dep[p]+k,n));
		printf("%lld\n",ans);
	}
	return 0;
}