Tree Path Color Sum

You are given a tree with n nodes, where each node has an associated color. You are also given m modification operations. Each modification updates the color of a node. After each modification, you need to compute and output the sum of the numbers of distinct colors on every directed simple path in the tree.

A directed simple path is defined as an ordered sequence of nodes (without repeating nodes) that are connected by edges. Note that for any two nodes u and v (possibly u = v), there is a unique simple path between them in a tree, which is considered in one direction.

Input Format:

• The first line contains two integers n and m — the number of nodes and the number of modifications.
• The second line contains n integers, where the i-th integer denotes the initial color of the i-th node.
• Each of the next n-1 lines contains two integers u and v representing an edge connecting nodes u and v (nodes are 1-indexed).
• Each of the next m lines contains two integers u and c indicating that the color of node u is updated to c.

Output Format:

• For each modification, output a single line containing one integer — the sum over all directed simple paths in the tree of the number of distinct colors on that path.

inputFormat

The input begins with two space-separated integers n and m. The next line contains n integers representing the initial colors of the nodes. The following n - 1 lines each contain two integers u and v representing an edge between nodes u and v. The final m lines each contain two integers u and c representing a modification operation (update the color of node u to c).

outputFormat

After each modification, output the sum over all directed simple paths in the tree of the number of distinct colors on that path, each on its own line.

sample

3 2
1 2 3
1 2
2 3
1 3
2 1

15
15