P14329 [JOI2022 预选赛 R2] 交易计划 / Trade Plan

JOI 合众国有 $ N $ 个城市，编号从 $ 1 $ 到 $ N $；另有 $ M $ 条道路，编号从 $ 1 $ 到 $ M $。第 $ i $ 条道路（$ 1 \le i \le M $）双向连接城市 $ U_i $ 与城市 $ V_i $。 JOI 合众国由 $ K $ 个州组成，各州编号从 $ 1 $ 到 $ K $。城市 $ j $（$ 1 \le j \le N $）属于州 $ S_j $。此外，每个州至少包含一个城市。 JOI 合众国的产业大臣 K 理事长计划进行 $ Q $ 次交易。第 $ k $ 次交易（$ 1 \le k \le Q $）是指将特产品从城市 $ A_k $ 运送到城市 $ B_k $，途中可经过若干道路或城市。但仅允许经过属于州 $ S_{A_k} $ 或州 $ S_{B_k} $ 的城市（当 $ S_{A_k} = S_{B_k} $ 时，仅允许经过州 $ S_{A_k} $ 的城市）；若路径经过不属于这两个州的任何城市，特产品将被窃取。 K 理事长希望调查是否存在一条运输路径，使得特产品在交易过程中不被窃取。当给出城市与道路的布局、州的归属信息以及各次交易的信息时，请编写程序，判断每次交易是否可能安全完成。

输入通过标准输入以如下格式给出： $ N $ $ M $ $ K $ $ U_1 $ $ V_1 $ $ U_2 $ $ V_2 $ $ \vdots $ $ U_M $ $ V_M $ $ S_1 $ $ S_2 $ $ \cdots $ $ S_N $ $ Q $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_Q $ $ B_Q $

在标准输出中，输出 $ Q $ 行。第 $ k $ 行（$ 1 \le k \le Q $）应输出：若第 $ k $ 次交易中特产品可以安全送达，则输出 $ 1 $；否则输出 $ 0 $。

### 样例 1 解释 - 第 1 次交易是指：仅通过属于州 1 或州 2 的城市，将特产品从城市 1 运送到城市 2。由于路径“城市 1 → 城市 2”满足条件，因此输出 $ 1 $。 - 第 2 次交易是指：仅通过属于州 1 的城市，将特产品从城市 1 运送到城市 3。不存在满足条件的运输路径，因此输出 $ 0 $。 - 第 3 次交易是指：仅通过属于州 1 或州 2 的城市，将特产品从城市 1 运送到城市 4。由于路径“城市 1 → 城市 2 → 城市 3 → 城市 4”满足条件，因此输出 $ 1 $。 本输入样例满足子任务 1、3、4 的约束条件。 ### 数据范围 - $ 2 \le N \le 400\,000 $。 - $ 1 \le M \le 400\,000 $。 - $ 1 \le K \le N $。 - $ 1 \le U_i < V_i \le N $（$ 1 \le i \le M $）。 - $ (U_i, V_i) \ne (U_j, V_j) $（$ 1 \le i < j \le M $）。 - $ 1 \le S_j \le K $（$ 1 \le j \le N $）。 - 对于任意 $ l $（$ 1 \le l \le K $），均存在某个 $ j $（$ 1 \le j \le N $），使得 $ S_j = l $。 - $ 1 \le Q \le 400\,000 $。 - $ 1 \le A_k \le N $（$ 1 \le k \le Q $）。 - $ 1 \le B_k \le N $（$ 1 \le k \le Q $）。 - $ A_k \ne B_k $（$ 1 \le k \le Q $）。 - 所有输入值均为整数。 ### 子任务 1. （5 分）$ N \le 1\,000 $，$ M \le 1\,000 $，$ Q \le 1\,000 $。 2. ~~（11 分）对于每个州 $ l $（$ 1 \le l \le K $），属于该州的所有城市仅可通过属于该州的道路和城市相互连通。~~ 3. （42 分）$ N \le 80\,000 $，$ M \le 80\,000 $，$ Q \le 80\,000 $。 4. （42 分）无额外约束。 由于没有明确的 Subtask2 的测试点，通过子任务 1、3、4 后会为分数自动增加 11 分。 翻译由 Qwen3-235B 完成