P2486 [SDOI2011] Coloring

Given an unrooted tree with $n$ nodes, there are $m$ operations of two types: 1. Color all nodes on the path from node $a$ to node $b$ (including $a$ and $b$) with color $c$. 2. Query the number of color segments on the path from node $a$ to node $b$. A color segment is defined as a maximal consecutive run of the same color. For example, `112221` consists of three segments: `11`, `222`, `1`.

The first line contains two integers separated by a space, representing the number of nodes $n$ and the number of operations $m$. The second line contains $n$ integers separated by spaces. The $i$-th integer $w_i$ represents the initial color of node $i$. Lines $3$ through $(n + 1)$ each contain two integers $u, v$ separated by a space, indicating that there is an edge between nodes $u$ and $v$ in the tree. Lines $(n + 2)$ through $(n + m + 1)$ each describe an operation in the following format: Each line starts with a character $op$, indicating the type of operation. - If $op$ is `C`, it denotes a coloring operation. After a space, there are three integers $a, b, c$ separated by spaces, meaning that all nodes on the path from $a$ to $b$ are colored with color $c$. - If $op$ is `Q`, it denotes a query operation. After a space, there are two integers $a, b$ separated by a space, indicating a query for the number of color segments on the path from $a$ to $b$.

For each query operation, output a single line containing one integer representing the answer.

#### Constraints For $100\%$ of the testdata, $1 \leq n, m \leq 10^5$, $1 \leq w_i, c \leq 10^9$, $1 \leq a, b, u, v \leq n$, $op$ is guaranteed to be `C` or `Q`, and the given graph is a tree. In addition to the original testdata, there exists a non-scoring set of hack testdata. Translated by ChatGPT 5