Description

The tree has $n$ nodes connected by $n-1$ edges. Initially, there is one “tumor” hanging on each node, with color $c_i$. Then Salamander will perform $q$ operations.

Sometimes Salamander will change the colors of all “tumors” on the simple path from one node to another.

For a given set of nodes on the tree, namely the point set $\bm{S}$, Salamander defines the weight of a node:

where $T(i,j)$ denotes the number of color segments along the path from $i$ to $j$. For example, if the colors along the path from $i$ to $j$ are $1223312$, the number of segments is $5$.

Salamander is very interested in the state of the “tumors” on the tree, so sometimes he will specify $m$ nodes as the set and ask for the weights of these $m$ nodes.

Input Format

The first line contains two positive integers $n$, $q$, the number of nodes in the tree and the number of operations.

The second line contains $n$ space-separated positive integers $c_i$, the initial color of the “tumor” on each node.

The next $n-1$ lines each contain two positive integers $u$, $v$, indicating there is an edge connecting $u$ and $v$.

Then follow $q$ operations:

1. If the first integer is $1$, then there will be three positive integers $u$, $v$, $y$, meaning that all “tumor” colors on the simple path from node $u$ to node $v$ are changed to $y$.
2. If the first integer is $2$, then there will be one positive integer $m$, the number of specified nodes on the tree. The next line contains $m$ distinct positive integers separated by spaces, representing the $m$ nodes in the current query.

Output Format

Output several lines. For each operation of type $2$, output the corresponding answer.

10 10
708916891 100649777 100649777 544409200 100649777 47435517 47435517 708916891 644811607 544409200 
3 2
7 1
8 1
1 10
3 4
1 5
9 2
1 2
3 6
2 1
6 
2 6
8 10 9 3 2 4 
2 2
7 8 
2 1
5 
2 2
6 10 
2 3
6 1 4 
2 1
7 
1 9 8 100649777
1 7 9 544409200
2 4
10 9 1 2 

1 
13 17 15 11 11 15 
3 3 
1 
5 5 
7 7 7 
1 
4 4 4 4 

Hint

The input is guaranteed to be valid.

For $30\%$ of the testdata, $1 \leq n, q \leq 1000$, $\sum m \leq 5000$.

For $60\%$ of the testdata, $1 \leq n, q \leq 20000$, $\sum m \leq 100000$.

For $100\%$ of the testdata, $1 \leq n, q \leq 100000$, $c_i, y \leq 10^9$, $\sum m \leq 200000$, $m \leq n$.

Translated by ChatGPT 5