CF2257C Spying on the Beaver

给定一棵有根树 $ ^{\text{∗}} $，包含 $ n $ 个顶点，编号为 $ 1 $ 到 $ n $。顶点 $ 1 $ 是树的根节点。海狸一开始位于根节点，会在树中行进至某一个编号为 $ a_1, \ldots, a_m $ 的“海狸坝”所在的顶点。 你需要确定海狸最终到达的是这 $ m $ 个顶点中的哪一个。为此，你可以在树上的任意边上安装摄像头。如果海狸经过了安装摄像头的边，你就能观测到这一行为。为便于理解，我们假设在海狸的所有移动结束之后，你会收到一个按顺序记录有摄像头的所有被穿越边的列表。 因为摄像头非常昂贵，需要用最少的摄像头，且能够唯一判断出海狸最终去向。你的任务是输出最小所需摄像头数量 $ k $，以及应当安装摄像头的所有边。 $ ^{\text{∗}} $ 有根树是一种树，其中有一个特殊的顶点，被称为根节点。

每组测试数据包含若干组数据。第一行包含测试数据组数 $ t $（$ 1 \le t \le 2 \cdot 10^4 $）。以下是每一组的数据描述。 每组测试数据的第一行包含一个整数 $ n $（$ 2 \le n \le 10^5 $）。 第二行包含 $ n-1 $ 个整数 $ p_2, \ldots, p_n $，表示顶点 $ 2 $ 到 $ n $ 的父节点编号（$ 1 \le p_i < i $，$ 2 \le i \le n $）。 第三行包含一个整数 $ m $，表示有 $ m $ 个顶点有海狸坝（$ 1 \le m \le n $）。 第四行包含 $ m $ 个不同的整数 $ a_1, \ldots, a_m $，表示这些顶点的编号（$ 1 \le a_i \le n $，$ 1 \le i \le m $）。 保证所有测试数据中 $ n $ 的总和不超过 $ 10^5 $。

对于每组测试数据，输出一行。首先输出整数 $ k $，表示所需最少摄像头数量。接下来，同一行中输出这 $ k $ 条边中每一条边对应的顶点编号 $ u $，即应在 $ u $ 和其父节点 $ p_u $ 之间安装摄像头的顶点 $ u $。 如果有多种方案，输出任意一种均可。

在第一个测试用例中，由于树上只有一个坝，无需安装摄像头，海狸必然前往该坝。 在第二个测试用例中，每个顶点上都有水坝，因此每条边都需安装摄像头。 在第三个测试用例中，水坝位于两个相邻的顶点，通过在这两个顶点之间的那条边上安装摄像头，可以唯一确定海狸的去向。 由 ChatGPT 5 翻译