[JOIST 2024] JOI 之旅 / JOI Tour

Luogu
IDLGP10437
Time3000ms
Memory1024MB
DifficultyP6
线段树2024交互题O2优化树链剖分动态 DPJOISC/JOIST（日本）
在 IOI 国，有 $N$ 个城市，编号为 $0$ 到 $N-1$，有 $N-1$ 条道路，编号为 $0$ 到 $N-2$。路 $j\ (0\le j\le N-2)$ 双向连接城市 $U_j$ 和城市 $V_j$。你可以通过道路从一个城市到达另一其他城市。 IOI 国的每个城市都有一家餐厅。在城市 $i\ (0\le i\le N-1)$ 的餐厅类型用 $F_i$ 表示，具体来说： - $F_i=0$：果汁店 - $F_i=1$：日式煎蛋卷店 - $F_i=2$：冰淇淋店 理惠女士是 IOI 国的导游，她正在规划一个叫做 **JOI 之旅**的观光计划。JOI 之旅中计划按如下顺序前往 $3$ 种餐厅： 1. 选择有果汁店的城市 $i_0\ (0\le i_0\le N-1)$，并从城市 $i_0$ 开始旅行。 2. 前往城市 $i_0$ 的果汁店。 3. 选择有日式煎蛋卷店的城市 $i_1\ (0\le i_1\le N-1)$，并从城市 $i_0$ 出发乘公交车沿最短路径前往城市 $i_1$。 4. 前往城市 $i_1$ 的日式煎蛋卷店。 5. 选择有冰淇淋店的城市 $i_2\ (0\le i_2\le N-1)$，并从城市 $i_1$ 出发乘公交车沿最短路径前往城市 $i_2$​。 6. 前往城市 $i_2$​ 的冰淇淋店。 7. 在城市 $i_2$ 结束行程。 为了避免游客无聊，理惠女士决定选择三个城市 $i_0,i_1,i_2$ 满足它们不会经过相同的道路两次。我们称这样的 JOI 之旅是好的。为了帮助她找到理想的旅行计划，你被要求计算好的 JOI 之旅的数量。换句话说，你需要找到满足所有如下条件的三元组 $(i_0,i_1,i_2)$ 的个数： - 城市 $i_0$ 中的餐厅是果汁店。 - 城市 $i_1$ 中的餐厅是日式煎蛋卷店。 - 城市 $i_2$ 中的餐厅是冰淇淋店。 - 当我们沿最短路径从城市 $i_0$ 移动到 $i_1$ 再移动到 $i_2$ 的过程中，不会经过相同的道路两次。 在 IOI 国，会有 $Q$ 次餐厅类型改变的事件。当第 $(k+1)\ (0\le k\le Q-1)$ 个事件发生时，会给出两个整数 $X_k$ 和 $Y_k$，满足 $0\le X_k\le N-1$ 且 $0\le Y_k\le 2$。然后，在城市 $X_k$ 的餐厅类型会变为 $Y_k$。也就是说，当 $Y_k=0,1,2$ 时，餐厅类型会分别变为果汁店，日式煎蛋卷店和冰淇淋店。在每个事件过后，你应该立即计算最新的好的 JOI 之旅的数量并告诉理惠女士。 给定道路和餐厅信息，在每次类型改变事件发生之后计算好的 JOI 之旅的数量。 ### 实现细节 你需要实现如下函数。 - `void init(int N, std::vector<int> F, std::vector<int> U, std::vector<int> V, int Q)` - 使用此函数给出道路和餐厅信息。 - 这个函数仅在程序开始时调用一次。 - 参数 `N` 是城市个数 $N$。 - 参数 `F` 是长为 $N$ 的数组。`F[i]` （$0\le i\le N-1$）表示城市 $i$ 中餐厅的类别，也就是 $F_i$。 - 参数 `U` 和 `V` 是长为 $N-1$ 的数组。`U[j]` 和 `V[j]`（$0\le j\le N-2$）是被路 $j$ 连接的两个城市 $U_j$ 和 $V_j$。 - 参数 `Q` 是餐厅类型改变事件的个数 $Q$。 - `void change(int X, int Y)` - 使用此函数给出餐厅类型改变事件。 - 这个函数被调用 $Q$ 次。 - 第 $(k+1)\ (0\le k\le Q-1)$ 次调用中，参数 `X` 是餐厅类型改变发生的城市编号，也就是 $X_k$。 - 第 $(k+1)\ (0\le k\le Q-1)$ 次调用中，参数 `Y` 是餐厅的新类型，也就是 $Y_k$。保证新类型与原类型不同。 - `long long num_tours()` - 这个函数在如下场景被调用，共 $Q+1$ 次。 - 在执行完函数 `init` 后。 - 在执行完函数 `change` 后。 - 这个函数应返回最新的好 JOI 之旅数。 ## Input **以下为下发 grader 的输入格式，你不应该从标准输入中读入任何信息。** 第一行一个整数 $N$。 第二行 $N$ 个整数 $F_0,\ldots,F_{N-1}$。 接下来 $N-1$ 行，每行两个整数 $U_j,V_j$。 接下来一行一个整数 $Q$。 接下来 $Q$ 行，每行两个整数 $X_k,Y_k$。 ## Output **以下为下发 grader 的输出格式，你不应该向标准输出中打印任何信息。** 下发 grader 会在每次调用 `num_tours` 函数后输出一行一个整数，表示这个函数的返回值。 [samples] ## Background 提交时请不要引用 `joitour.h`。 请不要使用 C++14 (GCC 9) 提交。 ## Note #### 样例解释 1 | 函数调用 | 返回值 | | :-------------------------------------: | :----: | | `init(3, [0, 1, 2], [0, 1], [1, 2], 0)` | | | `num_tours()` | $1$ | 只有一个好的 JOI 之旅，表示为 $(i_0,i_1,i_2)=(0,1,2)$。下面是对于它满足是好的 JOI 之旅条件的解释。 - $F_0=0$，在城市 $0$ 的餐厅是果汁店。 - $F_1=1$，在城市 $1$ 的餐厅是日式煎蛋卷店。 - $F_2=2$，在城市 $2$ 的餐厅是冰淇淋店。 - 当我们沿最短路径从城市 $0$ 移动到 $1$，然后从 $1$ 移动到 $2$ 时，我们没有经过相同的道路两次。 因此，第一次 `num_tours()` 函数的调用返回值为 $1$。 该样例满足子任务 $1,2,3,4,6,7$ 的限制。 #### 样例解释 2 | 函数调用 | 返回值 | | :-------------------------------------: | :----: | | `init(3, [0, 1, 2], [0, 1], [1, 2], 2)` | | | `num_tours()` | $1$ | | `change(2, 0)` | | | `num_tours()` | $0$ | | `change(0, 2)` | | | `num_tours()` | $1$ | 最初有一个好的 JOI 之旅，表示为 $(i_0,i_1,i_2)=(0,1,2)$。因此，第一次 `num_tours()` 函数的调用返回值为 $1$。 在第一个事件中，在城市 $2$ 的餐厅从冰淇淋店变成了果汁店。在这次变化后，冰淇淋店从 IOI 国消失了，好的 JOI 之旅也没有了。因此，第二次 `num_tours()` 函数的调用返回值为 $0$。 在第二个事件中，在城市 $0$ 的餐厅从果汁店变成了冰淇淋店。在这次变化后，有一个好的 JOI 之旅，表示为 $(i_0,i_1,i_2)=(2,1,0)$。因此，第三次 `num_tours()` 函数的调用返回值为 $1$。 该样例满足子任务 $1,2,4,6,7$ 的限制。 #### 样例解释 3 这组样例满足子任务 $1,2,5,6,7$ 的限制。 ### 重要提示 - 你的程序可以实现其它函数供内部使用，或者使用全局变量。 - 你的程序禁止使用标准输入输出。你的程序禁止与其他文件通过任何方式交互。然而，你的程序可以使用标准错误输出输出调试信息。 ### 编译和测试运行 你可以在「文件 - 附加文件」中下载样例交互器来测试你的程序。附加文件中还包含一个样例程序。 样例交互器是文件 `grader.cpp`。为了测试你的程序，请将 `grader.cpp`，`joitour.cpp` 和 `joitour.h` 放在同一目录下，并且执行如下命令编译程序。此外你也可以运行 `compile.sh` 来编译你的程序。 ```bash g++ -std=gnu++20 -O2 -o grader grader.cpp joitour.cpp ``` 当编译成功时，会生成可执行文件 `grader`。 注意测评时使用的交互器与样例交互器不同。样例交互器会以单进程的形式执行，它会从标准输入中读入数据，输出结果到标准输出。 ### 约束条件 - $3\le N\le 2\times 10^5$。 - $0\le F_i\le 2\ (0\le i\le N-1)$。 - $0\le U_j<V_j\le N-1\ (0\le j\le N-2)$。 - 可以通过道路从一个城市前往任意其他城市。 - $0\le Q\le 5\times 10^4$。 - $0\le X_k\le N-1\ (0\le k\le Q-1)$。 - $0\le Y_k\le 2\ (0\le k\le Q-1)$。 - 对于每次调用函数 `change`，新类型不同于原类型。 ### 子任务 - （6 分）$N\le 400$，$Q\le 100$。 - （8 分）$N\le 4\,000$，$Q\le 1\,000$。 - （6 分）$Q=0$。 - （16 分）$U_j=j,V_j=j+1\ (0\le j\le N-2)$。 - （16 分）$U_j=\lfloor\frac{j}{2}\rfloor,V_j=j+1\ (0\le j\le N-2)$。 - （34 分）$N\le 10^5$，$Q\le 2.5\times 10^4$。 - （14 分）无额外约束。
Samples
Input #1
3
0 1 2
0 1
1 2
0
Output #1
1
Input #2
3
0 1 2
0 1
1 2
2
2 0
0 2
Output #2
1
0
1
Input #3
7
1 0 2 2 0 1 0
0 1
0 2
1 3
1 4
2 5
2 6
7
0 0
1 1
2 0
3 0
4 2
5 2
6 2
Output #3
3
0
4
4
0
4
5
5
API Response (JSON) 
{
  "problem": {
    "name": "[JOIST 2024] JOI 之旅 / JOI Tour",
    "description": {
      "content": "在 IOI 国，有 $N$ 个城市，编号为 $0$ 到 $N-1$，有 $N-1$ 条道路，编号为 $0$ 到 $N-2$。路 $j\\ (0\\le j\\le N-2)$ 双向连接城市 $U_j$ 和城市 $V_j$。你可以通过道路从一个城市到达另一其他城市。 IOI 国的每个城市都有一家餐厅。在城市 $i\\ (0\\le i\\le N-1)$ 的餐厅类型用 $F_i$ 表示，具体来说： - $F",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10437"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "在 IOI 国，有 $N$ 个城市，编号为 $0$ 到 $N-1$，有 $N-1$ 条道路，编号为 $0$ 到 $N-2$。路 $j\\ (0\\le j\\le N-2)$ 双向连接城市 $U_j$ 和城市 $V_j$。你可以通过道路从一个城市到达另一其他城市。\n\nIOI 国的每个城市都有一家餐厅。在城市 $i\\ (0\\le i\\le N-1)$ 的餐厅类型用 $F_i$ 表示，具体来说：\n\n- $F...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments
© Rotriw 2026. 若您有相关疑问请联系 issue@rmj.ac