Description

一棵树$T$,节点带权,两种操作:

Change x y : 将编号为$x$ 的结点的权值修改为$y$ 。

Query k : 询问有多少棵 $T$ 的非空连通子树,满足其中所有点权值的异或和恰好为$k$ 。

Input

第一行包含两个正整数$n$ , $m$ ,分别表示结点的个数以及权值的上限+1。

第二行包含$n$ 个非负整数 $v_i$表示权值.

接下来$n-1$行,每行两个数,描述一条边.

接下来一行包含一个正整数$q$,表示小Q操作的次数。

接下来$q$ 行每行依次表示每个操作。

$n, q \le 3 \times 10^4, m \le 128$,修改操作不超过$10^4$.

Output

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

Solution

很有代表性的一道动态DP问题.

先考虑暴力怎么做,设$f[i][j]$表示包含$i$的连通块($i$为连通块中深度最小的节点),异或和为$j$的方案数,从下往上DP即可.注意到在合并子树信息时实际上是在做异或卷积,可以用FWT优化,事实上我们可以全程用FWT之后的数组计算,算答案时再FWT回去,此时的复杂度为$O(nqm + qm\log m)$.

接下来要支持动态修改,那么树上的修改问题可以用树链剖分转化为重链上的序列问题,设重链上$i$的重儿子为$j$,轻儿子集合为$child(i)$.

方便起见我们先用集合幂级数来表示之前的DP转移(这里的乘法均定义为异或卷积):

最后的$z^0$代表空树,统计答案时应去掉.用另一个幂级数$G$来统计答案:

我们将轻儿子的部分视为常数,设:

从向量$(F_j, G_j, 1)$到$(F_i, G_i, 1)$就是一个线性变换,可以用一个矩阵表示:

利用矩阵乘法的结合律,我们在重链上用线段树维护转移矩阵,得到重链顶的$F, G$,并对上一条重链的矩阵做修改即可,这样只需修改$log$个矩阵.另一个问题是重链顶的父亲$Fl_i(z)$需要重新计算,同样可以用线段树解决.

一个常数上的优化是,矩阵乘法时若某一项为$0$则可直接跳过,这一优化效果显著,这是因为上式中的矩阵做乘积后一定会形如:

那么我们只记录$a, b, c, d$即可,总的复杂度为$O(qm (\log^2 n + log m))$.

Source

#include <bits/stdc++.h>

#define For(i, j, k) for (int i = j; i <= k; ++i)

using namespace std;

const int N = 3e4 + 10;
const int Mod = 1e4 + 7, inv2 = (Mod + 1) / 2;

struct func{

	const static int L = 128;

	int x[L];

	func(int id = 0) {
		memset(x, 0, sizeof x);
		if (id == 1) For(i, 0, L - 1) x[i] = 1;
	}

	void operator = (const func& A) {
		memcpy(x, A.x, sizeof x);
	}

	func operator + (const func& A) const {
		func ret;
		For(i, 0, L - 1) ret.x[i] = (x[i] + A.x[i]) % Mod;
		return ret;
	}

	func operator - (const func& A) const {
		func ret;
		For(i, 0, L - 1) ret.x[i] = (x[i] - A.x[i] + Mod) % Mod;
		return ret;
	}

	func operator * (const func& A) const {
		func ret;
		For(i, 0, L - 1) ret.x[i] = x[i] * A.x[i] % Mod;
		return ret;
	}

	void FWT() {
		for (int i = 1; i < L; i <<= 1)
			for (int j = 0; j < L; j += (i << 1))
				for (int k = 0; k < i; ++k) {
					int u = x[j + k], v = x[i + j + k];
					x[j + k] = (u + v) % Mod, x[i + j + k] = (u - v + Mod) % Mod;
				}
	}

	void DFWT() {
		for (int i = 1; i < L; i <<= 1)
			for (int j = 0; j < L; j += (i << 1))
				for (int k = 0; k < i; ++k) {
					int u = x[j + k], v = x[i + j + k];
					x[j + k] = (u + v) * inv2 % Mod, x[i + j + k] = (u - v + Mod) * inv2 % Mod;
				}
	}

}base[128];

struct Info {

	func a, b, c, d;

	Info operator * (const Info &B) const {
		return (Info) {a * B.a, a * B.b + b, B.a * c + B.c, B.b * c + d + B.d};
	}
};

template <class Type>
struct Segment_Tree {

	const static int Node = 1e5 + 10;

	Type A[Node];
	int lc[Node], rc[Node], sz[Node], node;

