P16890 [GKS 2022 #F] Water Container System

有一个由 $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$ 是在处理完所有查询后被完全填满的容器数量。

在样例 #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 完成