Coloring

Problem Source

SDOI2011

Problem Description

Given an unrooted tree with $n$ nodes and $m$ operations, of two types:

1. Color all nodes on the path from node $a$ to node $b$ (including $a$ and $b$) with colour $c$.
2. Query the number of colour segments on the path from node $a$ to node $b$.

A colour segment is defined as a maximal run of consecutive nodes of the same colour. For example, 112221 consists of three colour segments: 11, 222, 1.

Input Format

The first line contains two integers separated by a space: $n$ (the number of nodes) and $m$ (the number of operations).

The second line contains $n$ integers separated by spaces; the $i$-th integer $w_i$ is the initial colour of node $i$.

The next $n - 1$ lines each contain two integers $u, v$ separated by a space, meaning there is an edge between node $u$ and node $v$.

The next $m$ lines each describe one operation, in the following format:

Each line begins with a character $op$ indicating the type of operation.

• If $op$ is C, it is a colouring operation; after a space there are three integers $a, b, c$ separated by spaces, meaning colour all nodes on the path from $a$ to $b$ with colour $c$.
• If $op$ is Q, it is a query operation; after a space there are two integers $a, b$, meaning query the number of colour segments on the path from $a$ to $b$.

It is guaranteed that $1 \le n, m \le 10^5,\ 1 \le w_i, c \le 10^9$.

Output Format

For each query operation, output one line containing one integer: the answer.

Sample Input

6 5
2 2 1 2 1 1
1 2
1 3
2 4
2 5
2 6
Q 3 5
C 2 1 1
Q 3 5
C 5 1 2
Q 3 5

Sample Output

3
1
2