Description：

给一棵树，每个点有点权（小于 $m$ ），支持修改点权，和查询异或和为 $k$ 的联通块个数。

$1\leqslant n\leqslant 30000,1\leqslant m\leqslant 128$

Solution：

动态 $DP+FWT$ 还是比较显然的。

考虑用一个多项式作为 $DP$ 数组， $f[i][1]$ 表示必须选子树根的联通块个数， $f[i][0]$ 无要求， $k$ 位置的值就是异或和为 $k$ 的联通块个数，那么转移为： $$ \begin{align} f[k][1]&=f[k][1]+f[k][1]\oplus f[e[i].to][1]=f[k][1]\times(f[e[i].to][1]+1)\\ f[k][0]&=\sum f[e[i].to][0]+f[k][1]\\ \end{align} $$ $'+'$ 代表对应相加， $'\oplus'$ 代表异或卷积。

按照动态 $DP$ 的套路维护一个只与虚儿子有关的量， $g[k][1]$ 表示所有虚儿子异或卷积起来的值， $g[k][0]$ 表示所有虚儿子的 $f[k][0]$ 的和还有这个点的 $f[k][1]$ 。那么考虑一个重链，发现要求的就是所有区间的异或值为某个数的个数，类似最大联通块和那道题的做法，那么就维护一个前缀 $FWT$ 数组和后缀 $FWT$ 数组，然后两边卷积起来，并把这个还有两边的值累加到答案里即可。

但是这样做会被卡常，所以干脆只在进入和退出的时候 $FWT$ ，中间 $DP$ 一直使用 $FWT$ 之后的数组能卡掉不少常数，但是有有一个问题，就是怎么单点加，分析一下 $FWT$ 那个 $tf$ 函数的性质会发现其实变成了所有位置都 $+1$ 。

这样做还有一个问题，动态 $DP$ 要求我们必须能去除子树的贡献，然而这道题如果方案数是 $10007$ 的倍数，就会没有逆元，这样答案就不是可减的了，一种做法是利用线段树分治，容易理解但代码量大，另一种做法是另开一种结构体叫做 $data$ ，专门维护所有虚儿子的信息，并且不包括他自己，然后每个位置维护一个 $cnt$ 表示这个位置 $\times0$ 有多少次， $f$ 表示这个位置除去 $0$ 的乘积，然后乘和除加一加减一减就行了，对于这个点的值，我们可以在用一个结构体维护，每次从 $data$ 里把他除掉，然后对他进行操作，然后再把他乘回去。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int n,m,q;

#define MAXN 30010

#define MAXM 130

#define MOD 10007

#define INV2 5004

int inv[MOD];

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

inline void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int val[MAXN];

int fa[MAXN],dep[MAXN],son[MAXN],siz[MAXN],top[MAXN],bot[MAXN];

int rnk[MAXN],th[MAXN],tot = 0;

void dfs1(int k,int depth)

{

	dep[k] = depth;siz[k] = 1;

	for(register int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k])

		{

			fa[e[i].to] = k;

			dfs1(e[i].to,depth + 1);

			siz[k] += siz[e[i].to];

			if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

			{

				son[k] = e[i].to;

			}

		}

	}

	return;

}

void dfs2(int k,int tp)

{

	top[k] = tp;

	rnk[k] = ++tot;th[tot] = k;

	if(son[k] == 0){bot[k] = k;return;}

	dfs2(son[k],tp);bot[k] = bot[son[k]];

	for(register int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k] && e[i].to != son[k])

		{

			dfs2(e[i].to,e[i].to);

		}

	}	

	return;

}

inline int power(int a,int b)

{

	register int res = 1;

	while(b > 0)

	{

		if(b & 1)res = res * a % MOD;

		a = a * a % MOD;

		b = b >> 1;

	}

	return res;

}

struct poly

{

	int f[MAXM];

	int& operator [](int x){return f[x];}

	inline void FWT(int type)

	{

		for(register int i = 2;i <= m;i = i << 1)

		{

			for(register int j = 0;j < m;j += i)

			{

				for(int k = j;k < j + i / 2;++k)

				{

					register int u = f[k],t = f[k + i / 2];

					f[k] = (u + t) % MOD;

					f[k + i / 2] = (u - t + MOD) % MOD;

					if(type == -1)

					{

						f[k] = f[k] * INV2 % MOD;

						f[k + i / 2] = f[k + i / 2] * INV2 % MOD;

					}

				}

			}

		}

		return;

	}

	inline friend poly operator * (poly a,poly b)

	{

		for(register int i = 0;i < m;++i)

		{

			a[i] = a[i] * b[i] % MOD;

		}

		return a;

	}

	inline friend poly operator / (poly a,poly b)

	{

		for(register int i = 0;i < m;++i)

		{

			a[i] = a[i] * inv[b[i]] % MOD;

		}

		return a;

	}

	inline friend poly operator + (poly a,poly b)

	{

		for(register int i = 0;i < m;++i)a[i] = (a[i] + b[i]) % MOD;

		return a;

	}

	inline friend poly operator - (poly a,poly b)

	{

		for(register int i = 0;i < m;++i)a[i] = (a[i] - b[i] + MOD) % MOD;

		return a;

	}

