4294. [TIOJ - 114學年度複試] Output Only

【题目背景】

pooh 很想买 Ina 的五周年纪念商品，因此他决定要去打工。 他的打工是要帮一棵神奇的树上油漆，不过这个打工很酷，不在乎你工作的过程，只在乎最后的结果。这种只看结果 (Output Only) 的工作 pooh 当然会想办法偷懒啦，所以他打算事先规划好该怎么刷油漆再开始工作。

【题目描述】

有一棵神奇的 $N$ 个节点的定根树，根在 1。因为现在正在举办活动，这棵树上每个节点都变成 $k$ 种颜色 ($0, 1, \dots, k-1$) 其中一种，编号 $i$ 的节点颜色为 $c_i$。

pooh 的老板希望他帮忙恢复这棵树，透过涂油漆将这棵树 每个节点都变成颜色 0。每次涂油漆 pooh 都可以选择某个节点 $u$ 涂上他选的某种色号 $p$ 的油漆。油漆会逆着重力扩散，将 $u$ 的子树（包含 $u$）内 所有节点的颜色改变。对于一个 $u$ 的子树内节点 $v$，他的颜色会从 $c_v$ 变成 $(c_v + p) \pmod k$。

随着活动的进行，树上每个节点的颜色都有可能改变，总共发生了 $Q$ 次树上的节点颜色改变。第 $i$ 次是节点 $w_i$ 的颜色变成 $x_i$。在每次树上节点颜色改变后，pooh 都想问你他最少需要涂几次油漆才可以完成任务。

【输入格式】

第一行包含三个正整数 $N, k, Q$，代表该树有几个节点，节点有几种颜色与会发生几次颜色改变。
第二行包含 $N$ 个整数 $c_1, c_2, \dots, c_N$，代表每个节点的初始颜色。
接下来 $N-1$ 行，每行包含两个正整数 $u_i, v_i$，代表该树的边 $(u_i, v_i)$。
再接下来 $Q$ 行，每行有两个正整数 $w_i, x_i$，代表节点 $w_i$ 的颜色变成 $x_i$。

【输出格式】

输出 $Q$ 行，每行有一个正整数，第 $i$ 行代表经过前 $i$ 笔颜色修改后，pooh 最少需要刷几次油漆才可以达成任务。

【样例输入】

5 4 4
1 0 1 2 3
1 2
1 3
3 4
3 5
2 1
1 0
3 2
1 2

【样例输出】

3
4
3
3

【样例说明】

对于样例测资 1，经过第一次修改后的颜色 $c = (1, 1, 1, 2, 3)$，pooh 最少需要涂三次油漆才可以将整棵树变成颜色 0，其中一种操作方法如下：在节点 4 涂色号 3 的颜料，接着在节点 1 涂色号 3 的颜料，最后在节点 5 涂色号 2 的颜料。

【数据规模与约定】

• $1 \le N, k, Q \le 2 \times 10^5$
• $0 \le c_i \le k-1$
• $1 \le u_i, v_i \le N$
• $1 \le w_i \le N$
• $0 \le x_i \le k-1$
• 大洋里（仅提供子任务 $4$ 和子任务 $5$ 各一个）
  

【来源】

114 学年度台湾省建国中学信息学科能力竞赛：复试