5s,512MB

给一颗大小为$n$ 的树，每个点有一个颜色$c_i$。定义$col(u,v)$为点u到点v路径上的颜色数。

有 $m$ 次修改，每次修改一个点的点权，在所有修改前和每次修改后，你都需要输出$\sum_{i=1}^n\sum_{j=1}^ndis(i,j)$。注意，你仍然需要输出初始的答案。

输入格式

第一行$n,m$，第二行$c_1,c_2,\cdots,c_n$

接下来$n-1$行输入整棵树得边，接下来$m$行每行输入两个数$x,c$表示将$c_x$设为$c$。

输出格式

输出$m+1$行表示一开始和每次修改后的答案（修改是永久生效的）。

样例

输入

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

输出

47
51
49
45

数据范围

$n,m\leq 500000$；题目中出现的所有颜色均$\in[1,n]$。

sub1(20pts):$n,m\leq 2000$

sub2(10pts):$m=0$

sub3(10pts):$\forall i\in[1,n-1]$存在$i$到$i+1$的边

sub4(10pts):$\forall i\in[1,n-1]$存在$i$到$n$的边

sub5(5pts):所有颜色均$\leq 2$

sub6(45pts):无特殊限制