#bzoj4999. This Problem Is Too Simple!

    ID: 5509 远端评测题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 8 上传者: 标签>树结构树链剖分数据结构线段树bzoj

This Problem Is Too Simple!

题目描述

给您一颗树,每个节点有个初始值。

现在支持以下两种操作:

  1. C i x表示将ii节点的值改为xx。
  2. Q i j x 表示询问ii节点到jj节点的路径上有多少个值为xx的节点。

输入格式

第一行有两个整数N,QN,Q,分别表示节点个数和操作个数。

下面一行NN个整数,表示初始时每个节点的初始值。

接下来N−1N-1行,每行两个整数x,yx,y,表示xx节点与yy节点之间有边直接相连(描述一颗树)。

接下来QQ行,每行表示一个操作,操作的描述已经在题目描述中给出。

输出格式

对于每个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

数据规模与约定

对于100%100\%的数据:1≤N≤100 000,1≤Q≤200 000,0≤x<2311 ≤N≤ 100\,000,1 ≤Q≤ 200\,000,0\le x<2^{31}