题解
把所有的数组一开始就FWT好然后再IFWT回去可以减小常数
从13s跑到0.7s……
可以参照immortalCO的论文，感受一下毒瘤的动态动态DP
就是用数据结构维护线性递推的矩阵的乘积
由于所有轻儿子\(F(z) + z^{0}\)的乘积做除法太麻烦，我们用一个线段树维护每个点所有的轻儿子即可
代码
#include <bits/stdc++.h>
#define enter putchar('\n')
#define space putchar(' ')
#define fi first
#define se second
#define MAXN 30005
//#define ivorysi
#define pii pair<int,int>
#define pb push_back
using namespace std;
typedef long long int64;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {putchar('-');x = -x;}
if(x >= 10) out(x / 10);
putchar('0' + x % 10);
}
const int MOD = 10007,Inv2 = 5004;
int mul(int a,int b) {
return a * b % MOD;
}
int inc(int a,int b) {
return a + b >= MOD ? a + b - MOD : a + b;
}
struct Enode {
int to,next;
}E[MAXN * 2];
int N,M,head[MAXN],sumE,val[MAXN],pos[MAXN];
int son[MAXN],siz[MAXN],fa[MAXN],dep[MAXN],top[MAXN];
int rt[MAXN],dfn[MAXN],L[MAXN],id[MAXN],Lcnt,idx;
void add(int u,int v) {
E[++sumE].to = v;
E[sumE].next = head[u];
head[u] = sumE;
}
struct Poly {
int p[128];
Poly() {memset(p,0,sizeof(p));}
friend void FWT(Poly &f) {
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 a0 = f.p[j + k],a1 = f.p[j + i + k];
f.p[j + k] = inc(a0,a1);
f.p[j + i + k] = inc(a0,MOD - a1);
}
}
}
}
friend void IFWT(Poly &f) {
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 a0 = f.p[j + k],a1 = f.p[j + i + k];
f.p[j + k] = mul(inc(a0,a1),Inv2);
f.p[j + i + k] = mul(inc(a0,MOD - a1),Inv2);
}
}
}
}
friend Poly operator * (Poly a,Poly b) {
Poly c;
for(int i = 0 ; i < M ; ++i) c.p[i] = mul(a.p[i],b.p[i]);
return c;
}
friend Poly operator + (const Poly &a,const Poly &b) {
Poly c;
for(int i = 0 ; i < M ; ++i) c.p[i] = inc(a.p[i],b.p[i]);
return c;
}
friend Poly operator - (const Poly &a,const Poly &b) {
Poly c;
for(int i = 0 ; i < M ; ++i) c.p[i] = inc(a.p[i],MOD - b.p[i]);
return c;
}
}F[MAXN],H[MAXN],one,LH[MAXN],LF[MAXN];
struct Matrix {
Poly a,b,c,d;
friend Matrix operator * (const Matrix &s,const Matrix &t) {
Matrix r;
r.a = s.a * t.a;
r.b = s.b + s.a * t.b;
r.c = s.c * t.a + t.c;
r.d = s.c * t.b + s.d + t.d;
return r;
}
};
struct node {
int lc,rc,L,R;
Matrix m;
}tr[MAXN * 5];
int Ncnt;
vector<Poly> Tr[MAXN];
vector<int> Lson;
void update(int u) {
tr[u].m = tr[tr[u].rc].m * tr[tr[u].lc].m;
}
void build(int &u,int l,int r){
u = ++Ncnt;
tr[u].L = l;tr[u].R = r;
if(l == r) {
int k = L[r];
Poly t;t.p[val[k]] = 1;FWT(t);
tr[u].m.a = tr[u].m.b = tr[u].m.c = LF[k] * t;
tr[u].m.d = LH[k] + tr[u].m.a;
return ;
}
int mid = (l + r) >> 1;
build(tr[u].lc,l,mid);
build(tr[u].rc,mid + 1,r);
update(u);
}
void buildLt(int id,int u,int l,int r) {
if(l == r) {
int k = Lson[l - 1];
Tr[id][u] = F[k] + one;
pos[k] = u;
return;
}
int mid = (l + r) >> 1;
buildLt(id,u << 1,l,mid);
buildLt(id,u << 1 | 1,mid + 1,r);
Tr[id][u] = Tr[id][u << 1] * Tr[id][u << 1 | 1];
}
void CalcAgain(int u,int pos,int k) {
if(tr[u].L == tr[u].R) {
Poly t;t.p[val[k]] = 1;FWT(t);
tr[u].m.a = tr[u].m.b = tr[u].m.c = LF[k] * t;
tr[u].m.d = tr[u].m.a + LH[k];
return ;
}
int mid = (tr[u].L + tr[u].R) >> 1;
if(pos <= mid) CalcAgain(tr[u].lc,pos,k);
else CalcAgain(tr[u].rc,pos,k);
update(u);
}
void Change(int u) {
while(u) {
CalcAgain(rt[id[u]],dfn[u],u);
u = top[u];
if(fa[u]) {
F[u] = tr[rt[id[u]]].m.c;
LH[fa[u]] = LH[fa[u]] - H[u] + tr[rt[id[u]]].m.d;
H[u] = tr[rt[id[u]]].m.d;
int t = pos[u];Tr[fa[u]][t] = F[u] + one;t >>= 1;
while(t) {
Tr[fa[u]][t] = Tr[fa[u]][t << 1] * Tr[fa[u]][t << 1 | 1];
t >>= 1;
}
LF[fa[u]] = Tr[fa[u]][1];
}
u = fa[u];
}
}
void dfs1(int u) {
siz[u] = 1;dep[u] = dep[fa[u]] + 1;
F[u].p[val[u]] = 1;FWT(F[u]);
for(int i = head[u] ; i ; i = E[i].next) {
int v = E[i].to;
if(v != fa[u]) {
fa[v] = u;
dfs1(v);
F[u] = F[u] * (F[v] + one);
H[u] = H[u] + H[v];
siz[u] += siz[v];
if(siz[v] > siz[son[u]]) son[u] = v;
}
}
H[u] = H[u] + F[u];
}
void dfs2(int u) {
LF[u] = one;
Lson.clear();
for(int i = head[u] ; i ; i = E[i].next) {
int v = E[i].to;
if(v != fa[u] && v != son[u]) {
Lson.pb(v);
LF[u] = LF[u] * (F[v] + one);
LH[u] = LH[u] + H[v];
}
}
if(Lson.size()) {
Tr[u].resize(Lson.size() * 4 + 5);
buildLt(u,1,1,Lson.size());
}
if(!top[u]) {top[u] = u;++Lcnt;idx = 0;}
L[++idx] = u;id[u] = Lcnt;dfn[u] = idx;
if(son[u]) {
top[son[u]] = top[u];
dfs2(son[u]);
}
else {
build(rt[Lcnt],1,idx);
return;
}
for(int i = head[u] ; i ; i = E[i].next) {
int v = E[i].to;
if(v != fa[u] && v != son[u]) {
dfs2(v);
}
}
}
void Init() {
read(N);read(M);
for(int i = 1 ; i <= N ; ++i) read(val[i]);
int u,v;
for(int i = 1 ; i < N ; ++i) {
read(u);read(v);add(u,v);add(v,u);
}
one.p[0] = 1;
FWT(one);
dfs1(1);dfs2(1);
}
void Solve() {
int Q;char op[25];int x,y;
read(Q);
for(int i = 1 ; i <= Q ; ++i) {
scanf("%s",op + 1);
read(x);
if(op[1] == 'Q') {
Poly t = tr[rt[id[1]]].m.d;IFWT(t);
out(t.p[x]);enter;
}
else {
read(y);
val[x] = y;Change(x);
}
}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Init();
Solve();
return 0;
}