题目描述

题目译自 JOISC 2024 Day3 T2「JOI ツアー / JOI Tour」

在 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$：冰淇淋店

理惠女士正在规划一个叫做 JOI 之旅的观光计划。JOI 之旅按如下顺序前往 3 种餐厅：

选择有果汁店的城市 $i_0$ $(0 \le i_0 \le N-1)$，并从城市 $i_0$ 开始旅行。

前往城市 $i_0$ 的果汁店。

选择有日式煎蛋卷店的城市 $i_1$ $(0 \le i_1 \le N-1)$，并从城市 $i_0$ 出发乘公交车沿最短路径前往城市 $i_1$。

前往城市 $i_1$ 的日式煎蛋卷店。

选择有冰淇淋店的城市 $i_2$ $(0 \le i_2 \le N-1)$，并从城市 $i_1$ 出发乘公交车沿最短路径前往城市 $i_2$。

前往城市 $i_2$ 的冰淇淋店。

在城市 $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 之旅的数量。

实现细节

需要在程序开头引入库 joitour.h。

需要实现如下函数：

void init(int N, std::vector F, std::vector U, std::vector 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 之旅数。

重要提示

程序可以实现其它函数供内部使用，或者使用全局变量。

程序禁止使用标准输入输出。程序禁止与其他文件通过任何方式交互。但程序可以使用标准错误输出输出调试信息。

编译和测试运行

你可以在「文件 - 附加文件」中下载样例交互器来测试你的程序。附加文件中还包含一个样例程序。

样例交互器是文件 grader.cpp。为了测试你的程序，请将 grader.cpp、joitour.cpp 和 joitour.h 放在同一目录下，并且执行如下命令编译程序。此外你也可以运行 compile.sh 来编译你的程序。

g++ -std=gnu++20 -O2 -o grader grader.cpp joitour.cpp

当编译成功时，会生成可执行文件 grader。

注意测评时使用的交互器与样例交互器不同。样例交互器会以单进程的形式执行，它会从标准输入中读入数据，输出结果到标准输出。

样例交互器输入格式

第一行一个整数 $N$。

第二行 $N$ 个整数 $F_0, F_1, \ldots, F_{N-1}$。

接下来 $N-1$ 行，每行两个整数 $U_j, V_j$。

接下来一行一个整数 $Q$。

接下来 $Q$ 行，每行两个整数 $X_k, Y_k$。

样例交互器输出

样例交互器会在每次调用 num_tours 函数后输出一行一个整数，表示这个函数的返回值。

样例1：

3
0 1 2
0 1
1 2
0

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：

3
0 1 2
0 1
1 2
2
2 0
0 2

1
0
1

函数调用	返回值
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：

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

3
0
4
4
0
4
5
5

这组样例满足子任务 1, 2, 5, 6, 7 的限制。

数据规模与提示

$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，新类型不同于原类型

$子任务$	$附加限制$	$分值$
$1$	$N \le 400, Q \le 100$	$6$
$2$	$N \le 4000, Q \le 1000$	$8$
$3$	$Q = 0$	$6$
$4$	$U_j = j, V_j = j+1$ $(0 \le j \le N-2)$	$16$
$5$	$U_j = \lfloor \frac{j}{2} \rfloor, V_j = j+1$ $(0 \le j \le N-2)$
$6$	$N \le 10^5, Q \le 2.5 \times 10^4$	$34$
$7$	无附加限制	$14$