Counting Valid Paths on a Colored Tree

In the magical Year of the Dragon, a mystical tree known as the "Deep Blue Tree" has its nodes painted in vibrant colors. The tree consists of n nodes, where the color of the i-th node is denoted by \(a_i\). In the next q days, our protagonist FanFan, who is known for his fickle tastes, decides to change his favorite colors every day. On the i-th day he favors two distinct colors \(x_i\) and \(y_i\).

On day \(i\), FanFan chooses an ordered pair of nodes \((u, v)\) and traverses the unique simple path from \(u\) to \(v\) on the tree. The condition is that every node along that path (including \(u\) and \(v\)) must have a color that is either \(x_i\) or \(y_i\). Note that \(u\) and \(v\) can be the same node. After traveling, he is allowed one special celebration.

Your task is to help FanFan by computing, for each day, the number of ordered pairs \((u, v)\) that satisfy the condition for that day.

Explanation: For a given query with colors \(x\) and \(y\), consider the subgraph obtained by deleting all nodes whose color is not in \(\{x, y\}\). This subgraph may break into several connected components. In any component of size \(s\), any ordered pair of nodes \((u, v)\) (including when \(u = v\)) will have a path entirely comprised of allowed colors, contributing \(s^2\) valid pairs. The answer for the query is the sum of \(s^2\) over all components.

Note: Use LaTeX formatting for mathematical expressions.

inputFormat

The first line contains two integers \(n\) and \(q\) \((1 \leq n, q \leq \text{small constraints})\) — the number of nodes in the tree and the number of days (queries).

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\), where \(a_i\) is the color of the i-th node.

The next \(n-1\) lines each contain two integers \(u\) and \(v\) denoting an edge between nodes \(u\) and \(v\). It is guaranteed that these edges form a tree.

The following \(q\) lines each contain two distinct integers \(x_i\) and \(y_i\) indicating the two colors favored on the i-th day.

outputFormat

For each day, output a single line containing one integer — the number of valid ordered pairs \((u, v)\) such that the unique path from \(u\) to \(v\) contains only nodes whose colors are in \(\{x_i, y_i\}\).

sample

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

16
5
5