P4242 Tumors on the Tree

Salamander happily brought home a big bag of “tumors”, dyed them in different colors, and hung them on the tree in the yard.

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: $$W_i=\sum_{j\in S}T(i,j)$$ 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.

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 several lines. For each operation of type $2$, output the corresponding answer.

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