P13248 [GCJ 2014 #1A] Full Binary Tree

树是一种**连通且无环**的图。 **有根树**是一种特殊的树，它指定了一个特殊的点作为根。在有根树中，如果存在一条边连接 $X$ 和 $Y$，且 $X$ 到根节点的最短路径长度小于 $Y$ 到根节点的最短路径长度，那么我们称 $Y$ 是 $X$ 的**子节点**。 **满二叉树**是一种有根树，其中每个节点要么恰好有 $2$ 个子节点，要么没有子节点。 你将获得一棵含有 $N$ 个节点的树 $G$（节点编号为 $1$ 到 $N$）。你可以**删除任意数量的节点**，每当你删除一个节点，与其相连的边也会一并删除。你的目标是：通过删除尽可能少的节点，使得剩下的节点可以构成一棵**满二叉树**（以剩余节点中的某个点作为根）。

输入的第一行是测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行是一个整数 $N$，表示树中节点的数量。接下来的 $N - 1$ 行，每行包含两个用空格分隔的整数 $X_i$ 和 $Y_i$，表示树 $G$ 中存在一条无向边连接 $X_i$ 和 $Y_i$。

对于每个测试用例，输出一行 `"Case #x: y"`，其中 $x$ 是当前测试用例的编号（从 $1$ 开始），$y$ 是为了将 $G$ 转换为一棵满二叉树所需删除的最少节点数。

**样例说明** - 在第一个样例中，如果将节点 $1$ 作为根，那么 $G$ 已经是一棵满二叉树，因此不需要做任何操作。 - 在第二个样例中，可以删除节点 $3$ 和 $7$，然后以节点 $2$ 为根，就能形成一棵满二叉树。 - 在第三个样例中，可以删除节点 $1$，然后以节点 $3$ 为根，构成一棵满二叉树（也可以选择删除节点 $4$，并将 $2$ 作为根，同样成立）。 ## 限制条件 - $1 \leq T \leq 100$ - $1 \leq X_i, Y_i \leq N$ - 每个测试用例保证输入构成一棵合法的连通树 **小数据集（9 分）** - 时间限制：~~60~~ 3 秒 - $2 \leq N \leq 15$ **大数据集（21 分）** - 时间限制：~~120~~ 10 秒 - $2 \leq N \leq 1000$ 翻译由 ChatGPT-4o 完成。