[BZOJ3653]谈笑风生

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;

const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {
	if(Head == Tail) {
		int l = fread(buffer, 1, BufferSize, stdin);
		Tail = (Head = buffer) + l;
	}
	return *Head++;
}
int read() {
	int x = 0, f = 1; char c = Getchar();
	while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = Getchar(); }
	while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = Getchar(); }
	return x * f;
}

#define maxn 300010
#define maxm 600010
#define maxnode 6000010
#define LL long long

int n, m, head[maxn], nxt[maxm], to[maxm];
void AddEdge(int a, int b) {
	to[++m] = b; nxt[m] = head[a]; head[a] = m;
	swap(a, b);
	to[++m] = b; nxt[m] = head[a]; head[a] = m;
	return ;
}

int siz[maxn], dep[maxn], dl[maxn], dr[maxn], uid[maxn], clo;
void build(int u, int fa) {
	dl[u] = ++clo; uid[clo] = u;
	siz[u] = 1;
	for(int e = head[u]; e; e = nxt[e]) if(to[e] != fa) {
		dep[to[e]] = dep[u] + 1;
		build(to[e], u);
		siz[u] += siz[to[e]];
	}
	dr[u] = clo;
	return ;
}

int rt[maxn], ToT, lc[maxnode], rc[maxnode];
LL sumv[maxnode];
void update(int& y, int x, int l, int r, int p, int v) {
	sumv[y = ++ToT] = sumv[x] + v;
	if(l == r) return ;
	int mid = l + r >> 1; lc[y] = lc[x]; rc[y] = rc[x];
	if(p <= mid) update(lc[y], lc[x], l, mid, p, v);
	else update(rc[y], rc[x], mid + 1, r, p, v);
	return ;
}
LL query(int o, int l, int r, int ql, int qr) {
	if(!o) return 0;
	if(ql <= l && r <= qr) return sumv[o];
	int mid = l + r >> 1; LL ans = 0;
	if(ql <= mid) ans += query(lc[o], l, mid, ql, qr);
	if(qr > mid) ans += query(rc[o], mid + 1, r, ql, qr);
	return ans;
}

int main() {
	n = read(); int q = read();
	for(int i = 1; i < n; i++) {
		int a = read(), b = read();
		AddEdge(a, b);
	}
	
	dep[1] = 1; build(1, 0);
	for(int i = 1; i <= clo; i++) update(rt[i], rt[i-1], 1, n, dep[uid[i]], siz[uid[i]] - 1);
	while(q--) {
		int u = read(), k = read();
		LL ans = (LL)(siz[u] - 1) * min(k, dep[u] - 1);
		ans += query(rt[dr[u]], 1, n, dep[u] + 1, dep[u] + k) - query(rt[dl[u]-1], 1, n, dep[u] + 1, dep[u] + k);
		printf("%lld\n", ans);
	}
	
	return 0;
}