题目描述

给你一棵 $n$ 个节点的树，每个点有个颜色，有 $m$ 次修改，每次修改需要输出树上所有有向简单路径的颜色数的和。

输入格式

第一行，输入两个整数 $n$ 和 $m$。

第二行，输入 $n$ 个整数 $c_1,c_2,\ldots,c_n$（$1\leq c_i\leq n$）。其中 $c_i$ 为 $i$ 节点的初始颜色。

接下来 $n-1$ 行每行包括两个整数 $u,v$（$1\leq u,v\leq n$），这表示 $u$ 与 $v$ 之间有一条边。

接着 $m$ 行每行包括两个整数 $u,x$（$1\leq u,x\leq n$）表示将节点 $u$ 的颜色修改为 $x$。

输出格式

输出 $m+1$ 行，每行一个整数，为初始这个树上所有路径颜色数的和，以及每次修改后的这个值。

样例 #1

样例输入 #1

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

样例输出 #1

47
51
49
45

样例 #2

样例输入 #2

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

样例输出 #2

36
46

提示

Idea：nzhtl1477，Solution：nzhtl1477，Code：nzhtl1477，Data：nzhtl1477

对于 $100\%$ 的数据，满足 $2\leq n\leq 4\times 10^5$，$1\leq m\leq 4\times 10^5$。