Problem Description

You are given a tree with $n$ nodes, each having a color. There are $m$ modifications, each requiring the sum of the number of distinct colors in all directed simple paths on the tree to be output.

Input Format

The first line contains two integers $n$ and $m$.

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

The next $n-1$ lines each contain two integers $u$ and $v$ ($1 \leq u, v \leq n$), indicating an edge between node $u$ and node $v$.

The following $m$ lines each contain two integers $u$ and $x$ ($1 \leq u, x \leq n$), representing a modification to change the color of node $u$ to $x$.

Output Format

Output $m+1$ lines, each containing an integer, which is the sum of the number of distinct colors in all paths on the tree initially and after each modification.

Sample Input and Output

Input Sample #1

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

Output Sample #1

47
51
49
45

Input Sample #2

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

Output Sample #2

36
46

Notes

For $100\%$ of the data, it is guaranteed that $2 \leq n \leq 4 \times 10^5$ and $1 \leq m \leq 4 \times 10^5$.

Idea: nzhtl1477, Solution: nzhtl1477, Code: nzhtl1477, Data: nzhtl1477

见题面 Input 部分

见题面 Output 部分