题目
题目描述
小 Q 是一个热爱学习的人，他经常去维基百科学习计算机科学。
就在刚才，小 Q 认真地学习了一系列位运算符，其中按位异或的运算符 $\oplus$ 对他影响很大。按位异或的运算符是双目运算符。按位异或具有交换律，即$i\oplus j=j\oplus i$ 。
他发现，按位异或可以理解成被运算的数字的二进制位对应位如果相同，则结果的该位置为 $0$，否则为 $1$，例如：$1(01)\oplus 2(10)=3(11)$。
他还发现，按位异或可以理解成参与运算的数字的每个二进制位都进行了不进位的加法，例如：$3(11)\oplus 3(11)=0(00)$。
现在小 Q 有一棵 $n$ 个结点的无根树 $T$，结点依次编号为 $1$ 到 $n$，其中结点 $i$ 的权值为 $v_i$。 定义一棵树的价值为它所有点的权值的异或和，一棵树 $T$ 的连通子树就是它的一个连通子图，并且这个图也是一棵树。 小 Q 想要在这棵树上玩切树游戏，他会不断做以下两种操作：
Change x y，将编号为 $x$ 的结点的权值修改为 $y$。Query k，询问有多少棵 $T$ 的非空连通子树，满足其价值恰好为$k$ 。
小 Q 非常喜（bu）欢（hui）数学，他希望你能快速回答他的问题，你能写个程序帮帮他吗？
输入格式
第一行包含两个正整数 $n$，$m$，分别表示结点的个数以及权值的上限。 第二行包含 $n$ 个非负整数 $v_1,v_2,…v_n$，分别表示每个结点一开始的权值。 接下来 $n-1$ 行，每行包含两个正整数$a_i$ ，$b_i$，表示有一条连接 $a_i$ 和 $b_i$ 的无向树边。 接下来一行包含一个正整数 $q$，表示小 Q 操作的次数。 接下来 $q$ 行每行依次表示每个操作。
输出格式
输出若干行，每行一个整数，依次回答每个询问。因为答案可能很大，所以请对 $10007$ 取模输出。
样例
样例输入
4 4
2 0 1 3
1 2
1 3
1 4
12
Query 0
Query 1
Query 2
Query 3
Change 1 0
Change 2 1
Change 3 3
Change 4 1
Query 0
Query 1
Query 2
Query 3
样例输出
3
3
2
3
2
4
2
3
数据范围与提示
对于 $100\%$ 的数据，$1\le a_i,b_i,x\le n$，$0\le v_i,y,k< m$，修改操作不超过 $10000$ 个。
| 测试点编号 | $n$ | $m$ | $q$ | 约定 |
|---|---|---|---|---|
| 1 ~ 4 | $\le 2000$ | $=64$ | $\le 64$ | 不存在修改操作 |
| 5 ~ 8 | $\le 30000$ | $=8$ | $\le 30000$ | $a_i=i$，$b_i=i+1$ |
| 9 ~ 10 | $\le 30000$ | $=128$ | $\le 30000$ | $a_i=i$，$b_i=i+1$ |
| 11 ~ 15 | $\le 30000$ | $=4$ | $\le 30000$ | 无 |
| 16 ~ 20 | $\le 30000$ | $=128$ | $\le 30000$ | 无 |
题解
没有修改操作的话就是一个简单的树上$dp$，设$f_{i,j}$表示以$i$为根权值为$j$的子树个数，有方程$f_{i,j}=\sum_{k=0}^{m}f_{i,k}\times f_{son_i,j\oplus k}$，可以用$FWT$优化到$O(nm\log n)$，如果直接用点值表达式进行运算复杂度降至$O(nm)$，下面全部为点值表达式的运算
有修改操作的话考虑动态$dp$，设$lf(x)$表示光计算轻儿子$x$点的答案，$lg(x)$表示$x$轻儿子子树中$f$的和
$lf(u)=x^{val_u}\prod_{v\in lightson_u}(f(v)+1),lg(u)=lf(u)+\sum_{v\in lightson_u}g(v)$
再计算重链$t$，有递推式：
$f_{t_i}(x)=lf_{t_i}(x)f_{t_{i+1}}(x)+lf_{t_i}(x)$
$g_{t_i}(x)=lg_{t_i}(x)+f_{t_i}(x)+g_{t_{i+1}}(x)=lf_{t_i}(x)f_{t_{i+1}}(x)+lf_{t_i}(x)+lg_{t_i}(x)+g_{t_{i+1}}(x)$
这样可以用矩阵优化转移
$(f_{c_{i+1}},g_{c_{i+1}},1){ \left( \begin{matrix} x^{v_{c_i}}LF_{c_i} & x^{v_{c_i}}LF_{c_i} & 0 \ 0 & 1 & 0 \ x^{v_{c_i}}LF_{c_i} & x^{v_{c_i}}LF_{c_i}+LG_{c_i} & 1 \ \end{matrix} \right )}=(f_{c_i},g_{c_i},1)$
因为矩阵中$0$很多所以可以手动推一下：
$\begin{pmatrix} a_1 & b_1 & 0 \ 0 & 1 & 0 \ c_1 & d_1 & 1 \end{pmatrix} \times \begin{pmatrix} a_2 & b_2 & 0 \ 0 & 1 & 0 \ c_2 & d_2 & 1 \end{pmatrix} = \begin{pmatrix} a_1 a_2 & b_1 + a_1 b_2 & 0 \ 0 & 1 & 0 \ a_2 c_1 + c_2 & b_2 c_1 + d_1 + d_2 & 1 \end{pmatrix}$
直接抄过来了
所以只用维护$a,b,c,d$四个值就好了
修改操作的时候需要除法操作，可能会有除以$0$的情况，新定义变量记录$0$的个数即可
luogu怎么还有人卡树剖呢gs
代码
// luogu-judger-enable-o2
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define tl (k<<1)
# define tr (k<<1|1)
# define mid (l+r>>1)
using namespace std;
const int MAX=3e4+5,N=129,inv2=5004;
const short mod=10007;
struct p{
short x,y;
short val() {return y?0:x;}
};
struct q{
p a[N];
}a[MAX],b[MAX],Val[MAX],f[2][MAX];
struct o{
q a,b,c,d;
}s[MAX<<2],F[MAX];
struct u{
int x,y;
}c[MAX<<1];
int n,m,num,cnt,Q;
short inv[MAX];
int val[MAX],id[MAX],re[MAX],h[MAX],fa[MAX],siz[MAX],son[MAX],top[MAX],d[MAX],qwq[MAX];
char S[10];
p operator+ (p a,p b) {return (p){(a.val()+b.val())%mod,0};}
p operator- (p a,p b) {return (p){(a.val()-b.val()+mod)%mod,0};}
p operator* (p a,p b) {return b.val()?(a.x=1ll*a.x*b.val()%mod,a):(++a.y,a);}
p operator/ (p a,p b) {return b.val()?(a.x=1ll*a.x*inv[b.val()]%mod,a):(--a.y,a);}
q operator+ (q a,q b) {for(int i=0;i<m;a.a[i]=a.a[i]+b.a[i],++i);return a;}
q operator- (q a,q b) {for(int i=0;i<m;a.a[i]=a.a[i]-b.a[i],++i);return a;}
q operator* (q a,q b) {for(int i=0;i<m;a.a[i]=a.a[i]*b.a[i],++i);return a;}
q operator/ (q a,q b) {for(int i=0;i<m;a.a[i]=a.a[i]/b.a[i],++i);return a;}
o operator* (o a,o b)
{
o c;
for(int i=0;i<m;++i)
{
c.a.a[i]=a.a.a[i]*b.a.a[i];
c.b.a[i]=a.a.a[i]*b.b.a[i]+a.b.a[i];
c.c.a[i]=a.c.a[i]*b.a.a[i]+b.c.a[i];
c.d.a[i]=a.d.a[i]+b.d.a[i]+a.c.a[i]*b.b.a[i];
}
return c;
}
p operator* (p a,int b) {return a.x=1ll*a.x*b%mod,a;}
short Pow(short a,short b)
{
int ans=1;
for(;b;b>>=1,a=1ll*a*a%mod)
if(b&1) ans=1ll*ans*a%mod;
return ans;
}
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
void add(int x,int y)
{
c[++num]=(u){h[x],y},h[x]=num;
c[++num]=(u){h[y],x},h[y]=num;
}
void FWT(q &A,short tt=1)
{
for(int i=1;i<m;i<<=1)
for(int l=i<<1,j=0;j<m;j+=l)
for(int k=0;k<i;++k)
{
p x=A.a[j+k],y=A.a[i+j+k];
A.a[j+k]=x+y,A.a[i+j+k]=x-y;
if(tt==-1) A.a[j+k]=A.a[j+k]*inv2,A.a[i+j+k]=A.a[i+j+k]*inv2;
}
}
void dfs(int x=1,int F=0)
{
fa[x]=F,d[x]=d[F]+(siz[x]=1),f[0][x]=Val[val[x]];
for(int i=h[x];i;i=c[i].x)
if(c[i].y^F)
{
dfs(c[i].y,x),siz[x]+=siz[c[i].y];
for(int j=0;j<m;++j)
f[0][x].a[j]=f[0][x].a[j]*(Val[0].a[j]+f[0][c[i].y].a[j]),f[1][x].a[j]=f[1][x].a[j]+f[1][c[i].y].a[j];
if(siz[c[i].y]>siz[son[x]]) son[x]=c[i].y;
}
for(int i=0;i<m;++i)
f[1][x].a[i]=f[1][x].a[i]+f[0][x].a[i];
}
void dfs1(int x=1,int tp=1)
{
top[x]=tp,re[id[x]=++cnt]=x;
if(!son[x]) return void(qwq[tp]=id[x]);
dfs1(son[x],tp);
for(int i=h[x];i;i=c[i].x)
if((c[i].y^fa[x])&&(c[i].y^son[x])) dfs1(c[i].y,c[i].y);
}
void build(int l=1,int r=n,int k=1)
{
if(l==r)
{
q f_=Val[val[re[l]]],g_=Val[m];
for(int i=h[re[l]];i;i=c[i].x)
if((c[i].y^fa[re[l]])&&(c[i].y^son[re[l]])) for(int j=0;j<m;++j)
f_.a[j]=f_.a[j]*(Val[0].a[j]+f[0][c[i].y].a[j]),g_.a[j]=g_.a[j]+f[1][c[i].y].a[j];
for(int i=0;i<m;++i)
g_.a[i]=g_.a[i]+f_.a[i];
return void(F[l]=s[k]=(o){f_,f_,f_,g_});
}
build(l,mid,tl),build(mid+1,r,tr),s[k]=s[tr]*s[tl];
}
void change(int l,int r,int k,int x)
{
if(l==r) return void(s[k]=F[l]);
if(x<=mid) change(l,mid,tl,x);
else change(mid+1,r,tr,x);
s[k]=s[tr]*s[tl];
}
o ask(int l,int r,int k,int L,int R)
{
if(l==L&&r==R) return s[k];
if(R<=mid) return ask(l,mid,tl,L,R);
if(L>mid) return ask(mid+1,r,tr,L,R);
return ask(mid+1,r,tr,mid+1,R)*ask(l,mid,tl,L,mid);
}
o ask(int x) {return ask(1,n,1,id[top[x]],qwq[top[x]]);}
void Upt(int x,int d)
{
q f=F[id[x]].a,g=F[id[x]].d;
for(int i=0;i<m;++i)
g.a[i]=g.a[i]-f.a[i],g.a[i]=g.a[i]+(f.a[i]=f.a[i]/Val[val[x]].a[i]*Val[d].a[i]);
F[id[x]]=(o){f,f,f,g},val[x]=d;
while(x)
{
o A=ask(x),B;
change(1,n,1,id[x]),B=ask(x),x=fa[top[x]];
if(x)
{
f=F[id[x]].a,g=F[id[x]].d;
for(int i=0;i<m;++i)
g.a[i]=g.a[i]-f.a[i],g.a[i]=g.a[i]-A.d.a[i]+B.d.a[i]+(f.a[i]=f.a[i]/(A.c.a[i]+Val[0].a[i])*(B.c.a[i]+Val[0].a[i]));
F[id[x]]=(o){f,f,f,g};
}
}
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;++i)
val[i]=read();
for(int i=1;i<n;++i)
add(read(),read());
for(short i=1;i<mod;++i)
inv[i]=Pow(i,mod-2);
for(int i=0;i<=m;++i)
Val[i].a[i]=(p){1,0},FWT(Val[i]);
dfs(),dfs1(),build(),Q=read();
for(int i=1,d;i<=Q;++i)
{
scanf("%s",S),d=read();
if(S[0]=='Q')
{
q ans=ask(1).d;
FWT(ans,-1);
printf("%d\n",ans.a[d].val());
}
else if(S[0]=='C') Upt(d,read());
}
return 0;
}
