P14734 [ICPC 2021 Seoul R] Ant Colonies

一组科学家研究了一个居住着多个蚁群的蚁巢。他们发现蚁巢是一种树形结构，其中每个节点代表一个蚁群生活的物理位置，每条边代表连接两个蚁群的隧道。最有趣的是，每个蚁群恰好有一种颜色，并且有时会改变其颜色。颜色变化机制依赖于两个给定蚁群 $A$ 和 $B$ 之间路径上所有蚁群中，具有特定颜色 $c$ 的**最近的一对蚁群**。两个蚁群之间的距离是连接它们的路径上的隧道数量，即树形结构中连接两个对应节点的路径上的边数。 例如，图 A.1 (a) 展示了一个包含五个蚁群的树形结构，蚁群编号从 $1$ 到 $5$，颜色分别为 $1, 2, 2, 2, 1$（用橙色标签标在蚁群上方）。对于颜色 $2$ 和两个蚁群 $2$ 与 $5$，在蚁群 $2$ 和蚁群 $5$ 之间路径上具有颜色 $2$ 的最近一对蚁群是（蚁群 $2$, 蚁群 $3$）。但对于蚁群 $2$ 和蚁群 $4$，具有颜色 $2$ 的最近一对是（蚁群 $3$, 蚁群 $4$）。 假设现在蚁群 $3$ 的当前颜色 $2$ 变为颜色 $3$，如图 A.1 (b) 所示。那么在蚁群 $2$ 和蚁群 $5$ 之间的路径上，就不存在具有颜色 $2$ 的最近一对蚁群，因为只有一个蚁群具有颜色 $2$。对于蚁群 $2$ 和蚁群 $4$，具有颜色 $2$ 的最近一对变为（蚁群 $2$, 蚁群 $4$）。 给定蚁群的颜色、蚁巢的树形结构以及颜色更新的命令列表和查询最近一对的查询命令，请编写一个程序，针对每个查询 $(A, B, c)$，找出蚁群 $A$ 和 $B$ 之间路径上具有颜色 $c$ 的最近一对蚁群。 :::align{center}  图 A.1 一个包含五个蚁群的蚁巢。橙色数字表示蚁群颜色。 :::

你的程序需要从标准输入读取数据。输入的第一行包含两个整数 $n$ 和 $q$ ($2 \leq n \leq 100,000$, $2 \leq q \leq 100,000$)，其中 $n$ 是蚁群的数量，$q$ 是更新和查询命令的数量。蚁群编号从 $1$ 到 $n$，颜色用 $1$ 到 $n$ 的整数标识。第二行包含 $n$ 个正整数，按从蚁群 $1$ 到蚁群 $n$ 的顺序表示蚁群的颜色。接下来的 $n-1$ 行中，第 $i$ 行包含两个整数 $a_i, b_i$ ($1 \leq a_i, b_i \leq n, a_i \neq b_i$)，表示由一条隧道连接的两个蚁群的编号，对应树形结构中的一条边。接下来的 $q$ 行中，第 $i$ 行的格式为 $(S,A,c)$ 或 $(S,A,B,c)$，其中 $S$ 是一个大写字符，取值为 'U' 或 'Q'，分别代表更新和查询。如果 $S = U$，则格式为 $(S,A,c)$，这是一个更新命令，表示将蚁群 $A$ 的当前颜色更改为颜色 $c$ ($1 \leq A, c \leq n$)。如果 $S = Q$，则格式为 $(S,A,B,c)$，这是一个查询命令，要求输出在蚁群 $A$ 和 $B$ 之间路径上具有颜色 $c$ 的最近一对蚁群的距离 ($1 \leq A,B,c \leq n$)。这些命令必须按照输入中给出的顺序执行。

你的程序需要向标准输出写入数据。对于每个 $S = Q$ 的查询 $(S,A,B,c)$，输出恰好一行，包含在当前蚁巢状态下，蚁群 $A$ 和 $B$ 之间路径上具有颜色 $c$ 的最近一对蚁群的距离。如果它们之间不存在具有颜色 $c$ 的蚁群对，则输出 $-1$。

翻译由 DeepSeek V3 完成