还是loj的机子快啊。。。
普通的DP不难想到，设F[i][zt]为带上根玩出zt的方案数，G[i][zt]为子树中的方案数，后面是可以用FWT优化的
主要是复习了下动态DP
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
const int _=1e2;
const int maxn=3e4+_;
const int fbin=maxn<<;
const int maxm=+;
const int mod=1e4+;
inline int ad(int x,int y){return (x>=mod-y)?(x-mod+y):x+y;}
inline int re(int x,int y){return (x<y)?(x-y+mod):x-y;}
inline int read()
{
int x=; char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch)){x=x*+ch-'';ch=getchar();}
return x;
}
inline void write(int d)
{
if(d>=)write(d/);
putchar(d%+'');
}
int m; struct poly
{
int a[maxm];
poly(){}
void FWT(int op)
{
for(int i=;i<m;i<<=)
for(int j=;j<m;j+=(i<<))
for(int k=;k<i;k++)
{
int a1=a[j+k],a2=a[j+k+i];
a[j+k]=ad(a1,a2);
a[j+k+i]=re(a1,a2);
if(op==-)
{
a[j+k]=a[j+k]*(mod/+)%mod;
a[j+k+i]=a[j+k+i]*(mod/+)%mod;
}
}
}
poly(int x){memset(a,,sizeof(a));a[x]=;FWT();} friend poly operator +(poly u,poly v){for(int i=;i<m;i++)u.a[i]=ad(u.a[i],v.a[i]); return u;}
friend poly operator -(poly u,poly v){for(int i=;i<m;i++)u.a[i]=re(u.a[i],v.a[i]); return u;}
friend poly operator *(poly u,poly v){for(int i=;i<m;i++)u.a[i]=u.a[i]*v.a[i]%mod; return u;}
}o;
struct Matrix
{
poly a,b,c,d;
Matrix(){}
Matrix(poly f,poly g){a=b=c=f;d=f+g;}
Matrix(poly A,poly B,poly C,poly D){a=A,b=B,c=C,d=D;}
friend Matrix operator +(Matrix u,Matrix v){return Matrix(u.a*v.a,u.a*v.b+u.b,u.c*v.a+v.c,u.c*v.b+u.d+v.d);}
}; //----------------------------------------def------------------------------------------------------------ namespace FASEG//每个点的每个孩子的F+1
{
struct trnode
{
int lc,rc;poly p;
}tr[*maxn];int trlen,rt[maxn];
void update(int now)
{
int lc=tr[now].lc,rc=tr[now].rc;
if(lc&&rc)tr[now].p=tr[lc].p*tr[rc].p;
else if(lc)tr[now].p=tr[lc].p;
else if(rc)tr[now].p=tr[rc].p;
}
void insert(int &now,int l,int r,int p,poly u)
{
if(now==)now=++trlen;
if(l==r){tr[now].p=u;return ;}
int mid=(l+r)/;
if(p<=mid)insert(tr[now].lc,l,mid,p,u);
else insert(tr[now].rc,mid+,r,p,u);
update(now);
}
}
namespace LINESEG//第i个位置放的是i的重儿子转移到i的转移矩阵
{
#define lc (now<<1)
#define rc (now<<1|1)
#define mid ((ql+qr)/2) Matrix tr[fbin];
void update(int now){tr[now]=tr[rc]+tr[lc];}
void change(int now,int ql,int qr,int p,Matrix m)
{
if(ql==qr){tr[now]=m;return ;}
if(p<=mid)change(lc,ql,mid,p,m);
else change(rc,mid+,qr,p,m);
update(now);
}
Matrix getmatrix(int now,int ql,int qr,int l,int r)
{
if(ql==l&&qr==r)return tr[now];
if(r<=mid) return getmatrix(lc,ql,mid,l,r);
else if(mid+<=l)return getmatrix(rc,mid+,qr,l,r);
else return getmatrix(rc,mid+,qr,mid+,r)+getmatrix(lc,ql,mid,l,mid);
} #undef lc
#undef rc
#undef mid
} //---------------------------------------data struct---------------------------------------------------- int n;
struct node
{
int x,y,next;
}a[*maxn];int len,last[maxn];
void ins(int x,int y)
{
len++;
a[len].x=x;a[len].y=y;
a[len].next=last[x];last[x]=len;
}
int fa[maxn],son[maxn],tot[maxn],dep[maxn];
void pre_tree_node(int x)
{
tot[x]=;
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(y!=fa[x])
{
fa[y]=x;
dep[y]=dep[x]+;
pre_tree_node(y);
if(son[x]==||tot[son[x]]<tot[y])son[x]=y;
tot[x]+=tot[y];
}
}
}
int z,ys[maxn],top[maxn],bot[maxn];
void pre_tree_edge(int x,int tp)
{
ys[x]=++z;top[x]=tp;
if(son[x]!=)pre_tree_edge(son[x],tp),bot[x]=bot[son[x]];
else bot[x]=x;
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(y!=fa[x]&&y!=son[x])
pre_tree_edge(y,y);
}
} //-------------------------------------------cop---------------------------------------------------- int w[maxn],cnt[maxn],wch[maxn];//有多少轻孩子，爸爸的第几个轻孩子
poly F[maxn],G[maxn],g[maxn];//包括x的方案数，总方案数，只有轻儿子的总方案数
void treeDP(int x)
{
F[x]=poly(w[x]);
cnt[x]=;
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(fa[x]!=y)
{
treeDP(y);
F[x]=F[x]*(F[y]+o);
G[x]=G[x]+G[y];
if(son[x]!=y)
{
wch[y]=++cnt[x];
g[x]=g[x]+G[y];
}
}
}
G[x]=G[x]+F[x]; using namespace FASEG;
insert(rt[x],,cnt[x],,poly(w[x]));
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(fa[x]!=y&&son[x]!=y)
insert(rt[x],,cnt[x],wch[y],F[y]+o);
}
} //-------------------------------------------pre------------------------------------------------ void query(int zt)
{
poly u=G[];u.FWT(-);
write(u.a[zt]),putchar('\n');
}
Matrix ma;
void change(int x,int zt)
{
w[x]=zt;
using namespace FASEG;
insert(rt[x],,cnt[x],,poly(w[x])); int tx=top[x];
while(x!=)
{
LINESEG::change(,,n,ys[x],Matrix(tr[rt[x]].p,g[x]));
if(fa[tx]!=)
{
ma=LINESEG::getmatrix(,,n,ys[tx],ys[bot[tx]]);
insert(rt[fa[tx]],,cnt[fa[tx]],wch[tx],ma.c+o);
g[fa[tx]]=g[fa[tx]]-G[tx];
G[tx]=ma.d;
g[fa[tx]]=g[fa[tx]]+G[tx];
}
else G[tx]=LINESEG::getmatrix(,,n,ys[tx],ys[bot[tx]]).d;
x=fa[tx];tx=top[x];
}
} char ss[];
int main()
{
freopen("xor.in","r",stdin);
freopen("xor.out","w",stdout);
int x,y;
n=read(),m=read();
for(int i=;i<=n;i++)w[i]=read();
for(int i=;i<n;i++)
{
x=read(),y=read();
ins(x,y),ins(y,x);
}
pre_tree_node();
z=,pre_tree_edge(,);
for(int i=;i<m;i++)o.a[i]=;
treeDP();
for(int i=;i<=n;i++)
LINESEG::change(,,n,ys[i],Matrix(FASEG::tr[FASEG::rt[i]].p,g[i])); int Q;
Q=read();
while(Q--)
{
char ch=getchar();
while(ch!='C'&&ch!='Q')ch=getchar();
bool bk=ch=='C';
while(ch!='e'&&ch!='y')ch=getchar();
if(!bk)
x=read(),query(x);
else
{
x=read(),y=read(),change(x,y); /* poly u=LINESEG::getmatrix(1,1,n,ys[1],ys[bot[1]]).d;
u.FWT(-1);
for(int i=0;i<=3;i++)
printf("%d ",u.a[i]);
puts(""); */
}
} return ;
}