首先，任何一个卡树剖的出题人都很没有素质
前言
2023 年 8 月 22 日，XDFnoip模拟赛场上，神犇 liuhangxin 自己发明了矩阵乘法维护FWT，可是出成绩的时候发现本题挂了30分。
2023 年 9 月 22 日，菜鸡 cool_milo 看到了 liuhangxin 的题解，但是由于太菜，并没有看懂。
2023 年 10 月 22 日，菜鸡 cool_milo 看到了 liuhangxin 的题解，但是由于太菜，并没有看懂。
2023 年 11 月 22 日，菜鸡 cool_milo 看到了 liuhangxin 的题解，但是由于太菜，并没有看懂。
2023 年 12 月 5 日，菜鸡 cool_milo 看到神仙 liuhangxin 讨论切树游戏那题，发现 liuhangxin 会 矩阵乘法维护FWT 而自己不会。
2023 年 12 月 6 日，菜鸡 cool_milo 最终还是学习了矩阵乘法维护FWT，并且在 300min 切掉此题。
一个月前我在 NOIp2023 的赛场上，散散沙。一个月后，我从倒下的地方爬起。
我成功了。我不再是以前的那个我了。
什么是全局平衡二叉树
顾名思义，是全局看来都很平衡的二叉树
我们参考树剖的思想，对原树进行轻重链剖分：
（图源oiwiki，下同）
我们思考树链剖分的劣势在哪里：树剖的过程和数据结构是割裂的，两个的复杂度是相乘的关系，所以就显得很没有必要。虽然 LCT 能够消除这一劣势，但是在没有Link和cut的时候就显得很多余我不想背这么多代码。
那我们可以试着魔改一下LCT，还是借用一条链一棵二叉树的方式建树，但是选择 整条链的带权重心作为根。每个点的权定义为它的 \(size\) 减去 它的重儿子的 \(size\) 。
而每一条轻边在树上体现为 二叉树的根 （注意不是轻子树的头）到重链上的一条单向边，和LCT类似，这条边满足“认父不认子”。
这样的好处是什么呢？：我们在这个“二叉树”上往父亲走一次，整个树的大小至少翻倍。因为这里每个点的 \(size\) 其实就是它管辖的那一段重链的长度加上重链的轻子树的大小之和。
感觉不太难理解吧？
先贴一个建树代码：
code
int Sbuild(int l, int r) {
if(l > r) return 0;
int sum = 0;
for(int i = l; i <= r; i++) {
sum += lsze[stk[i]];
}
for(int i = l, sum2 = lsze[stk[l]]; 1; i++, sum2 += lsze[stk[i]]) {
if(sum2 * 2 > sum) {
int rt = stk[i];
lc[rt] = Sbuild(l, i - 1);
rc[rt] = Sbuild(i + 1, r);
if(lc[rt]) {
fs[lc[rt]] = rt;
}
if(rc[rt]) {
fs[rc[rt]] = rt;
}
return rt;
}
}
return -114514;
}
int Build(int u) {
//build以u为根的重链
for(int i = u; i; i = son[i]) {
vis[i] = 1;
}
for(int i = u; i; i = son[i]) {
for(auto it:G[i]) {
if(!vis[it]) {
int rt = Build(it);
fs[rt] = i;
}
}
}
ptr = 0;
for(int i = u; i; i = son[i]) {
stk[++ptr] = i;
}
return Sbuild(1, ptr);
}
正题
把转移写成 \(dp\) 的形式，记 \(f_{u,k}\) 表示以 \(u\) 为根的联通块，异或得到的权值为 \(k\) 的方案数。
那么有：
\[f_{u,k} = \prod{(f_{son,i} + 0)} * {(v_u)}
\]
其中乘法定义为异或卷积，'t' 定义为给数组的第 \(t\) 位加上 \(1\) （表示不选）
那么容易把所有东西全部FWT起来，然后最后再FWT回去，就能做到 dp 一次 \(\Theta(nm)\) 。
然后需要动态修改。我们先定义每个点的 \(f_{u, k}\) 为 \(F(u)\)
首先我们需要对 \(F\) 求和对吧，那么我们重新定义一个 \(S\) 表示所有 \(u\) 子树内的 \(F\) 求和。这个是容易的。
然后我们需要把 dp 写成和重儿子有关的形式：我们记 \(Fl(u)\) 表示
\[\prod (F_{v \in son_u \land v \neq wson_u} + 0) * {(v_u)}
\]
记 \(Su(u)\) 表示
\[\sum S_{v \in son_u \land v \neq wson_u}
\]
这里 \(*\) 表示 FWT 乘法，注意这里所有的东西都被FWT了。
那么有
\[F_u = Fl_u * (F_{wson_u} + 0) = Fl_u + Fl_u * F_{wson_u} \\
S_u = Su_u + S_{son_u} + F_u = Su_u + S_{son_u} + Fl_u * F_{wson_u} + Fl_u
\]
写成矩阵形式：
\[\begin{bmatrix}
Fl_u & 0 & Fl_u\\
Fl_u & 1 & Su_u + S_{son_u} + Fl_u\\
0 & 0 & 1
\end{bmatrix}
*
\begin{bmatrix}
F_{wson} \\
S_{wson} \\
1
\end{bmatrix}
=
\begin{bmatrix}
F_{u} \\
S_{u} \\
1
\end{bmatrix}
\]
注意到：
\[\begin{bmatrix}
a_1 & 0 & b_1\\
c_1 & 1 & d_1\\
0 & 0 & 1
\end{bmatrix}
*
\begin{bmatrix}
a_2 & 0 & b_2\\
c_2 & 1 & d_2\\
0 & 0 & 1
\end{bmatrix}
=
\begin{bmatrix}
a_1a_2 & 0 & a_1b_2 + b_1\\
a_2c_1 + c_2 & 1 & c_1b_2 + d_1 + d_2\\
0 & 0 & 1
\end{bmatrix}
\]
那么我们只用维护四个FWT就行了，不需要写显示的矩阵乘法。
然后就完了。。。吗？
注意到撤销一个点的贡献的时候可能要除以0，所以\(Fl\) 需要维护成 \(a * 0^y\) 的形式，写的时候恶心++。
这下是真没了。
EOF.
code(7.3k)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P = 10007;
const int N = 3e4+5, M = 128;
template<typename T>inline void read(T &a)
{
a = 0;
int f = 1;
char c = getchar();
while(!isdigit(c))
{
if(c == '-') f = -1;
c = getchar();
}
while(isdigit(c))
a = a * 10 + c - 48,c = getchar();
a *= f;
}
template<typename T,typename ...L> inline void read(T &a,L &...l)
{
read(a),read(l...);
}
int inv[P];
typedef pair<int, int> pii;
inline pii Mul(pii A, pii B) {
return make_pair(A.first * B.first % P, A.second + B.second);
}
inline pii Div(pii A, pii B) {
return make_pair(A.first * inv[B.first] % P, A.second - B.second);
}
inline int Add(int a, int b) {
return a + b >= P ? a + b - P : a + b;
}
inline int Mul(int a, int b) {
return a * b % P;
}
inline void Inc(int &a, int b) {
a = Add(a, b);
}
inline int Sub(int a, int b) {
return a - b < 0 ? a - b + P : a - b;
}
inline int qmi(int a, int b) {
int ans = 1;
while(b) {
if(b & 1) {
ans = Mul(ans, a);
}
a = Mul(a, a);
b >>= 1;
}
return ans;
}
struct FWT {
int arr[M];
FWT() {
memset(arr, 0, sizeof arr);
}
FWT(int _k) {//kpos -> 1
memset(arr, 0, sizeof arr);
for(int i = 0; i < M; i++) {
if(__builtin_parity(i & _k)) {
arr[i] = P - 1;
}
else {
arr[i] = 1;
}
}
}
FWT operator + (const FWT &A) const {
FWT ans;
for(int i = 0; i < M; i++) {
ans.arr[i] = Add(arr[i], A.arr[i]);
}
return ans;
}
FWT operator * (const FWT &A) const {
FWT ans;
for(int i = 0; i < M; i++) {
ans.arr[i] = Mul(arr[i], A.arr[i]);
}
return ans;
}
FWT operator - (const FWT &A) const {
FWT ans;
for(int i = 0; i < M; i++) {
ans.arr[i] = Sub(arr[i], A.arr[i]);
}
return ans;
}
};
FWT fwt(FWT A, int op) {
for(int i = 1; i < M; i <<= 1) {//步长
for(int j = 0; j < M; j += (i << 1)) {
for(int k = 0; k < i; k++) {
int x = A.arr[j + k], y = A.arr[i + j + k];
A.arr[j + k] = Mul(Add(x, y), op);
A.arr[i + j + k] = Mul(Sub(x, y), op);
}
}
}
return A;
}
struct Matr {
FWT a, b, c, d;
Matr(FWT _a = FWT(), FWT _b = FWT(), FWT _c = FWT(), FWT _d = FWT()) {
a = _a, b = _b, c = _c, d = _d;
}
Matr operator * (const Matr &A) const{
return Matr(a * A.a, b + a * A.b, A.a * c + A.c, A.b * c + d + A.d);
}
};
vector<int> G[N];
int v[N], x, y, n, m, q;
char op[10];
namespace GlbBST {
FWT fl[N], Su[N];
Matr F[N], Fv[N];//F是乘积，Fv是单点的值
pii _0fl[N][M];
int son[N], sze[N], lc[N], rc[N], fs[N];//fs是GlbBst上的父亲
int stk[N], ptr, vis[N], lsze[N];
void DFS1(int u, int f) {
sze[u] = 1;
for(auto it:G[u]) {
if(it != f) {
DFS1(it, u);
sze[u] += sze[it];
if(sze[it] > sze[son[u]]) {
son[u] = it;
}
}
}
lsze[u] = sze[u] - sze[son[u]];
}
int Sbuild(int l, int r) {
if(l > r) return 0;
int sum = 0;
for(int i = l; i <= r; i++) {
sum += lsze[stk[i]];
}
for(int i = l, sum2 = lsze[stk[l]]; 1; i++, sum2 += lsze[stk[i]]) {
if(sum2 * 2 > sum) {
int rt = stk[i];
lc[rt] = Sbuild(l, i - 1);
rc[rt] = Sbuild(i + 1, r);
F[rt] = Fv[rt];
if(lc[rt]) {
F[rt] = F[lc[rt]] * F[rt];
fs[lc[rt]] = rt;
}
if(rc[rt]) {
F[rt] = F[rt] * F[rc[rt]];
fs[rc[rt]] = rt;
}
return rt;
}
}
return -114514;
}
int Build(int u) {
//build以u为根的重链
for(int i = u; i; i = son[i]) {
vis[i] = 1;
fl[i] = FWT(v[i]);
for(int j = 0; j < M; j++) {
_0fl[i][j] = make_pair(fl[i].arr[j], 0);//必然非0
}
}
for(int i = u; i; i = son[i]) {
for(auto it:G[i]) {
if(!vis[it]) {
int rt = Build(it);
fs[rt] = i;
Su[i] = Su[i] + F[rt].d;
FWT tmp = F[rt].b + FWT(0);
fl[i] = fl[i] * tmp;
for(int j = 0; j < M; j++) {
pii res;
if(tmp.arr[j]) {
res = make_pair(tmp.arr[j], 0);
}
else {
res = make_pair(1, 1);
}
_0fl[i][j] = Mul(_0fl[i][j], res);
}
}
}
}
ptr = 0;
for(int i = u; i; i = son[i]) {
Fv[i] = Matr(fl[i], fl[i], fl[i], fl[i] + Su[i]);
stk[++ptr] = i;
}
return Sbuild(1, ptr);
}
void modify(int x, int y) {
//x -> y;
int xx = x;
while(x) {
if(fs[x] && lc[fs[x]] != x && rc[fs[x]] != x) {
Su[fs[x]] = Su[fs[x]] - F[x].d;
FWT tmp = F[x].b + FWT(0);
for(int j = 0; j < M; j++) {
pii res;
if(tmp.arr[j]) {
res = make_pair(tmp.arr[j], 0);
}
else {
res = make_pair(1, 1);
}
_0fl[fs[x]][j] = Div(_0fl[fs[x]][j], res);
if(_0fl[fs[x]][j].second) {
fl[fs[x]].arr[j] = 0;
}
else {
fl[fs[x]].arr[j] = _0fl[fs[x]][j].first;
}
}
}
x = fs[x];
}
x = xx;
//撤回一个贡献
FWT ord = FWT(v[x]);
for(int j = 0; j < M; j++) {
if(ord.arr[j]) {
_0fl[x][j] = Div(_0fl[x][j], make_pair(ord.arr[j], 0));
}
else {
_0fl[x][j].second--;
}
}
v[x] = y;
ord = FWT(v[x]);
for(int j = 0; j < M; j++) {
if(ord.arr[j]) {
_0fl[x][j] = Mul(_0fl[x][j], make_pair(ord.arr[j], 0));
}
else {
_0fl[x][j].second++;
}
if(_0fl[x][j].second) {
fl[x].arr[j] = 0;
}
else {
fl[x].arr[j] = _0fl[x][j].first;
}
}
Fv[x] = Matr(fl[x], fl[x], fl[x], fl[x] + Su[x]);
while(x) {
F[x] = Fv[x];
if(lc[x]) {
F[x] = F[lc[x]] * F[x];
}
if(rc[x]) {
F[x] = F[x] * F[rc[x]];
}
if(fs[x] && lc[fs[x]] != x && rc[fs[x]] != x) {
//修改父节点的矩阵
Su[fs[x]] = Su[fs[x]] + F[x].d;
FWT tmp = F[x].b + FWT(0);
for(int j = 0; j < M; j++) {
pii res;
if(tmp.arr[j]) {
res = make_pair(tmp.arr[j], 0);
}
else {
res = make_pair(1, 1);
}
_0fl[fs[x]][j] = Mul(_0fl[fs[x]][j], res);
if(_0fl[fs[x]][j].second) {
fl[fs[x]].arr[j] = 0;
}
else {
fl[fs[x]].arr[j] = _0fl[fs[x]][j].first;
}
}
Fv[fs[x]] = Matr(fl[fs[x]], fl[fs[x]], fl[fs[x]], fl[fs[x]] + Su[fs[x]]);
}
x = fs[x];
}
}
}
int main() {
//freopen("1.in", "r", stdin);
for(int i = 1; i < P; i++) {
inv[i] = qmi(i, P - 2);
}
read(n, m);
for(int i = 1; i <= n; i++) {
read(v[i]);
}
for(int i = 1; i < n; i++) {
read(x, y);
G[x].emplace_back(y), G[y].emplace_back(x);
}
read(q);
GlbBST::DFS1(1, 0);
int root = GlbBST::Build(1);
// for(int i = 1; i <= n; i++) {
// cout<<i<<' '<<GlbBST::fs[i]<<endl;
// }
while(q--) {
scanf("%s", op);
if(op[0] == 'C') {
read(x, y);
GlbBST::modify(x, y);
}
else {
read(x);
FWT res = fwt(GlbBST::F[root].d, (P + 1) >> 1);
printf("%d\n", res.arr[x]);
}
}
}
//FWT是好东西——Sword_K
/*
[a1 0 b1] [a2 0 b2] [a1a2 0 b1+a1b2]
[c1 1 d1] * [c2 1 d2] = [a2c1+c2 1 b2c1+d1+d2]
[0 0 1] [0 0 1] [0 0 1]
*/
/*
start coding at:2023/12/6 10:32
finish debugging at:2023/12/6 15:14
stubid mistakes:枚举重儿子写出死循环，树剖it = f没有continue，传参传挂，轻子树的父亲设为自己，所有的FWT(0)都应该是FWT(1)，FWT一个数的结果不是1和0，撤销贡献的时候Su[fs[x]]写成Su[x]
*/
/*
吾日三省吾身：
你排序了吗？
你取模了吗？
你用%lld输出long long 了吗？
1LL<<x写对了吗？
判断=0用了abs()吗？
算组合数判了a<b吗？
线段树build()了吗？
.size()加了(signed)吗？
树链剖分的DFS序是在第二次更新的吗？
修改在询问前面吗？
线段树合并到叶子结点return了吗？
__builtin_ctz后面需要加ll吗？
*/