Tree Path Color Segments Queries

The problem presents you with a tree of n nodes and n-1 edges. Initially, each node has a tumor with a given color. Then, there are q operations. There are two types of operations:

• Update Operation: Given two nodes u and v and a new color c, change the color of every tumor on the simple path from u to v to c.
• Query Operation: Given an integer m and a set of m nodes S, for each node i in S, calculate its weight W_i, defined as follows:

$$W_i=\sum_{j\in S}T(i,j)$$

Here, T(i,j) is the number of color segments along the simple path from node i to node j. For example, if the colors along the path are 1 2 2 3 3 1 2, then the number of segments is 5 (the segments being: 1, 2, 3, 1, and 2).

For each query operation, output one line with m integers, where each integer is the corresponding node’s weight, in the order provided in the query.

inputFormat

The input begins with two integers n and q (the number of nodes and the number of operations).

The second line contains n integers, representing the initial colors of nodes 1 to n.

Then follow n-1 lines, each containing two integers u and v, denoting an edge between nodes u and v.

After that, there are q lines, each representing an operation. An operation is of one of the following two types:

• Update Operation: A line formatted as "1 u v c", meaning update all nodes along the simple path from u to v to the color c.
• Query Operation: A line formatted as "2 m s₁ s₂ ... s_m", which represents a query on the set S = {s₁, s₂, ..., s_m}.

outputFormat

For each query operation (type 2), output one line with m integers. The i-th integer on that line is the weight W_i of the corresponding node in the query, computed as the sum over all nodes in the query set of the number of color segments on the simple path between them.

sample

5 5
1 2 3 4 5
1 2
2 3
3 4
4 5
2 3 1 3 5
1 1 5 7
2 2 2 4
1 2 3 9
2 3 1 2 3

9 7 9
2 2
5 4 4