	#define M ((L + R) >> 1)

	void modify(int &o, int L, int R, int x, const Type& val) {
		if (!o) o = ++node;
		++sz[o];
		if (L == R) A[o] = val;
		else {
			if (x <= M) modify(lc[o], L, M, x, val);
			else modify(rc[o], M + 1, R, x, val);
			if (sz[o] > R - L) A[o] = A[rc[o]] * A[lc[o]];
		}
	}
	
};

Segment_Tree<Info> F;
Segment_Tree<func> FL;

int Begin[N], Next[N << 1], to[N << 1], e;

void add(int u, int v) {
	to[++e] = v, Next[e] = Begin[u], Begin[u] = e;
}

int n, q;

int fa[N], son[N], sz[N], ch[N], id[N], w[N];

void DFS_init(int o) {
	sz[o] = 1;
	for (int i = Begin[o]; i; i = Next[i]) {
		int u = to[i];
		if (u == fa[o]) continue;
		fa[u] = o;
		DFS_init(u);
		sz[o] += sz[u];
		if (sz[u] > sz[son[o]]) son[o] = u;
	}
}

int rth[N], rtl[N], top[N], idc[N], len[N], tail[N];
func fl[N], f[N], g[N], gl[N];

void DFS_decompose(int o) {
	if (son[fa[o]] == o) {
		idc[o] = idc[fa[o]] + 1;
		top[o] = top[fa[o]], len[top[o]]++;
	} else {
		idc[o] = len[o] = 1;
		top[o] = o;
	}
	tail[top[o]] = o;

	for (int i = Begin[o]; i; i = Next[i]) {
		int u = to[i];
		if (u == fa[o] || u == son[o]) continue;
		id[u] = ++ch[o];
		DFS_decompose(u);
		gl[o] = gl[o] + g[u];
	}
	++ch[o];

	for (int i = Begin[o]; i; i = Next[i]) {
		int u = to[i];
		if (u == fa[o] || u == son[o]) continue;
		FL.modify(rtl[o], 1, ch[o], id[u], f[u]);
	}

	FL.modify(rtl[o], 1, ch[o], ch[o], base[w[o]]);
	fl[o] = FL.A[rtl[o]];

	if (son[o]) {
		DFS_decompose(son[o]);
		F.modify(rth[top[o]], 1, len[top[o]], idc[o],
				(Info){fl[o], fl[o], 1, gl[o]});
	} else {
		F.modify(rth[top[o]], 1, len[top[o]], idc[o], 
				(Info){1, 0, 0, 0});
	}

	if (o == top[o]) {
		const Info& p = F.A[rth[o]];
		g[o] = (fl[tail[o]] + 1) * p.b + base[w[tail[o]]] + p.d;
		f[o] = (fl[tail[o]] + 1) * p.a + p.c;
	}
}


int main() {

	scanf("%d%*d", &n);
	For(i, 1, n) scanf("%d", &w[i]);
	For(i, 2, n) {
		int u, v;
		scanf("%d%d", &u, &v);
		add(u, v), add(v, u);
	}
	
	For(i, 0, 127) base[i].x[i] = 1, base[i].FWT();
	DFS_init(1);
	DFS_decompose(1);

	scanf("%d", &q);
	while (q--) {
		char op[10];
		scanf("%s", op);

		if (op[0] == 'Q') {
			int val;
			scanf("%d", &val);
			func ans = g[1];
			ans.DFWT();
			printf("%d\n", ans.x[val]);
		} else {
			int o, y;
			scanf("%d%d", &o, &y);
			FL.modify(rtl[o], 1, ch[o], ch[o], base[y]);
			fl[o] = FL.A[rtl[o]];
			w[o] = y;
			
			while (o) {
				int s = top[o];
				if (son[o]) 
					F.modify(rth[s], 1, len[s], idc[o], (Info){fl[o], fl[o], 1, gl[o]});

				const Info& p = F.A[rth[s]];
				if (fa[s]) gl[fa[s]] = gl[fa[s]] - g[s];
				g[s] = (fl[tail[s]] + 1) * p.b + base[w[tail[s]]] + p.d;
				f[s] = (fl[tail[s]] + 1) * p.a + p.c;

				o = fa[s];
				if (o) {
					FL.modify(rtl[o], 1, ch[o], id[s], f[s]);
					fl[o] = FL.A[rtl[o]];
					gl[o] = gl[o] + g[s];
				}
			}
		}
	}

	return 0;
}