P9340 [JOIST 2023] 旅行 / Tourism

JOI 王国是一个由 $N$ 个岛屿组成的岛国，编号从 $1$ 到 $N$。这些岛屿通过 $N - 1$ 座桥相连，编号从 $1$ 到 $N - 1$。桥 $i\ (1 \leq i \leq N - 1)$ 双向连接岛屿 $A_i$ 和岛屿 $B_i$。可以通过若干座桥从任意一个岛屿到达另一个岛屿。在 JOI 王国，有 $M$ 个观光景点，编号从 $1$ 到 $M$。观光景点 $j\ (1 \leq j \leq M)$ 位于岛屿 $C_j$。有 $Q$ 位旅行者，他们计划参观 JOI 王国的观光景点。旅行者编号从 $1$ 到 $Q$。每位旅行者按以下方式旅行。 1. 旅行者选择一个岛屿 $x\ (1 \leq x \leq N)$。乘坐飞机，旅行者到达岛屿 $x$。 2. 旅行者进行若干次以下动作。动作的顺序和种类是任意的。 - 旅行者选择当前岛屿上的一个观光景点，并参观。 - 旅行者通过桥梁移动到另一个岛屿。 3. 乘坐飞机，旅行者离开 JOI 王国。旅行者 $k\ (1 \leq k \leq Q)$ 想要参观所有的观光景点 $L_k, L_k+1, \ldots, R_k$。然而，由于预算有限，旅行者 $k$ 希望最小化至少访问一次的岛屿数量。

从标准输入读取以下数据。 > $N\ M\ Q$ > > $A_1\ B_1$ > > $A_2\ B_2$ > > $\vdots$ > > $A_{N-1}\ B_{N-1}$ > > $C_1\ C_2\ \cdots\ C_M$ > > $L_1\ R_1$ > > $L_2\ R_2$ > > $\vdots$ > > $L_Q\ R_Q$

向标准输出写入 $Q$ 行。输出的第 $k$ 行 $(1 \leq k \leq Q)$ 应包含旅行者 $k$ 至少访问一次的岛屿的最小可能数量。

**【样例解释 #1】** 旅行者 1 按以下方式旅行，并参观所有的观光景点 1, 2, 3。 1. 旅行者 1 到达岛屿 2。 2. 旅行者 1 参观岛屿 2 上的观光景点 1。 3. 旅行者 1 通过桥梁 1 从岛屿 2 移动到岛屿 1。 4. 旅行者 1 通过桥梁 2 从岛屿 1 移动到岛屿 3。 5. 旅行者 1 参观岛屿 3 上的观光景点 2。 6. 旅行者 1 通过桥梁 5 从岛屿 3 移动到岛屿 6。 7. 旅行者 1 参观岛屿 6 上的观光景点 3。 8. 旅行者 1 从岛屿 6 出发，离开 JOI 王国。 岛屿 1, 2, 3, 6 是旅行者 1 至少访问一次的四个岛屿。如果旅行者 1 至少访问一次的岛屿数量小于或等于 3，则不可能参观所有的观光景点 1, 2, 3。因此，第一行输出 4。旅行者 2 按以下方式旅行，并参观所有的观光景点 4, 5, 6。 1. 旅行者 2 到达岛屿 3。 2. 旅行者 2 通过桥梁 6 从岛屿 3 移动到岛屿 7。 3. 旅行者 2 参观岛屿 7 上的观光景点 6。 4. 旅行者 2 通过桥梁 6 从岛屿 7 移动到岛屿 3。 5. 旅行者 2 通过桥梁 2 从岛屿 3 移动到岛屿 1。 6. 旅行者 2 通过桥梁 1 从岛屿 1 移动到岛屿 2。 7. 旅行者 2 通过桥梁 3 从岛屿 2 移动到岛屿 4。 8. 旅行者 2 参观岛屿 4 上的观光景点 4。 9. 旅行者 2 通过桥梁 3 从岛屿 4 移动到岛屿 2。 10. 旅行者 2 通过桥梁 4 从岛屿 2 移动到岛屿 5。 11. 旅行者 2 参观岛屿 5 上的观光景点 5。 12. 旅行者 2 从岛屿 5 出发，离开 JOI 王国。 岛屿 1, 2, 3, 4, 5, 7 是旅行者 2 至少访问一次的六个岛屿。如果旅行者 2 至少访问一次的岛屿数量小于或等于 5，则不可能参观所有的观光景点 4, 5, 6。因此，第二行输出 6。此样例输入满足子任务 1, 2, 4, 5, 6 的约束。 岛屿 1, 2, 3, 4, 5, 7 是旅行者 2 至少访问一次的六个岛屿。如果旅行者 2 至少访问一次的岛屿数量小于或等于 5，则不可能参观所有的观光景点 4, 5, 6。因此，第二行输出 6。 此样例输入满足子任务 1, 2, 4, 5, 6 的约束。 **【样例解释 #2】** 此样例输入满足子任务 1, 2, 3, 6 的约束。 **【样例解释 #3】** 此样例输入满足子任务 1, 2, 6 的约束。 **【数据范围】** - $1 \leq N \leq 100 000$。 - $1 \leq M \leq 100 000$。 - $1 \leq Q \leq 100 000$。 - $1 \leq A_i \leq N\ (1 \leq i \leq N - 1)$。 - $1 \leq B_i \leq N\ (1 \leq i \leq N - 1)$。 - 可以通过若干座桥从任意一个岛屿到达另一个岛屿。 - $1 \leq C_j \leq N\ (1 \leq j \leq M)$。 - $1 \leq L_k \leq R_k \leq M\ (1 \leq k \leq Q)$。 - 给定的值都是整数。 **【子任务】** 1. (5 分) $N \leq 300, M \leq 300, Q \leq 300$。 2. (5 分) $N \leq 2 000, M \leq 2 000, Q \leq 2 000$。 3. (7 分) $A_i = i, B_i = i + 1\ (1 \leq i \leq N - 1)$。 4. (18 分) $L_1 = 1, R_{k} + 1 = L_{k+1}\ (1 \leq k \leq Q - 1), R_Q = M$。 5. (24 分) $A_i = \lfloor\frac{i+1}2\rfloor, B_i = i + 1\ (1 \leq i \leq N-1)$。这里，$\lfloor x\rfloor$ 是不超过 x 的最大整数。 6. (41 分) 无额外约束。 题面翻译由 ChatGPT-4o 提供。