切树游戏

题目描述:

小Q是一个热爱学习的人，他经常去维基百科学习计算机科学。
就在刚才，小Q认真地学习了一系列位运算符，其中按位异或的运算符⊕对他影响很大。按位异或的运算符是双目运算符。按位异或具有交换律，即i ⊕ j = j ⊕ i。
他发现，按位异或可以理解成被运算的数字的二进制位对应位如果相同，则结果的该位置为0，否则为1，例如：1(01) ⊕ 2(10) = 3(11)。
他还发现，按位异或可以理解成参与运算的数字的每个二进制位都进行了不进位的加法，例如：
3(11) ⊕ 3(11) = 0(00)。
现在小Q有一棵n个结点的无根树T，结点依次编号为1到n，其中结点i的权值为vi。
定义一棵树的价值为它所有点的权值的异或和，一棵树T的连通子树就是它的一个连通子图，并且这个图也是一棵树。
小Q想要在这棵树上玩切树游戏，他会不断做以下两种操作：
• Change x y 将编号为x的结点的权值修改为y。
• Query k 询问有多少棵T的非空连通子树，满足其价值恰好为k。
小Q非常喜(bu)欢(hui)数学，他希望你能快速回答他的问题，你能写个程序帮帮他吗？

输入格式:

第一行包含两个正整数n; m，分别表示结点的个数以及权值的上限。
第二行包含n个非负整数v1; v2; :::; vn，分别表示每个结点一开始的权值。
接下来n - 1行，每行包含两个正整数ai; bi，表示有一条连接ai和bi的无向树边。
接下来一行包含一个正整数q，表示小Q操作的次数。
接下来q行每行依次表示每个操作。

输出格式:

输出若干行，每行一个整数，依次回答每个询问。因为答案可能很大，所以请对10007取模输出。

样例输入:

4 4
2 0 1 3
1 2
1 3
1 4
12
Query 0
Query 1
Query 2
Query 3
Change 1 0
Change 2 1
Change 3 3
Change 4 1
Query 0
Query 1
Query 2
Query 3

样例输出:

3
3
2
3
2
4
2
3

下载附加文件

提示:

对于100%的数据，1 ≤ ai; bi; x ≤ n; 0 ≤ vi; y; k < m，修改操作不超过10000个。

测试点编号	n	m	q	约定
1,2,3,4	≤ 2000	= 64	≤ 64	不存在修改操作
5,6,7,8	≤ 30000	= 8	≤ 30000	ai = i; bi = i + 1
9,10	≤ 30000	= 128	≤ 30000	ai = i; bi = i + 1
11,12,13,14,15	≤ 30000	= 4	≤ 30000	无
16,17,18,19,20	≤ 30000	= 128	≤ 30000	无

 

时间限制: 3000ms
空间限制: 256MB

---

来源: 山东省选2017day3t3