{"raw_statement":[{"iden":"background","content":"提交时请不要引用 `joitour.h`。\n\n请不要使用 C++14 (GCC 9) 提交。"},{"iden":"statement","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_i=0$：果汁店\n- $F_i=1$：日式煎蛋卷店\n- $F_i=2$：冰淇淋店\n\n理惠女士是 IOI 国的导游，她正在规划一个叫做 **JOI 之旅**的观光计划。JOI 之旅中计划按如下顺序前往 $3$ 种餐厅：\n\n1. 选择有果汁店的城市 $i_0\\ (0\\le i_0\\le N-1)$，并从城市 $i_0$ 开始旅行。\n2. 前往城市 $i_0$ 的果汁店。\n3. 选择有日式煎蛋卷店的城市 $i_1\\ (0\\le i_1\\le N-1)$，并从城市 $i_0$ 出发乘公交车沿最短路径前往城市 $i_1$。\n4. 前往城市 $i_1$ 的日式煎蛋卷店。\n5. 选择有冰淇淋店的城市 $i_2\\ (0\\le i_2\\le N-1)$，并从城市 $i_1$ 出发乘公交车沿最短路径前往城市 $i_2$​。\n6. 前往城市 $i_2$​ 的冰淇淋店。\n7. 在城市 $i_2$ 结束行程。\n\n为了避免游客无聊，理惠女士决定选择三个城市 $i_0,i_1,i_2$ 满足它们不会经过相同的道路两次。我们称这样的 JOI 之旅是好的。为了帮助她找到理想的旅行计划，你被要求计算好的 JOI 之旅的数量。换句话说，你需要找到满足所有如下条件的三元组 $(i_0,i_1,i_2)$ 的个数：\n\n- 城市 $i_0$ 中的餐厅是果汁店。\n- 城市 $i_1$ 中的餐厅是日式煎蛋卷店。\n- 城市 $i_2$ 中的餐厅是冰淇淋店。\n- 当我们沿最短路径从城市 $i_0$ 移动到 $i_1$ 再移动到 $i_2$ 的过程中，不会经过相同的道路两次。\n\n在 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 之旅的数量并告诉理惠女士。\n\n给定道路和餐厅信息，在每次类型改变事件发生之后计算好的 JOI 之旅的数量。\n\n### 实现细节\n\n你需要实现如下函数。\n\n- `void init(int N, std::vector<int> F, std::vector<int> U, std::vector<int> V, int Q)`\n  - 使用此函数给出道路和餐厅信息。\n  - 这个函数仅在程序开始时调用一次。\n  - 参数 `N` 是城市个数 $N$。\n  - 参数 `F` 是长为 $N$ 的数组。`F[i]` （$0\\le i\\le N-1$）表示城市 $i$ 中餐厅的类别，也就是 $F_i$。\n  - 参数 `U` 和 `V` 是长为 $N-1$ 的数组。`U[j]` 和 `V[j]`（$0\\le j\\le N-2$）是被路 $j$ 连接的两个城市 $U_j$ 和 $V_j$。\n  - 参数 `Q` 是餐厅类型改变事件的个数 $Q$。\n- `void change(int X, int Y)`\n  - 使用此函数给出餐厅类型改变事件。\n  - 这个函数被调用 $Q$ 次。\n  - 第 $(k+1)\\ (0\\le k\\le Q-1)$ 次调用中，参数 `X` 是餐厅类型改变发生的城市编号，也就是 $X_k$。\n  - 第 $(k+1)\\ (0\\le k\\le Q-1)$ 次调用中，参数 `Y` 是餐厅的新类型，也就是 $Y_k$。保证新类型与原类型不同。\n- `long long num_tours()`\n  - 这个函数在如下场景被调用，共 $Q+1$ 次。\n    - 在执行完函数 `init` 后。\n    - 在执行完函数 `change` 后。\n  - 这个函数应返回最新的好 JOI 之旅数。"},{"iden":"input","content":"**以下为下发 grader 的输入格式，你不应该从标准输入中读入任何信息。**\n\n第一行一个整数 $N$。\n\n第二行 $N$ 个整数 $F_0,\\ldots,F_{N-1}$。\n\n接下来 $N-1$ 行，每行两个整数 $U_j,V_j$。\n\n接下来一行一个整数 $Q$。\n\n接下来 $Q$ 行，每行两个整数 $X_k,Y_k$。"},{"iden":"output","content":"**以下为下发 grader 的输出格式，你不应该向标准输出中打印任何信息。**\n\n下发 grader 会在每次调用 `num_tours` 函数后输出一行一个整数，表示这个函数的返回值。"},{"iden":"note","content":"#### 样例解释 1\n\n|                函数调用                 | 返回值 |\n| :-------------------------------------: | :----: |\n| `init(3, [0, 1, 2], [0, 1], [1, 2], 0)` |        |\n|              `num_tours()`              |  $1$   |\n\n只有一个好的 JOI 之旅，表示为 $(i_0,i_1,i_2)=(0,1,2)$。下面是对于它满足是好的 JOI 之旅条件的解释。\n\n- $F_0=0$，在城市 $0$ 的餐厅是果汁店。\n- $F_1=1$，在城市 $1$ 的餐厅是日式煎蛋卷店。\n- $F_2=2$，在城市 $2$ 的餐厅是冰淇淋店。\n- 当我们沿最短路径从城市 $0$ 移动到 $1$，然后从 $1$ 移动到 $2$ 时，我们没有经过相同的道路两次。\n\n因此，第一次 `num_tours()` 函数的调用返回值为 $1$。\n\n该样例满足子任务 $1,2,3,4,6,7$ 的限制。\n\n#### 样例解释 2\n\n|                函数调用                 | 返回值 |\n| :-------------------------------------: | :----: |\n| `init(3, [0, 1, 2], [0, 1], [1, 2], 2)` |        |\n|              `num_tours()`              |  $1$   |\n|             `change(2, 0)`              |        |\n|              `num_tours()`              |  $0$   |\n|             `change(0, 2)`              |        |\n|              `num_tours()`              |  $1$   |\n\n最初有一个好的 JOI 之旅，表示为 $(i_0,i_1,i_2)=(0,1,2)$。因此，第一次 `num_tours()` 函数的调用返回值为 $1$。\n\n在第一个事件中，在城市 $2$ 的餐厅从冰淇淋店变成了果汁店。在这次变化后，冰淇淋店从 IOI 国消失了，好的 JOI 之旅也没有了。因此，第二次 `num_tours()` 函数的调用返回值为 $0$。\n\n在第二个事件中，在城市 $0$ 的餐厅从果汁店变成了冰淇淋店。在这次变化后，有一个好的 JOI 之旅，表示为 $(i_0,i_1,i_2)=(2,1,0)$。因此，第三次 `num_tours()` 函数的调用返回值为 $1$。\n\n该样例满足子任务 $1,2,4,6,7$ 的限制。\n\n#### 样例解释 3\n\n这组样例满足子任务 $1,2,5,6,7$ 的限制。\n\n### 重要提示\n\n- 你的程序可以实现其它函数供内部使用，或者使用全局变量。\n- 你的程序禁止使用标准输入输出。你的程序禁止与其他文件通过任何方式交互。然而，你的程序可以使用标准错误输出输出调试信息。\n\n### 编译和测试运行\n\n你可以在「文件 - 附加文件」中下载样例交互器来测试你的程序。附加文件中还包含一个样例程序。\n\n样例交互器是文件 `grader.cpp`。为了测试你的程序，请将 `grader.cpp`，`joitour.cpp` 和 `joitour.h` 放在同一目录下，并且执行如下命令编译程序。此外你也可以运行 `compile.sh` 来编译你的程序。\n\n```bash\ng++ -std=gnu++20 -O2 -o grader grader.cpp joitour.cpp\n```\n\n当编译成功时，会生成可执行文件 `grader`。\n\n注意测评时使用的交互器与样例交互器不同。样例交互器会以单进程的形式执行，它会从标准输入中读入数据，输出结果到标准输出。\n\n### 约束条件\n\n- $3\\le N\\le 2\\times 10^5$。\n- $0\\le F_i\\le 2\\ (0\\le i\\le N-1)$。\n- $0\\le U_j<V_j\\le N-1\\ (0\\le j\\le N-2)$。\n- 可以通过道路从一个城市前往任意其他城市。\n- $0\\le Q\\le 5\\times 10^4$。\n- $0\\le X_k\\le N-1\\ (0\\le k\\le Q-1)$。\n- $0\\le Y_k\\le 2\\ (0\\le k\\le Q-1)$。\n- 对于每次调用函数 `change`，新类型不同于原类型。\n\n### 子任务\n\n- （6 分）$N\\le 400$，$Q\\le 100$。\n- （8 分）$N\\le 4\\,000$，$Q\\le 1\\,000$。\n- （6 分）$Q=0$。\n- （16 分）$U_j=j,V_j=j+1\\ (0\\le j\\le N-2)$。\n- （16 分）$U_j=\\lfloor\\frac{j}{2}\\rfloor,V_j=j+1\\ (0\\le j\\le N-2)$。\n- （34 分）$N\\le 10^5$，$Q\\le 2.5\\times 10^4$。\n- （14 分）无额外约束。"}],"translated_statement":null,"sample_group":[["3\n0 1 2\n0 1\n1 2\n0","1"],["3\n0 1 2\n0 1\n1 2\n2\n2 0\n0 2","1\n0\n1"],["7\n1 0 2 2 0 1 0\n0 1\n0 2\n1 3\n1 4\n2 5\n2 6\n7\n0 0\n1 1\n2 0\n3 0\n4 2\n5 2\n6 2","3\n0\n4\n4\n0\n4\n5\n5"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}