	inline void inc()

	{

		for(register int i = 0;i < m;++i)f[i] = (f[i] + 1) % MOD;

		return;

	}

}f[MAXN][2],g0[MAXN],w[MAXN];

struct data

{

	poly f;

	int cnt[MAXM];

	data(){memset(cnt,0,sizeof(cnt));}

	friend data operator * (data a,poly b)

	{

		for(int i = 0;i < m;++i)

		{

			if(b[i] == 0)++a.cnt[i];

			else a.f[i] = a.f[i] * b[i] % MOD;

		}

		return a;

	}

	friend data operator / (data a,poly b)

	{

		for(int i = 0;i < m;++i)

		{

			if(b[i] == 0)--a.cnt[i];

			else a.f[i] = a.f[i] * inv[b[i]] % MOD;

		}

		return a;

	}

	poly get()

	{

		poly res;

		for(int i = 0;i < m;++i)

		{

			if(cnt[i] == 0)res[i] = f[i];

			else res[i] = 0;

		}

		return res;

	}

}g1[MAXN];

bool vis[MAXN];

void dp(int k)

{

	vis[k] = true;

	for(register int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		dp(e[i].to);

		f[e[i].to][1].inc();

		f[k][1] = f[k][1] * f[e[i].to][1];

		f[k][0] = f[k][0] + f[e[i].to][0];

		if(e[i].to != son[k])

		{

			g1[k] = g1[k] * f[e[i].to][1];

			g0[k] = g0[k] + f[e[i].to][0];

		}

	}

	f[k][0] = f[k][0] + f[k][1];

	return;

}

struct state

{

	poly ls,rs,s,ms;

	inline friend state operator + (state a,state b)

	{

		register state res;

		res.s = a.s * b.s;

		res.ls = a.ls + a.s * b.ls;

		res.rs = b.rs + b.s * a.rs;

		res.ms = a.ms + b.ms + a.rs * b.ls;

		return res;

	}

};

struct node

{

	int lc,rc;

	state s;

}t[MAXN << 1];

int ptr = 0;

inline int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)

	{

		g1[th[l]] = g1[th[l]] * w[th[l]];

		t[rt].s.ls = t[rt].s.rs = t[rt].s.s = g1[th[l]].get();

		t[rt].s.ms = g1[th[l]].get() + g0[th[l]];

		return;

	}

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	t[rt].s = t[t[rt].lc].s + t[t[rt].rc].s;

	return;

}

void maintain(int rt,int p,int l,int r)

{

	if(l == r)

	{

		t[rt].s.ls = t[rt].s.rs = t[rt].s.s = g1[th[l]].get();

		t[rt].s.ms = g1[th[l]].get() + g0[th[l]];

		return;

	}

	if(p <= mid)maintain(t[rt].lc,p,l,mid);

	else maintain(t[rt].rc,p,mid + 1,r);

	t[rt].s = t[t[rt].lc].s + t[t[rt].rc].s;

	return;

}

state query(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)return t[rt].s;

	if(R <= mid)return query(t[rt].lc,L,R,l,mid);

	if(L > mid)return query(t[rt].rc,L,R,mid + 1,r);

	return query(t[rt].lc,L,R,l,mid) + query(t[rt].rc,L,R,mid + 1,r);

}

inline void modify(int k,int v)

{

	g1[k] = g1[k] / w[k];

	w[k].FWT(-1);

	w[k][val[k]] = (w[k][val[k]] - 1 + MOD) % MOD;

	val[k] = v;

	w[k][val[k]] = (w[k][val[k]] + 1) % MOD;

	w[k].FWT(1);

	g1[k] = g1[k] * w[k];

	while(k != 0)

	{

		register state a = query(root,rnk[top[k]],rnk[bot[k]],1,n);

		maintain(root,rnk[k],1,n);

		register state b = query(root,rnk[top[k]],rnk[bot[k]],1,n);

		register int anc = fa[top[k]];

		a.ls.inc();b.ls.inc();

		g0[anc] = g0[anc] - a.ms + b.ms;

		g1[anc] = g1[anc] / a.ls * b.ls;

		k = anc;

	}

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	inv[0] = 0;for(int i = 1;i < MOD;++i)inv[i] = power(i,MOD - 2);

	for(register int i = 1;i <= n;++i)val[i] = rd();

	for(register int i = 1;i < n;++i)add(rd(),rd());

	dfs1(1,1);dfs2(1,1);

	for(register int i = 1;i <= n;++i)

	{

		f[i][1][val[i]] = g1[i].f[0] = 1;w[i].f[val[i]] = 1;

		f[i][1].FWT(1);g1[i].f.FWT(1);w[i].FWT(1);

	}

	dp(1);

	build(root,1,n);

	scanf("%d",&q);

	register char c[10];

	register int k,v;

	register poly res;

	for(register int i = 1;i <= q;++i)

	{

		scanf("%s",c);

		if(c[0] == 'Q')

		{

			k = rd();

			res = query(root,rnk[top[1]],rnk[bot[1]],1,n).ms;

			res.FWT(-1);

			printf("%d\n",res[k]);

		}

		else

		{

			k = rd();v = rd();

			modify(k,v);

		}

	}

	return 0;

}