Problem Description

You are given a tree with $n$ nodes. Each node has a color. There are $m$ modifications. For each modification, you need to output the sum, over all directed simple paths in the tree, of the number of distinct colors on the path.

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,v$ ($1\leq u,v\leq n$), indicating that there is an edge between $u$ and $v$.

Then follow $m$ lines, each containing two integers $u,x$ ($1\leq u,x\leq n$), meaning to change the color of node $u$ to $x$.

Output Format

Output $m+1$ lines, each containing one integer: the sum of the number of colors over all paths in the tree for the initial tree, and the value after each modification.

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

47
51
49
45

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

36
46

Hint

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

For $100\%$ of the testdata, $2\leq n\leq 4\times 10^5$ and $1\leq m\leq 4\times 10^5$.

Translated by ChatGPT 5