#P4999. This Problem Is Too Simple!

    ID: 4098 传统题 1000ms 256MiB 尝试: 859 已通过: 196 难度: 6 上传者: 标签>难度分类提高树算法LCA树上倍增欧拉序排序与序列处理一维差分数据结构树状数组离散化离线预收集坐标局部离散化CF2100鸣谢佚名上传

This Problem Is Too Simple!

This Problem Is Too Simple!

题目描述

给定一棵树,每个顶点有一个初始值。处理两种操作。

  • C i x 将顶点 ii 的值改为 xx。
  • Q i j x 询问从顶点 ii 到顶点 jj 的唯一路径上,有多少个顶点的值等于 xx。路径包含两个端点。

操作中的 xx 满足 0≤x<2310\le x<2^{31}。

输入格式

第一行两个整数 N,QN,Q,表示顶点数和操作数,满足 1≤N≤1000001\le N\le100000、1≤Q≤2000001\le Q\le200000。

第二行 NN 个整数,表示从 11 到 NN 的各顶点初始值。接下来 N−1N-1 行,每行两个整数 u,vu,v,表示一条连接顶点 u,vu,v 的无向边。

最后 QQ 行,每行一个操作。

输出格式

每个查询操作输出一行一个整数。

样例

5 6
10 20 30 40 50
1 2
1 3
3 4
3 5
Q 2 3 40
C 1 40
Q 2 3 40
Q 4 5 30
C 3 10
Q 4 5 30
0
1
1
0