Problem 2409. -- 小奇的花园

2409: 小奇的花园

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 2  Solved: 1
[Submit][Status][Web Board]

Description

【题目背景】
小奇在家中的花园漫步时,总是会思考一些奇怪的问题。
【问题描述】
小奇的花园有n个温室,标号为1到n,温室以及以及温室间的双向道路形成一棵树。每个温室都种植着一种花,随
着季节的变换,温室里的花的种类也在不断发生着变化。小奇想知道从温室x走到温室y的路径中(包括两个端点),
第t种花出现的次数。

Input

第一行为两个整数n,q,表示温室的数目和操作的数目。
第二行有n个整数T1,T2…Tn其中Ti表示温室i中的花的种类。
接下来n-1行,每个两个整数x, y,表示温室x和y之间有一条双向道路。
接下来q行,表示q个操作,分别为以下两种形式之一:
C x t 表示在温室x中的花的种类变为t。
Q x y t 表示询问温室x走到温室y的路径中(包括两个端点),第t种花出现的次数。
为了体现在线操作,输入数据中的每个操作的参数都进行了加密。
记最后一次询问的答案为anslast(一开始设anslast为0),下次读入中的x,y,t均需要异或上anslast以得到真实值,
在C/C++中异或为?运算符,在pascal中为xor运算符。
n <= 100000, q <= 200000,0 <= T < 2^31。

Output

输出q行,每行一个正整数表示该次询问答案。

Sample Input

5 8
10 20 30 40 50
1 2
1 3
3 4
3 5
Q 2 5 10
C 2 21
Q 3 4 21
C 6 22
Q 1 7 28
C 5 20
Q 2 5 20
Q 2 0 9

Sample Output

1
2
0
3
1
【样例解释】
加密前的操作:
Q 2 5 10
C 3 20
Q 2 5 20
C 4 20
Q 3 5 30
C 5 20
Q 2 5 20
Q 1 3 10

HINT

Source

[Submit][Status]