[JOIST 2023] 旅行 / Tourism

Luogu

IDLGP9340

Time4000ms

Memory1024MB

DifficultyP6

2023O2优化JOISC/JOIST（日本）

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$ 希望最小化至少访问一次的岛屿数量。 ## Input 从标准输入读取以下数据。 > $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$ ## Output 向标准输出写入 $Q$ 行。输出的第 $k$ 行 $(1 \leq k \leq Q)$ 应包含旅行者 $k$ 至少访问一次的岛屿的最小可能数量。 [samples] ## Note **【样例解释 #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 提供。

Samples

Input #1

7 6 2
1 2
1 3
2 4
2 5
3 6
3 7
2 3 6 4 5 7
1 3
4 6

Output #1

4
6

Input #2

8 8 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 6 4 3 5 2 4 7
3 5
4 6
6 8
1 4
2 3
6 8
5 5
2 8
1 2

Output #2

Input #3

10 7 9
6 5
3 6
9 3
8 3
7 8
7 1
2 5
7 10
8 4
9 4 10 1 10 7 6
4 4
1 3
1 3
6 7
3 6
3 3
1 5
2 5
1 2

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[JOIST 2023] 旅行 / Tourism",
    "description": {
      "content": "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 \\l",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9340"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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 \\l...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments