题目背景

提交时请不要引用 joitour.h。

请不要使用 C++14 (GCC 9) 提交。

题目描述

在 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 之旅数。

输入格式

以下为下发 grader 的输入格式，你不应该从标准输入中读入任何信息。

第一行一个整数 $N$。

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

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

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

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

输出格式

以下为下发 grader 的输出格式，你不应该向标准输出中打印任何信息。

下发 grader 会在每次调用 num_tours 函数后输出一行一个整数，表示这个函数的返回值。

3
0 1 2
0 1
1 2
0

1

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

1
0
1

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

函数调用	返回值
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 来编译你的程序。

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 分）无额外约束。