CF1172E.Nauuo and ODT

Nauuo is a girl who loves traveling.

One day she went to a tree, Old Driver Tree, literally, a tree with an old driver on it.

The tree is a connected graph consisting of $n$ nodes and $n-1$ edges. Each node has a color, and Nauuo will visit the ODT through a simple path on the tree in the old driver's car.

Nauuo wants to visit see more different colors in her journey, but she doesn't know which simple path she will be traveling on. So, she wants to calculate the sum of the numbers of different colors on all different paths. Can you help her?

What's more, the ODT is being redecorated, so there will be $m$ modifications, each modification will change a single node's color. Nauuo wants to know the answer after each modification too.

Note that in this problem, we consider the simple path from $u$ to $v$ and the simple path from $v$ to $u$ as two different simple paths if and only if $u\ne v$.

Nauuo 是一位热爱旅行的女孩。

一天，她来到一棵树——老司机树（Old Driver Tree），字面意思就是一棵上面坐着一位老司机的树。

这棵树是一个由 $n$ 个节点和 $n-1$ 条边构成的连通图。每个节点都有一种颜色，Nauuo 将乘坐老司机的汽车，沿着树上的一条简单路径游览这棵老司机树。

Nauuo 希望在旅途中看到尽可能多的不同颜色，但她并不知道最终会走哪一条简单路径。因此，她希望计算所有不同简单路径上不同颜色数量的总和。你能帮她吗？

此外，这棵老司机树正在重新装修，因此将进行 $m$ 次修改，每次修改会改变单个节点的颜色。Nauuo 还希望知道每次修改后该总和的值。

注意：在本题中，我们认为从 $u$ 到 $v$ 的简单路径与从 $v$ 到 $u$ 的简单路径是两条不同的简单路径，当且仅当 $u \ne v$。

The first line contains two integers $n$ and $m$ ($2\le n\le 4\cdot 10^5$, $1\le m\le 4\cdot 10^5$) — the number of nodes and the number of modifications.

The second line contains $n$ integers $c_1,c_2,\ldots,c_n$ ($1\le c_i\le n$), where $c_i$ is the initial color of node $i$.

Each of the next $n-1$ lines contains two integers $u$ and $v$ ($1\le u,v\le n$), denoting there is an edge between $u$ and $v$. It is guaranteed that the given edges form a tree.

Each of the next $m$ lines contains two integers $u$ and $x$ ($1\le u,x\le n$), which means a modification that changes the color of node $u$ into $x$.

第一行包含两个整数 $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$ 的操作。

The output contains $m+1$ integers — the first integer is the answer at the beginning, the rest integers are the answers after every modification in the given order.

输出包含 $m+1$ 个整数——第一个整数为初始状态下的答案，其余整数为按给定顺序进行每次修改后的答案。

Example 1

The number of colors on each simple path at the beginning:

示例 1

初始时每条简单路径上的颜色种数：