← 返回题目列表

Codeforces · 1172/E

E. Nauuo 和 ODT

中文机器翻译题面 查看原题

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

每个简单路径开头的颜色数量: