[湖南集训]谈笑风生

很显然答案只有两种情况

  • $b$ 是 $a$ 的祖先时, $c$ 可以是以 $a$ 为根的子树中的任意一个
  • $a$ 是 $b$ 的祖先时, $c$ 可以使以 $b$ 为根的子树中的任意一个

第一种情况很好解决,主要是第二种情况不太容易处理

我们需要保证 $dis_b-dis_a\le k$ ,并且对于每个 $b$ 要加上 $size_b-1$ 的贡献

考虑依旧按照DFS的顺序建一棵主席树,对于节点 $i$ 插入主席树的键值为 $dis_i$,权值为 $size_i-1$

所以建出来的主席树只需要对 $a$ 这棵子树查询 $[dis_a+1,dis_a+k]$ 的权值和

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
/***************************************************************
File name: P3899.cpp
Author: ljfcnyali
Create time: 2019年09月14日 星期六 15时45分55秒
***************************************************************/
#include<bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for ( int i = (a), _end_ = (b); i <= _end_; ++ i )
#define mem(a) memset ( (a), 0, sizeof ( a ) )
#define str(a) strlen ( a )
#define ls(x) Tree[x].l
#define rs(x) Tree[x].r
#define int long long
typedef long long LL;

const int maxn = 600010;

int n, q, Begin[maxn], Next[maxn], To[maxn], e, Root[maxn];
int size[maxn], dfn[maxn], id[maxn], tot, cnt, dis[maxn], N;
struct node
{
int l, r, sum;
} Tree[maxn << 4];

inline void add(int u, int v) { To[++ e] = v; Next[e] = Begin[u]; Begin[u] = e; }

inline void DFS(int u, int fa)
{
dfn[u] = ++ cnt; id[cnt] = u; size[u] = 1;
for ( int i = Begin[u]; i; i = Next[i] )
{
int v = To[i]; if ( v == fa ) continue ;
dis[v] = dis[u] + 1; N = max(N, dis[v]); DFS(v, u);
size[u] += size[v];
}
}

inline int Modify(int now, int l, int r, int pos, int val)
{
int root = ++ tot; Tree[root] = Tree[now];
Tree[root].sum += val;
if ( l == r ) return root;
int Mid = l + r >> 1;
if ( pos <= Mid ) ls(root) = Modify(ls(root), l, Mid, pos, val);
else rs(root) = Modify(rs(root), Mid + 1, r, pos, val);
return root;
}

inline int Query(int p, int q, int l, int r, int L, int R)
{
if ( !q || Tree[q].sum - Tree[p].sum == 0 ) return 0;
if ( L <= l && r <= R ) return Tree[q].sum - Tree[p].sum;
int Mid = l + r >> 1, sum = 0;
if ( L <= Mid ) sum += Query(ls(p), ls(q), l, Mid, L, R);
if ( Mid < R ) sum += Query(rs(p), rs(q), Mid + 1, r, L, R);
return sum;
}

signed main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
scanf("%lld%lld", &n, &q);
REP(i, 1, n - 1) { int u, v; scanf("%lld%lld", &u, &v); add(u, v); add(v, u); }
dis[1] = 1; DFS(1, 0);
REP(i, 1, n) Root[i] = Modify(Root[i - 1], 1, N, dis[id[i]], size[id[i]] - 1);
// REP(i, 1, n) printf("%lld ", Tree[Root[i]].sum); puts("");
REP(i, 1, q)
{
int p, k, x; scanf("%lld%lld", &p, &k);
if ( dis[p] - 1 <= k ) x = dis[p] - 1;
else x = k;
int ans = x * (size[p] - 1);
// printf("%lld %lld %lld ", dfn[p], dfn[p] + size[p] - 1, ans);
// printf("%lld %lld ", min(N, dis[p] + 1), min(N, dis[p] + k));
ans += Query(Root[dfn[p]], Root[dfn[p] + size[p] - 1], 1, N, min(N, dis[p] + 1), min(N, dis[p] + k));
printf("%lld\n", ans);
}
return 0;
}