题目描述

有一个由 $N$ 个相同容器组成的水容器系统，该系统可以表示为一棵树，其中每个容器是一个顶点。容器之间由 $N-1$ 条双向管道连接。相互连接的两个容器总是位于相邻的层级。形式化地说，如果两个容器 $a$ 和 $b$ 相连，则 $|\text{level}_a - \text{level}_b| = 1$。容器 $1$ 位于最底层。每个容器恰好连接一个下方层级的容器（唯一的例外是容器 $1$，它下方没有连接），但可以连接零个或多个上方层级的容器。每个容器的最大容量为 $1$ 升，初始时所有容器都是空的。假设管道的容量为 $0$ 升，即它们不储存任何水，只允许水以任意方向通过。

下图是一个水容器系统的示例：

:::align{center} :::

系统的第一层只有一个容器，即容器 $1$（根）。容器 $1$ 连接到位于上一层（第 $2$ 层）的容器 $2$ 和容器 $3$。容器 $2$ 还连接到位于第 $3$ 层的容器 $4$。

你会得到 $Q$ 个查询。每个查询包含一个整数 $i$，表示一个容器。对于每个查询，向容器 $i$ 中额外添加 $1$ 升水。

下图展示了不同条件下系统中水的流动情况：

:::align{center} :::

• 第 $1$ 步：向容器 $3$ 添加 $1$ 升水后，水向下流动，因为较低层的水容器还是空的。
• 第 $2$ 步：再次向容器 $3$ 添加 $1$ 升水后，水向下流动，但由于容器 $1$ 已完全填满，水在容器 $2$ 和容器 $3$ 之间均匀分配。
• 第 $3$ 步：再次向容器 $3$ 添加 $1$ 升水后，容器 $2$ 和容器 $3$ 均完全填满。
• 第 $4$ 步：再次向容器 $3$ 添加 $1$ 升水后，水被向上推至容器 $4$，容器 $4$ 随即被完全填满。

如上例所示，同一层的容器将具有相同的水量。请找出在处理完所有查询后，被完全填满的容器数量。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。

每个测试用例的第一行包含两个整数 $N$ 和 $Q$，其中 $N$ 是容器的数量，$Q$ 是查询的数量。

接下来的 $N-1$ 行，每行包含两个整数 $i$ 和 $j$（$1 \le i, j \le N$，$i \ne j$），表示第 $i$ 个水容器与第 $j$ 个水容器相连。

接下来的 $Q$ 行，每行包含一个整数 $i$（$1 \le i \le N$），表示应向哪个容器添加 $1$ 升水。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是在处理完所有查询后被完全填满的容器数量。

2
1 1
1
3 2
1 2
1 3
1
2

Case #1: 1
Case #2: 1

2
4 4
1 2
1 3
2 4
3
3
3
3
5 2
1 2
5 3
3 1
2 4
4
5

Case #1: 4
Case #2: 1

提示

在样例 #1 中，有 $N = 1$ 个水容器。向容器 $1$ 添加 $1$ 升水后，被完全填满的容器数量为 $1$。

在样例 #2 中，有 $N = 3$ 个水容器。处理完所有查询后，被完全填满的容器数量为 $1$。

:::align{center} :::

• 向容器 $1$ 添加 $1$ 升水后：容器 $1$ 被完全填满，其余容器为空。
• 向容器 $2$ 添加 $1$ 升水后：容器 $1$ 被完全填满，容器 $2$ 和 $3$ 部分填满。

限制条件

$1 \le T \le 100$。

$1 \le Q \le N$。

保证给出的水容器系统是一棵树。

测试集 1

$1 \le N \le 65535$。

水容器系统是一棵完美二叉树。

测试集 2

$1 \le N \le 10^4$。

翻译由 DeepSeek V4 Pro 完成