CF1172E Nauuo and ODT

Nauuo 是一个喜欢旅行的女孩。 有一天，她来到了一个叫做 Old Driver Tree（简称 ODT）的树上，字面意思是一棵树上有一位老司机。 这棵树是一个包含 $n$ 个节点和 $n-1$ 条边的连通图。每个节点都有一个颜色，Nauuo 将乘坐老司机的车在树上沿一条简单路径游览 ODT。 Nauuo 希望在旅途中看到更多不同的颜色，但她并不知道自己会走哪一条简单路径。因此，她想要计算所有不同路径上不同颜色的数量之和。你能帮帮她吗？ 此外，ODT 正在重新装修，因此会有 $m$ 次修改，每次修改会改变某个节点的颜色。Nauuo 也想知道每次修改后的答案。 注意，在本题中，我们认为从 $u$ 到 $v$ 的简单路径和从 $v$ 到 $u$ 的简单路径是两条不同的简单路径，当且仅当 $u\ne v$。

第一行包含两个整数 $n$ 和 $m$（$2\le n\le 4\cdot 10^5$，$1\le m\le 4\cdot 10^5$），分别表示节点数和修改次数。 第二行包含 $n$ 个整数 $c_1,c_2,\ldots,c_n$（$1\le c_i\le n$），其中 $c_i$ 表示节点 $i$ 的初始颜色。 接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1\le u,v\le n$），表示存在一条连接 $u$ 和 $v$ 的边。保证给定的边构成一棵树。 接下来的 $m$ 行，每行包含两个整数 $u$ 和 $x$（$1\le u,x\le n$），表示一次修改操作，将节点 $u$ 的颜色改为 $x$。

输出共 $m+1$ 个整数——第一个整数为初始时的答案，之后每个整数为每次修改后的答案，顺序与输入的修改顺序一致。

示例 1  初始时每条简单路径上的颜色数量如下：  由 ChatGPT 4.1 翻译