Nauuo是一个热爱旅行的女孩。
有一天,她去了一棵树,老司机树,字面意思是一棵树上有一个老司机。
树是由 $$$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
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
6 1 1 1 1 1 1 1 1 2 2 3 3 4 4 5 5 6 1 2
输出 #2
36 46
注意
示例 1
每个简单路径开头的颜色数量: