P5526 [Ynoi2012] Panic SCOI2016

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.

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 $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.

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