orz rqy。首先可以知道,维护每种值的方案即可。令F_x为x为根的子树的集合幂级数,只需要用\prod (F_y+1)更新即可。
那么无脑FWT一下。之后考虑动态化。那么就维护轻儿子和重链。令H_x表示x轻儿子合并后的东西,那么有F_x=H_x(F_y+1)=H_x+H_xH_{xx'}+...,也就是一堆积的和。
就可以知道一条链的答案就是所有子区间的积的和,线段树可以维护。
之后就是一些(很多)细节问题了。列举一二:
FWT直接单点就可以了。考虑贡献发现就是更改正负号。
在修改时,因为不是用矩阵的方式维护的,要直接从某个H中除掉一部分。但是当是倍数的时候,没有逆元。解决方法是手写一个东西,维护每个点轻儿子中,有多少个0,以及剩下的乘积。
代码在洛谷T了两个点,不知道为什么,貌似被卡了,loj过了。。
// orz rqy jiejie
#include <bits/stdc++.h>
using std::cerr;
using std::endl;
inline int rd() {
int b = 0; char c = getchar();
while (!isdigit(c)) c = getchar();
while (isdigit(c)) b = b * 10 + c - '0', c = getchar();
return b;
}
inline int get_op() {
char c = getchar();
while (!isalpha(c)) c = getchar();
return c == 'Q' ? 1 : 2;
}
const int N = 3e4 + 233, M = 130, P = 10007;
int n, m, q, val[N], cnt[N], inv[N];
int fa[N], son[N], size[N], top[N], dfn[N], id[N], num, bot[N];
int ans[M];
std::vector<int> G[N];
struct Int {
int a, p;
Int(int t = 0) {
a = (t == 0 ? 1 : t);
p = (t == 0);
}
Int(int _a, int _p) { a = _a, p = _p; }
operator int() { return !p ? a : 0; }
Int operator+(int x) {
if ((x %= P) != 0)
return Int(p > 0 ? x : (a + x) % P, 0);
else
return *this;
}
Int& operator*=(int x) {
if (!(x %= P)) ++p;
else a = a * x % P;
return *this;
}
Int& operator/=(int x) {
if (!(x %= P)) --p;
else a = a * inv[(x + P) % P] % P;
return *this;
}
};
Int H[N][M];
int F[N][M];
struct Node {
int sum[M], pre[M], suf[M], mul[M];
inline void init() {
memset(sum, 0, sizeof sum);
memset(pre, 0, sizeof pre);
memset(suf, 0, sizeof suf);
memset(mul, 0, sizeof mul);
for (int i = 0; i < m; ++i)
mul[i] = 1;
}
Node() { init(); }
Node(Int H[]) {
for (int i = 0; i < m; ++i)
sum[i] = pre[i] = suf[i] = mul[i] = H[i];
}
inline friend Node operator*(const Node &l, const Node &r) {
Node ret;
for (int i = 0; i < m; ++i) {
ret.sum[i] = (l.sum[i] + r.sum[i] + l.suf[i] * r.pre[i]) % P;
ret.pre[i] = (l.pre[i] + l.mul[i] * r.pre[i]) % P;
ret.suf[i] = (r.suf[i] + r.mul[i] * l.suf[i]) % P;
ret.mul[i] = l.mul[i] * r.mul[i] % P;
}
return ret;
}
} seg[N * 4], tmp;
#define ls (p << 1)
#define rs (ls | 1)
#define mid ((L + R) >> 1)
inline void pushup(int p, int L, int R) {
if (L != R)
seg[p] = seg[ls] * seg[rs];
else
seg[p] = Node(H[id[L]]);
}
void build(int p, int L, int R) {
if (L != R) {
build(ls, L, mid);
build(rs, mid + 1, R);
}
pushup(p, L, R);
}
void modify(int p, int x, int L, int R) {
if (L != R)
x <= mid ? modify(ls, x, L, mid)
: modify(rs, x, mid + 1, R);
pushup(p, L, R);
}
void query(int p, int l, int r, int L, int R) {
if (l <= L && r >= R)
return tmp = tmp * seg[p], void();
if (l <= mid) query(ls, l, r, L, mid);
if (r > mid) query(rs, l, r, mid + 1, R);
}
void dfs1(int x, int dad) {
fa[x] = dad, size[x] = 1;
for (int y : G[x]) if (y != dad) {
dfs1(y, x);
size[x] += size[y];
if (size[son[x]] < size[y])
son[x] = y;
/*
// what the fuck ??
if (!son[x] || size[son[x]] + 50 < size[y])
son[x] = y;
*/
}
}
void dfs2(int x, int topf) {
top[x] = topf, id[dfn[x] = ++num] = x;
if (!son[x]) {
bot[x] = x;
} else {
dfs2(son[x], topf);
bot[x] = bot[son[x]];
}
for (int i = 0; i < m; ++i)
H[x][i] = 1;
for (int y : G[x])
if (y != fa[x] && y != son[x]) {
dfs2(y, y);
for (int i = 0; i < m; ++i)
H[x][i] *= F[y][i] + 1;
}
for (int i = 0; i < m; ++i)
if (cnt[i & val[x]] & 1)
H[x][i] *= -1;
for (int i = 0; i < m; ++i)
F[x][i] = H[x][i];
if (son[x])
for (int i = 0; i < m; ++i)
F[x][i] = F[x][i] * (F[son[x]][i] + 1) % P;
for (int i = 0; i < m; ++i)
ans[i] = (ans[i] + F[x][i]) % P;
}
void cut(int x) {
if (!x) return;
modify(1, dfn[x], 1, n);
int y = top[x];
cut(fa[y]);
tmp.init();
query(1, dfn[y], dfn[bot[y]], 1, n);
for (int i = 0; i < m; ++i)
ans[i] = (ans[i] - tmp.sum[i] + P) % P;
for (int i = 0; i < m; ++i)
H[fa[y]][i] /= tmp.pre[i] + 1;
}
void link(int x) {
if (!x) return;
modify(1, dfn[x], 1, n);
int y = top[x];
tmp.init();
query(1, dfn[y], dfn[bot[y]], 1, n);
for (int i = 0; i < m; ++i)
ans[i] = (ans[i] + tmp.sum[i]) % P;
for (int i = 0; i < m; ++i)
H[fa[y]][i] *= tmp.pre[i] + 1;
link(fa[y]);
}
inline void modify(int x, int y) {
cut(x);
for (int i = 0; i < m; ++i)
if (cnt[i & val[x]] & 1)
H[x][i] *= -1;
val[x] = y;
for (int i = 0; i < m; ++i)
if (cnt[i & val[x]] & 1)
H[x][i] *= -1;
link(x);
}
int main() {
n = rd(), m = rd();
inv[1] = cnt[1] = 1;
for (int i = 2; i < P; ++i) {
inv[i] = P - P / i * inv[P % i] % P;
cnt[i] = cnt[i >> 1] + (i & 1);
}
for (int i = 1; i <= n; ++i) {
val[i] = rd();
}
for (int i = 1; i < n; ++i) {
int x = rd(), y = rd();
G[x].push_back(y);
G[y].push_back(x);
}
dfs1(1, 0);
dfs2(1, 1);
build(1, 1, n);
q = rd();
while (q--) {
int op = get_op(), x = rd(), y = op == 2 ? rd() : 0;
if (op == 1) {
int sum = 0;
for (int i = 0; i < m; ++i)
sum = (sum + (cnt[i & x] & 1 ? P - 1 : 1) * ans[i]) % P;
sum = (sum * inv[m] % P + P) % P;
printf("%d\n", sum);
} else {
modify(x, y);
}
}
tmp.init();
query(1, 1, n, 1, n);
return 0;
}