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
| #include<bits/stdc++.h>
#define RG register
#define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define clear(x, y) memset(x, y, sizeof(x));
using namespace std;
inline int read()
{
int data = 0, w = 1;
char ch = getchar();
while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if(ch == '-') w = -1, ch = getchar();
while(ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();
return data*w;
}
const int maxn(300010);
struct node { int id, k; };
vector<node> q[maxn];
struct edge { int next, to; } e[maxn << 1];
int head[maxn], e_num, Dep[maxn], dep[maxn], fa[maxn], heavy[maxn], n, Q, size[maxn];
inline void add_edge(int from, int to) { e[++e_num] = {head[from], to}; head[from] = e_num; }
long long pool[maxn], *s[maxn], *pos = pool, ans[maxn];
void dfs(int x)
{
Dep[x] = dep[x] = dep[fa[x]] + 1; size[x] = 1;
for(RG int i = head[x]; i; i = e[i].next)
{
int to = e[i].to; if(to == fa[x]) continue;
fa[to] = x; dfs(to); size[x] += size[to];
if(Dep[heavy[x]] < Dep[to]) heavy[x] = to;
}
if(heavy[x]) Dep[x] = Dep[heavy[x]];
}
void Solve(int x)
{
s[x][0] = size[x] - 1;
if(!heavy[x]) return;
s[heavy[x]] = s[x] + 1;
Solve(heavy[x]); s[x][0] += s[heavy[x]][0];
for(RG int i = head[x]; i; i = e[i].next)
{
int to = e[i].to; if(to == fa[x] || to == heavy[x]) continue;
s[to] = pos; pos += Dep[to] - dep[to] + 1; Solve(to);
for(RG int j = 0; j <= Dep[to] - dep[to]; j++) s[x][j + 1] += s[to][j];
s[x][0] += s[to][0];
}
for(RG vector<node>::iterator it = q[x].begin(); it != q[x].end(); ++it)
{
int id = it -> id, k = it -> k;
ans[id] += 1ll * (size[x] - 1) * min(dep[x] - 1, k);
if(k >= Dep[x] - dep[x]) ans[id] += s[x][0] - size[x] + 1;
else ans[id] += s[x][0] - size[x] - s[x][k + 1] + 1;
}
}
int main()
{
#ifndef ONLINE_JUDGE
file(cpp);
#endif
n = read(); Q = read();
for(RG int i = 1, a, b; i < n; i++)
a = read(), b = read(), add_edge(a, b), add_edge(b, a);
dfs(1);
for(RG int i = 1, a, b; i <= Q; i++)
a = read(), b = read(), q[a].push_back({i, b});
s[1] = pos; pos += Dep[1]; Solve(1);
for(RG int i = 1; i <= Q; i++) printf("%lld\n", ans[i]);
return 0;
}
|