1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

#include <bits/stdc++.h>

namespace rvalue{
	const int MAXV=3e5+10;
	const int MAXE=1e6+10;
	typedef long long intEx;

	struct Edge{
		int from;
		int to;
		Edge* next;
	};
	Edge E[MAXE];
	Edge* head[MAXV];
	Edge* top=E;

	struct Node{
		int l;
		int r;
		intEx sum;
		Node* lch;
		Node* rch;
		Node(int,int);
		void Insert(int,int);
		intEx Query(int,int);
	};
	Node* N[MAXV];

	int n;
	int q;
	int deep[MAXV];
	int size[MAXV];
	intEx ans[MAXV];

	int ReadInt();
	void Insert(int,int);
	void DFS(int,int,int);
	Node* Merge(Node*,Node*);

	int main(){
		n=ReadInt(),q=ReadInt();
		for(int i=1;i<n;i++){
			int a=ReadInt(),b=ReadInt();
			Insert(a,b);
			Insert(b,a);
		}
		DFS(1,0,1);
		for(int i=0;i<q;i++){
			int root=ReadInt();
			int k=ReadInt();
			intEx ans=N[root]->Query(deep[root]+1,std::min(deep[root]+k,n));
			ans+=1ll*std::min(k,deep[root]-1)*(size[root]-1);
			printf("%lld\n",ans);
		}
		return 0;
	}

	void DFS(int root,int prt,int deep){
		rvalue::size[root]=1;
		rvalue::deep[root]=deep;
		N[root]=new Node(1,n);
		for(Edge* i=head[root];i!=NULL;i=i->next){
			if(i->to!=prt){
				DFS(i->to,root,deep+1);
				rvalue::size[root]+=rvalue::size[i->to];
				N[root]=Merge(N[root],N[i->to]);
			}
		}
		N[root]->Insert(rvalue::deep[root],size[root]-1);
	}

	Node::Node(int l,int r):l(l),r(r),sum(0),lch(NULL),rch(NULL){}

	Node* Merge(Node* L,Node* R){
		if(L==NULL)
			return R;
		if(R==NULL)
			return L;
		Node* cur=new Node(L->l,R->r);
		cur->sum=L->sum+R->sum;
		cur->lch=Merge(L->lch,R->lch);
		cur->rch=Merge(L->rch,R->rch);
		return cur;
	}

	intEx Node::Query(int l,int r){
		if(l<=this->l&&this->r<=r)
			return this->sum;
		else{
			int mid=(this->l+this->r)>>1;
			intEx ans=0;
			if(l<=mid&&this->lch!=NULL)
				ans+=this->lch->Query(l,r);
			if(mid+1<=r&&this->rch!=NULL)
				ans+=this->rch->Query(l,r);
			return ans;
		}
	}

	void Node::Insert(int x,int d){
		this->sum+=d;
		if(this->l!=this->r){
			int mid=(this->l+this->r)>>1;
			if(x<=mid){
				if(this->lch==NULL)
					this->lch=new Node(this->l,mid);
				this->lch->Insert(x,d);
			}
			else{
				if(this->rch==NULL)
					this->rch=new Node(mid+1,this->r);
				this->rch->Insert(x,d);
			}
		}
	}

	inline void Insert(int from,int to){
		top->from=from;
		top->to=to;
		top->next=head[from];
		head[from]=top++;
	}
	
	inline int ReadInt(){
		int x=0;
		register char ch=getchar();
		while(!isdigit(ch))
			ch=getchar();
		while(isdigit(ch)){
			x=x*10+ch-'0';
			ch=getchar();
		}
		return x;
	}
}

int main(){
	freopen("laugh.in","r",stdin);
	freopen("laugh.out","w",stdout);
	rvalue::main();
	return 0;
}