还是打上转载吧，毕竟很多都是shadowice1984的东西，只是我用了我看得懂的语言（外星语言？）解释了一遍。ZFY：震惊，机房猴子不会普通话
前言
这道题目真的难！！！才紫的！！！
参考文献
总体框架：https://www.luogu.com.cn/blog/ShadowassIIXVIIIIV/solution-p3781
看懂DDP那一块的东西：https://blog.csdn.net/weixin_30258901/article/details/99187239
例题
术语
(u.lightson)，(u)的轻儿子。(u.heavyson)，(u)的重儿子。
思路
老老实实抄袭了，这个题解我是真的佛了。
朴素DP
设(dp_{i,j})表示最高点为(i)异或和为(j)的联通块个数。
那么如果询问为(k)的话我们最后求的就是：(sumlimits_{i=1}^ndp_{i,k})
推转移方程：
考虑现在往(dp_{u,k})加入子树(dp_{v})
(dp_{u,k}+=sumlimits_{i⊕j==k}dp_{u,i}dp_{v,j})
后面的不就是异或卷积吗？FWT套上。
然后我们设(Dp_{i})为(dp_{i})经过FWT摧残变换后的数组。（注意，基本上后面的值都是FWT向量了。）
所以就是：(Dp_{u,k}=Dp_{u,k}Dp_{v,k}+Dp_{u,k})。
就是：
(Dp_{u,k}*=(Dp_{v,k}+1))
DDP加速
然后我们假如设（这里的(1)表示的是全部位置都是(1)的一个数组，(F,f)也是个数组）：
(F_{u}=prodlimits_{v∈u.son}(F_{u}+1))
(f_{u}=prodlimits_{v∈u.lightson}(F_{u}+1))
其实这里的(F)就是上面的(Dp)数组，简写。
再设(G)数组表示一个节点子树内的答案，(g)表示一个节点轻儿子内的答案
(g_{x}=sumlimits_{y∈x.lightson}G_{y})
怎么转移呢？
(y=x.heavyson)
(F_{x}=f_{x}*(F_{y}+1))
(G_{x}=g_{x}+F_{x}+G_{y})
拆开就是：
(F_{x}=f_{x}+f_{x}*F_{x})
(G_{x}=g_{x}+f_{x}*F_{y}+f_{x}+G_{y})
写成矩阵就是：
(egin{bmatrix}F_{y} & G_{y} & 1end{bmatrix}*egin{bmatrix}f_{x} & f_{x} & 0 \ 0 & 1 & 0\ f_{x} & f_{x}+g_{x} & 1end{bmatrix}=egin{bmatrix}F_{x} & G_{x} & 1end{bmatrix})
但是这个矩阵特别难维护。
怎么搞？
奆佬猫神给了我们一个神仙的维护方法：
(egin{bmatrix}a & b & 0 \ 0 & 1 & 0\ c & d & 1end{bmatrix}*egin{bmatrix}A & B & 0 \ 0 & 1 & 0\ C & D & 1end{bmatrix}=egin{bmatrix}aA & aB+b & 0 \ 0 & 1 & 0\ cA+C & cB+d+D & 1end{bmatrix})
维护四个向量就可以啦！！！
当然也许有人会问单位矩阵是什么，又没有改变矩阵乘法的方式，不就是：(a=1,b=c=d=0)。
细节
关于修改是如何逆回去的
这里有模运算，可以大量的逆元乘法，但是也是因为模运算，导致有可能乘的是0，出现了乘(0)除(0)的情况，那么我们就只能坐以待毙了吗，其实不然，在维护(f)的时候，我们可以顺带记录乘了多少个(0)，实现不可实现的除以(0)的操作。
点值都去哪了？
这里解释一下，点值直接在(FWT)之后，直接赋给了(f)，自己看看就会发现不是很影响。
矩阵的答案以及如何从轻儿子的矩阵抠东西下来
我们知道了一个矩阵，我们又要怎么把他的答案抠下来？
其实就是乘一个(egin{bmatrix}0 & 0 & 1end{bmatrix})就全部抠下来了。
轻儿子你也可以看作乘了(egin{bmatrix}0 & 0 & 1end{bmatrix})再抠。
代码
时间复杂度：(O(mqlog{n}))
#include<cstdio>
#include<cstring>
#define N 31000
#define NN 61000
#define M 140
#define mod 10007
using namespace std;
int inv[N];
int lim,n;
struct node
{
int y,next;
}tr[NN];int last[N],len;
inline void inz(int x,int y){len++;tr[len].y=y;tr[len].next=last[x];last[x]=len;}
inline void fwt(int *a,const int& o)
{
for(register int i=2;i<=lim;i<<=1)
{
int mid=(i>>1);
for(register int j=0;j<lim;j+=i)
{
for(register int k=0;k<mid;k++)
{
int x=a[j+k],y=a[j+k+mid];
a[j+k]=(x+y)*o%mod;a[j+k+mid]=(x-y+mod)*o%mod;//当初为了减轻常数抄了题解
}
}
}
}//FWT
struct poly
{
int a[M];
inline int& operator[](const int& x){return a[x];}
}we[N],one,L2;
inline int pdz(int x){return x>mod?x-mod:x;}
inline int pdf(int x){return x<0?x+mod:x;}
inline poly operator*(poly x,poly y){for(register int i=0;i<lim;i++)L2[i]=(x[i]*y[i])%mod;return L2;}
inline poly operator+(poly x,poly y){for(register int i=0;i<lim;i++)L2[i]=pdz(x[i]+y[i]);return L2;}
inline poly operator-(poly x,poly y){for(register int i=0;i<lim;i++)L2[i]=pdf(x[i]-y[i]);return L2;}
inline poly operator/(poly x,poly y){for(register int i=0;i<lim;i++)L2[i]=L2[i]*(inv[y[i]])%mod;return L2;}
inline void operator+=(poly &x,poly y){for(register int i=0;i<lim;i++)x[i]=pdz(x[i]+y[i]);}
inline void operator-=(poly &x,poly y){for(register int i=0;i<lim;i++)x[i]=pdf(x[i]-y[i]);}
inline void operator*=(poly &x,poly y){for(register int i=0;i<lim;i++)x[i]=(x[i]*y[i])%mod;}
inline void operator/=(poly &x,poly y){for(register int i=0;i<lim;i++)x[i]=x[i]*(inv[y[i]])%mod;}
struct Mar
{
poly a[2][2];
poly* operator[](const int& x){return a[x];}
}L1;//矩阵
inline Mar operator*(Mar a,Mar b)
{
L1[0][0]=a[0][0]*b[0][0];
L1[0][1]=a[0][0]*b[0][1]+a[0][1];
L1[1][0]=a[1][0]*b[0][0]+b[1][0];
L1[1][1]=a[1][0]*b[0][1]+a[1][1]+b[1][1];
return L1;
}
struct data//维护f的工具。
{
int fz[M];//有多少个0
int fv[M];//除了0以外的乘积，没有默认为1
inline void wt(const int x,const int k){if(k==0)fz[x]=fv[x]=1;else fz[x]=0,fv[x]=k;} //初始化所用到的函数
inline void operator*=(poly y){for(int i=0;i<lim;i++)y[i]%mod==0?fz[i]+=1:fv[i]=(fv[i]*y[i])%mod;}
inline void operator/=(poly y){for(int i=0;i<lim;i++)y[i]%mod==0?fz[i]-=1:fv[i]=(fv[i]*inv[y[i]])%mod;}
};
inline void cpy(poly &x,const data y){for(int i=0;i<lim;i++)x[i]=(!y.fz[i])?y.fv[i]:0;}//将f复制到矩阵上面的一个向量上
struct Tree
{
int son[N][2],h[N],size[N],fa[N];
data lt[N];/*f*/poly lh[N];/*g*/
Mar val[N]/*BST上所管理的值*/,w[N]/*自身的值*/;
bool v[N];//用来建全局平衡二叉树的
inline void update(const int x){val[x]=val[son[x][0]]*w[x]*val[son[x][1]];}//维护
inline void ins(const int x,const int y){lt[x]*=(val[y][1][0]+one);lh[x]+=val[y][1][1];}//将一个点插入到x中
inline void del(const int x,const int y){lt[x]/=(val[y][1][0]+one);lh[x]-=val[y][1][1];}//将一个点删除出x
inline bool pd(const int x){return son[fa[x]][0]!=x && son[fa[x]][1]!=x;}//判断是不是真正的二组
inline void pu(const int x){cpy(w[x][0][0],lt[x]);w[x][0][1]=w[x][1][0]=w[x][0][0];w[x][1][1]=lh[x]+w[x][0][0];}//将一个点的f,g打到矩阵上面去
int sta[N],top;
int root;poly ans;
int bt(int l,int r)
{
if(l>r)return 0;
int sum=0;
for(register int i=l;i<=r;i++)sum+=size[sta[i]];
int now=size[sta[l]];
for(register int i=l;i<=r;i++,now+=size[sta[i]])
{
int x=sta[i];
if(now*2>=sum)
{
int ls=bt(i+1,r),rs=bt(l,i-1);fa[ls]=fa[rs]=x;
son[x][0]=ls;son[x][1]=rs;
update(x);
return x;
}
}
}
int sbuild(int x)
{
for(register int i=x;i;i=h[i])v[i]=1;
for(register int i=x;i;i=h[i])
{
for(int k=last[i];k;k=tr[k].next)
{
int y=tr[k].y;
if(!v[y])
{
int z=sbuild(y);fa[z]=i;
ins(i,z);
}
}
}
top=0;for(register int i=x;i;i=h[i])pu(i),sta[++top]=i,size[i]-=size[h[i]];
return bt(1,top);
}
void dfs(int x,const int fa)
{
size[x]=1;
for(register int k=last[x];k;k=tr[k].next)
{
int y=tr[k].y;
if(fa!=y)
{
dfs(y,x);
size[x]+=size[y];
if(size[y]>size[h[x]])h[x]=y;
}
}
}
//建树部分
inline void modify(int x,int k)
{
lt[x]/=we[x];
for(register int i=0;i<lim;i++)we[x][i]=0;we[x][k]=1;
fwt(we[x].a,1);
lt[x]*=we[x];pu(x);
//先删后加
for(register int i=x;i;i=fa[i])
{
if(pd(i) && fa[i]){del(fa[i],i);update(i);ins(fa[i],i);pu(fa[i]);}
else update(i);
}//沿着重链或者轻链慢慢往上跳
}
inline void getans()
{
ans=val[root][1][1];//答案
fwt(ans.a,5004);
}
}T;
int main()
{
inv[1]=1;for(register int i=2;i<mod;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;//线性推逆元
scanf("%d%d",&n,&lim);
for(register int i=0;i<lim;i++)one[i]=1;
for(register int i=1;i<=n;i++){int x;scanf("%d",&x);we[i][x]=1;fwt(we[i].a,1);}
for(register int i=1;i<n;i++)
{
int x,y;scanf("%d%d",&x,&y);
inz(x,y);inz(y,x);
}
T.w[0][0][0]=T.val[0][0][0]=one;//处理成单位矩阵
for(int i=1;i<=n;i++)for(int j=0;j<lim;j++)T.lt[i].wt(j,we[i][j]);//预处理
T.dfs(1,0);T.root=T.sbuild(1);T.getans();
int q;scanf("%d",&q);
for(register int i=1;i<=q;i++)
{
register char opt[10];scanf("%s",opt);
if(opt[0]=='Q')
{
int t;scanf("%d",&t);
printf("%d
",T.ans[t]);
}
else {int x,k;scanf("%d%d",&x,&k);T.modify(x,k);T.getans();}
}
return 0;
}