Tree Path Color Queries

You are given a rooted tree with \(n\) nodes, where the root is node \(1\). Each node \(i\) has a color \(a_i\). You need to support \(m\) queries of two types:

1. 1 x y: Query the number of distinct colors on the shortest path between nodes \(x\) and \(y\).
2. 2 a b: Consider the path from node \(a\) to the root and the path from node \(b\) to the root. A node \(x\) is chosen uniformly at random from the first path and a node \(y\) from the second path. Let \(\mathrm{ans}\) be the answer (i.e. the distinct color count) for query type 1 on nodes \(x\) and \(y\), and let \(\mathrm{cnt_a}\) and \(\mathrm{cnt_b}\) be the number of nodes on the respective paths. You only need to output \(\mathrm{ans} \times \mathrm{cnt_a} \times \mathrm{cnt_b}\), which is equivalent to the sum of the answers for every pair \((x, y)\) with \(x\) coming from the first path and \(y\) from the second path.

The input is given as follows:

• The first line contains two integers \(n\) and \(m\).
• The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) representing the colors of the nodes.
• 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 with root \(1\).
• The following \(m\) lines each represent a query in one of the two formats described above.

inputFormat

The input begins with a line containing two integers \(n\) and \(m\) \( (1 \leq n, m \leq \text{some limit}) \). The next line contains \(n\) integers representing the node colors \(a_1, a_2, \ldots, a_n\). Then follow \(n - 1\) lines, each with two integers \(u\) and \(v\), indicating an undirected edge in the tree. Finally, there are \(m\) lines each with a query. A query is in one of the following formats:

• 1 x y
• 2 a b

For a query of type 2, the answer is computed as explained in the problem description, and you are required to output \(\mathrm{ans} \times \mathrm{cnt_a} \times \mathrm{cnt_b}\).

outputFormat

For each query, output a single integer in a new line representing the answer for that query.

sample

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

2
16
3

</p>