P15577 [USACO26FEB] Picking Flowers G

**注意：本题的时间限制为 3 秒，是默认时间的 1.5 倍。** 农夫约翰的农场结构可以表示为一个有 $N$ 个顶点和 $M$ 条无权重边的连通无向图（$2 \leq N \leq 2 \cdot 10^5$，$N - 1 \leq M \leq 2 \cdot 10^5$）。初始时，农夫约翰在他的谷仓，即农场 $1$。 初始时，农场 $s_1, s_2, \ldots, s_K$ 包含花田，而农场 $d_1, d_2, \ldots, d_L$ 是目标农场。FJ 称一条路径为 **美丽的**，如果它满足： - 起点是农场 $1$。 - 终点是某个目标农场 $x$。 - 不存在从农场 $1$ 到农场 $x$ 的更短路径。 - FJ 沿途访问了所有花田。 FJ 可以挥动他的魔杖，使得最多再有一个农场（如果原本没有）变成花田。然而，FJ 并不是很果断。对于编号从 $2$ 到 $N$ 的农场 $f$，在 FJ 临时让农场 $f$ 变成花田后，判断是否存在一条美丽的路径。 注意，有多个测试用例，每个用例需独立处理。

第一行包含 $T$（$1 \leq T \leq 100$），表示独立测试用例的数量。 每个测试用例的第一行包含 $N$、$M$、$K$ 和 $L$（$0 \leq K \leq N - 1$，$1 \leq L \leq N - 1$）。 接下来的一行包含 $s_1, s_2, \ldots, s_K$（$2 \leq s_i \leq N$，所有 $s_i$ 互不相同）。 接下来的一行包含 $d_1, d_2, \ldots, d_L$（$2 \leq d_i \leq N$，所有 $d_i$ 互不相同）。 接下来的 $M$ 行每行包含 $u$ 和 $v$，表示农场 $u$ 和 $v$ 之间有一条无向边。所有边的长度视为相等。保证没有重边或自环。 保证所有测试用例的 $N$ 之和以及 $M$ 之和均不超过 $10^6$。

对于每个测试用例，输出一个长度为 $N - 1$ 的二进制字符串。字符串的第 $i$ 个字符应为 $1$，如果对于第 $i+1$ 号农场的答案为真（即存在美丽路径）。

#### 样例 1 解释 由于 $5$ 是唯一的目标农场，如果第 $i$ 号农场位于从 $1$ 到 $5$ 的任意一条最短路径上，则答案为真。 从 $1$ 到 $5$ 有两条最短路径，分别是 $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5$ 和 $1 \rightarrow 2 \rightarrow 3 \rightarrow 6 \rightarrow 5$。 由于原本没有农场包含花田，因此对于农场 $i$，如果它位于上述两条路径中的至少一条上，则答案为真。 #### 样例 2 解释 有两个目标农场：$5$ 和 $3$。由于原本没有农场包含花田，第 $i$ 号农场必须位于到 $5$ 或 $3$ 的最短路径上。因为农场 $2$ 位于到农场 $5$ 的一条最短路径上，所以对于农场 $2$ 答案为真。显然，农场 $3$ 位于到农场 $3$ 的最短路径上，农场 $5$ 位于到农场 $5$ 的最短路径上。 #### 样例 3 解释 对于第一个测试用例，如果 FJ 能在某条到农场 $4$ 的最短路径上依次经过农场 $i$、农场 $2$ 和农场 $3$（顺序不限），则对于第 $i$ 号农场答案为真。可以证明，对于所有农场答案均为真。 ### 评分标准 - 输入 4-6：$K = 0$ 且 $L = 1$ - 输入 7-9：$K = 0$ - 输入 10-23：无额外限制 题目来源：Chongtian Ma 翻译由 DeepSeek 完成