アメカーの部屋

时空限制#

C/C++: 1s/256MB

其他语言：2s/512MB

题目背景#

「所谓七影蝶，就是人的记忆残片……」

「生前留下过迷恋和悔恨的人们的『记忆』，就会以蝴蝶的姿态存在于这个世上。」

「……虽说只是记忆，但这并不是能留在世上的东西。」

「需要有人把它们指引到本来应该归返的地方。」

「这就是代代由空门家掌管的山之祭。」

「……有一份记忆，我是无论如何都必须找到的……」

为了完成空门家的职责和寻找那份无论如何都必须找到的记忆，空门苍需要在山之祭期间，将散落在山间的七影蝶指引向 迷途之橘。

题目描述#

鸟白岛的山路可以看作一棵以节点 $1$ 为根的树¹，共有 $n$ 个节点。

树的每个叶节点的深度（即到根节点的距离）均相同。

山路崎岖，夜色幽晦。安全起见，苍的行动必须遵循以下规则：

1. 苍在 $0$ 时刻 从 任意一个叶节点 出发，目标是到达「迷途之橘」所在山顶的根节点 $1$。
2. 苍可以花费 $1$ 的时间，从当前节点移动到其 父节点。
3. 苍可以 至多一次 借助稻荷的能力：花费 $1$ 的时间，从当前深度为 $d$ 的非根节点移动到深度为 $d-1$ 的 任意节点。
4. 当苍处于某个节点时，她能成功指引该位置的所有尚未消失（即当前时间 $\le t_i$）的七影蝶。

为了尽可能多地让七影蝶归返，请你告诉苍最多能指引多少只七影蝶。

输入格式#

每个测试包含多组测试用例。

• 第一行包含一个整数 $T$ ($1 ≤ T ≤ 10^4$)，表示测试用例的数量。
• 对于每个测试用例：
  • 第一行包含两个整数 $n$ , $m$ ($2 \le n \le 2×10^5$, $0 \le m \le 2×10^5$)，分别表示树的节点数和七影蝶的数量。
  • 接下来 $n-1$ 行，每行包含两个整数 $u_i$ , $v_i$ ($1 \le u_i, v_i \le n$)，表示树的一条边。
  • 接下来 $m$ 行，每行包含两个整数 $a_i$ , $t_i$ ($1 \le a_i \le n$ , $0 \le t_i \le n$)，表示第 $i$ 只七影蝶的位置和消失时间。

数据保证所有测试用例中 $n$ 的总和与 $m$ 的总和均不超过 $2×10^5$，且保证给定的边构成一棵树，所有叶节点深度相同。

输出格式#

对于每个测试用例，输出 $1$ 个整数，表示苍最多能指引的七影蝶数。

1
3
2
3 2
3
1 2
4
1 3
5
3 0
6
1 1
7
6 3
8
1 2
9
1 3
10
2 4
11
2 5
12
3 6
13
6 1
14
2 1
15
1 1
16
8 5
17
1 2
18
1 3
19
2 4
20
3 6
21
4 5
22
6 7
23
6 8
24
5 2
25
4 2
26
6 8
27
3 1
28
1 5

1
2
2
2
3
3