动态DP小记
command_block
2020-06-08 14:43:37
最近你可能在本`Blog`看到许多这样的小记,这完全属于省选之前的游击战术,内容不保证严谨,也不保证大多数人能看懂。
如果省选过后有时间我会来仔细更新并且把这些文字去掉的。
------------
- [P4719 【模板】"动态 DP"&动态树分治](https://www.luogu.com.cn/problem/P4719)
首先要得到一个朴素的`DP`算法。
设 $f[u][0]$ 为不选 $u$ 的最佳答案, $f[u][1]$ 为选 $u$ 的最佳答案。
设 $v$ 为 $u$ 的直接儿子,则有转移:
$f[u][0]=\max_v\max(f[v][0],f[v][1])$
$f[u][1]=w[u]+\max_vf[v][0]$
然后按照套路把树剖了,对每条重链维护这些`DP`值。
设 $g$ 为其子树中轻儿子的`DP`值,也就是说只缺重儿子。
那么,一条重链的转移是 :
$f[i][0]=\max(f[i+1][0],f[i+1][1])+g[i][0]$
$f[i][1]=f[i+1][0]+g[i][1]$
做完一条重链之后,会产生对重链顶的父亲的 $g$ 的一次修改,这是平凡的。
然后这些东西可以大力讨论来转移,但是太麻烦了,而且可能产生不友好的细节。
这里有一个技巧 : 把`DP`的转移写成满足结合律的矩阵乘法的形式,可以大大简化讨论。
这里是最优化问题,我们选择 `Folyd` 矩阵,即 $\{max,+\}$ 矩阵,不难验证其具有结合律。
乘法是这样的 :
$$C[i][j]=\max_kA[i][k]+B[k][j]$$
假如我们对于 $g[i]$ 构造的矩阵为 $B$ ,而 $f[i]$ 的向量为 $C$ , $f[i+1]$ 的向量为 $A$。
我们需要满足 $C=B*A$
展开一下 : $\begin{cases}C[0]=\max(B[0][0]+A[0],B[0][1]+A[1])\\C[1]=\max(B[1][0]+A[0],B[1][1]+A[1])\end{cases}$
结合上面的转移式,不难推出转移矩阵为 $\begin{bmatrix}g[i][0]&g[i][0]\\g[i][1]&-\inf\end{bmatrix}$。
现在就是要支持修改一个矩阵,并维护所有矩阵的连乘积。
由于矩阵乘法具有结合律,使用线段树维护即可。复杂度 $O(n\log^2n)$。
某条重链顶的`DP`值,即为重链矩阵乘积的 $a,c$ 且 $f[u][0]=a,f[u][1]=c$ ,原因请读者自己思考。
```cpp
#include<algorithm>
#include<vector>
#include<cstdio>
#define MaxN 105000
using namespace std;
inline int read(){
int X=0;char ch=0,w=0;
while(ch<48||ch>57)ch=getchar(),w|=(ch=='-');
while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
return w?-X:X;
}
vector<int> g[MaxN];
struct Node
{int f,tf,son,siz,dep,ed;}b[MaxN];
void pfs1(int u)
{
b[u].siz=1;
for (int i=0,v;i<g[u].size();i++)
if (!b[v=g[u][i]].siz){
b[v].dep=b[b[v].f=u].dep+1;
pfs1(v);
b[u].siz+=b[v].siz;
if (b[v].siz>b[b[u].son].siz)
b[u].son=v;
}
}
int id[MaxN],tp[MaxN],tim,
f[MaxN][2],lf[MaxN][2],mp[MaxN];
void pfs2(int u,int tf)
{
b[tp[id[u]=++tim]=u].tf=tf;
if (!b[u].son){
f[u][1]=lf[u][1]=mp[u];
b[u].ed=u;
return ;
}pfs2(b[u].son,tf);
int v;
for (int i=0;i<g[u].size();i++){
if (!b[v=g[u][i]].tf){
pfs2(v,v);
lf[u][0]+=max(f[v][0],f[v][1]);
lf[u][1]+=f[v][0];
}
}lf[u][1]+=mp[u];
v=b[u].son;
f[u][0]=lf[u][0]+max(f[v][0],f[v][1]);
f[u][1]=lf[u][1]+f[v][0];
b[u].ed=b[v].ed;
}
#define INF 100000000
struct Matrix
{
int a[2][2];
Matrix operator * (const Matrix &B) const{
Matrix S;
S.a[0][0]=max(a[0][0]+B.a[0][0],a[0][1]+B.a[1][0]);
S.a[0][1]=max(a[0][0]+B.a[0][1],a[0][1]+B.a[1][1]);
S.a[1][0]=max(a[1][0]+B.a[0][0],a[1][1]+B.a[1][0]);
S.a[1][1]=max(a[1][0]+B.a[0][1],a[1][1]+B.a[1][1]);
return S;
}
}a[MaxN<<2];
inline void up(int u)
{a[u]=a[u<<1]*a[u<<1|1];}
int n;
void build(int l=1,int r=n,int u=1)
{
if (l==r){
a[u].a[0][0]=lf[tp[l]][0];
a[u].a[0][1]=lf[tp[l]][0];
a[u].a[1][0]=lf[tp[l]][1];
a[u].a[1][1]=-INF;
return ;
}int mid=(l+r)>>1;
build(l,mid,u<<1);
build(mid+1,r,u<<1|1);
up(u);
}
int to;
void chg(int l=1,int r=n,int u=1)
{
if (l==r){
a[u].a[0][0]=lf[tp[l]][0];
a[u].a[0][1]=lf[tp[l]][0];
a[u].a[1][0]=lf[tp[l]][1];
return ;
}int mid=(l+r)>>1;
if (to<=mid)chg(l,mid,u<<1);
else chg(mid+1,r,u<<1|1);
up(u);
}
int wfl,wfr;
Matrix qry(int l=1,int r=n,int u=1)
{
if (wfl<=l&&r<=wfr)return a[u];
int mid=(l+r)>>1;
if (wfl<=mid&&wfr>mid)
return qry(l,mid,u<<1)*qry(mid+1,r,u<<1|1);
return wfl<=mid ? qry(l,mid,u<<1) : qry(mid+1,r,u<<1|1);
}
void pathop(int u,int c)
{
lf[u][1]+=c-mp[u];mp[u]=c;
Matrix s;
while(1){
to=id[u];chg();
wfl=id[u=b[u].tf];wfr=id[b[u].ed];
s=qry();
if (u==1)break;
lf[b[u].f][1]+=s.a[0][0]-f[u][0];
lf[b[u].f][0]+=max(s.a[0][0],s.a[1][0])-max(f[u][0],f[u][1]);
f[u][0]=s.a[0][0];f[u][1]=s.a[1][0];
u=b[u].f;
}printf("%d\n",max(s.a[0][0],s.a[1][0]));
}
int m;
int main()
{
n=read();m=read();
for (int i=1;i<=n;i++)mp[i]=read();
for (int i=1,f,t;i<n;i++){
f=read();t=read();
g[f].push_back(t);
g[t].push_back(f);
}b[1].dep=1;pfs1(1);pfs2(1,1);
build();
for (int i=1,u,c;i<=m;i++){
u=read();c=read();
pathop(u,c);
}return 0;
}
```
- [P4751 【模板】"动态DP"&动态树分治（加强版）](https://www.luogu.com.cn/problem/P4751)
当然,也可以使用全局平衡二叉树来维护,这样复杂度是 $O(n\log n)$ 的。
```cpp
```
- [P6021 洪水](https://www.luogu.com.cn/problem/P6021)
设 $f[u]$ 为防卫 $u$ 的子树的最小代价。
朴素 `DP` 有 : $f[u]=\min(w[u],\sum\limits_{v\in son[u]}f[v])$
树剖一下,记 $lf[u]$ 为 $u$ 轻儿子的 $f$ 和。
方程变为 $f[u]=\min(w[u],f[u+1]+lf[u])$
把转移写成 `Folyd` 矩阵的形式可得 :
$\begin{bmatrix}f[u]\\0\end{bmatrix}=\begin{bmatrix}lf[u]&w[u]\\\inf&0\end{bmatrix}*\begin{bmatrix}f[u+1]\\0\end{bmatrix}$
注意到 $\begin{bmatrix}a_1&b_1\\\inf&0\end{bmatrix}*\begin{bmatrix}a_2&b_2\\\inf&0\end{bmatrix}=\begin{bmatrix}a_1+a_2&\min(b_1,a_1+b_2)\\\inf&0\end{bmatrix}$
这样我们就只需要维护两个变量了。
一个子树的`DP`值为根到所在重链底端的矩阵乘积。
注意需要`long long`。
```cpp
#include<algorithm>
#include<vector>
#include<cstdio>
#define ll long long
#define MaxN 205000
using namespace std;
inline char readc(){
char ch=0;
while(ch!='Q'&&ch!='C')ch=getchar();
return ch;
}
inline int read(){
int X=0;char ch=0;
while(ch<48||ch>57)ch=getchar();
while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
return X;
}
vector<int> g[MaxN];
struct Node
{int f,tf,son,siz,dep,ed;}b[MaxN];
void pfs1(int u)
{
b[u].siz=1;
for (int i=0,v;i<g[u].size();i++)
if (!b[v=g[u][i]].siz){
b[v].dep=b[b[v].f=u].dep+1;
pfs1(v);
b[u].siz+=b[v].siz;
if (b[v].siz>b[b[u].son].siz)
b[u].son=v;
}
}
int id[MaxN],tp[MaxN],tim;
ll f[MaxN],lf[MaxN],mp[MaxN];
void pfs2(int u,int tf)
{
b[tp[id[u]=++tim]=u].tf=tf;
if (!b[u].son){
f[b[u].ed=u]=mp[u];
return ;
}pfs2(b[u].son,tf);
int v;
for (int i=0;i<g[u].size();i++){
if (!b[v=g[u][i]].tf){
pfs2(v,v);
lf[u]+=f[v];
}
}v=b[u].son;
f[u]=min(lf[u]+f[v],mp[u]);
b[u].ed=b[v].ed;
}
#define INF (1ll<<60)
struct Matrix
{
ll a,b;
Matrix operator * (const Matrix &B) const
{return (Matrix){a+B.a,min(b,a+B.b)};}
}a[MaxN<<2];
inline void up(int u)
{a[u]=a[u<<1]*a[u<<1|1];}
int n;
void build(int l=1,int r=n,int u=1)
{
if (l==r){
a[u].a=lf[tp[l]];
a[u].b=mp[tp[l]];
return ;
}int mid=(l+r)>>1;
build(l,mid,u<<1);
build(mid+1,r,u<<1|1);
up(u);
}
int to;
void chg(int l=1,int r=n,int u=1)
{
if (l==r){
a[u].a=lf[tp[l]];
a[u].b=mp[tp[l]];
return ;
}int mid=(l+r)>>1;
if (to<=mid)chg(l,mid,u<<1);
else chg(mid+1,r,u<<1|1);
up(u);
}
int wfl,wfr;
Matrix qry(int l=1,int r=n,int u=1)
{
if (wfl<=l&&r<=wfr)return a[u];
int mid=(l+r)>>1;
if (wfl<=mid&&wfr>mid)
return qry(l,mid,u<<1)*qry(mid+1,r,u<<1|1);
return wfl<=mid ? qry(l,mid,u<<1) : qry(mid+1,r,u<<1|1);
}
void pathop(int u,int c)
{
mp[u]+=c;
while(1){
to=id[u];chg();
u=b[u].tf;
if (u==1)break;
wfl=id[u];wfr=id[b[u].ed];
Matrix s=qry();
lf[b[u].f]-=f[u];
lf[b[u].f]+=(f[u]=s.b);
u=b[u].f;
}
}
int m;
int main()
{
n=read();
for (int i=1;i<=n;i++)mp[i]=read();
for (int i=1,f,t;i<n;i++){
f=read();t=read();
g[f].push_back(t);
g[t].push_back(f);
}b[1].dep=1;pfs1(1);pfs2(1,1);
build();m=read();
for (int i=1,u;i<=m;i++)
if (readc()=='Q'){
wfl=id[u=read()];wfr=id[b[u].ed];
Matrix s=qry();
printf("%lld\n",s.b);
}else {
u=read();
pathop(u,read());
}
return 0;
}
```
- [P5024 保卫王国](https://www.luogu.com.cn/problem/P5024)
首先有最小点覆盖=全集-最大独立集。
那么就可以直接套用前面模板题的做法,不选就是把权值置为 $\inf$ ,选就是 $-\inf$。
但是此题的询问之间互不影响,所以没必要动用带修链分治结构,只需要倍增就够了。
预处理从某个点向上跳 $2^i$ 的转移矩阵连乘积,然后我们就能把某个点被钦定的`DP`值快速向祖先转移。
若 $a$ 是 $b$ 的祖先,直接将 $b$ 倍增到 $a$ 的直接儿子,然后从原来的 $a$ 中挖掉旧贡献,加入新贡献,再次倍增到根。
若 $a,b$ 无祖先关系,则都倍增至 $lca(a,b)$ 的直接儿子,然后仍然是挖和补,再次倍增到根。
其实本质就是在虚树上`DP`,所以说扩展到 $k$ 个点一样能做 (
写起来似乎比直接剖还要长,细节也不少……唯一的好处是(表面上)考察的都是noip级算法。
```cpp
#include<algorithm>
#include<vector>
#include<cstdio>
#define ll long long
#define INF (1ll<<60)
#define MaxN 105000
using namespace std;
inline int read(){
int X=0;char ch=0;
while(ch<48||ch>57)ch=getchar();
while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
return X;
}
vector<int> g[MaxN];
struct Matrix
{
ll a[2][2];
void Init(ll c1,ll c2){
a[0][0]=a[0][1]=c1;
a[1][0]=c2;a[1][1]=-INF;
}
void I(){
a[0][1]=a[1][0]=-INF;
a[0][0]=a[1][1]=0;
}
Matrix operator * (const Matrix &B) const{
Matrix S;
S.a[0][0]=max(a[0][0]+B.a[0][0],a[0][1]+B.a[1][0]);
S.a[0][1]=max(a[0][0]+B.a[0][1],a[0][1]+B.a[1][1]);
S.a[1][0]=max(a[1][0]+B.a[0][0],a[1][1]+B.a[1][0]);
S.a[1][1]=max(a[1][0]+B.a[0][1],a[1][1]+B.a[1][1]);
return S;
}
}c[18][MaxN];
ll sum,dp[MaxN][2],mp[MaxN];
int f[18][MaxN],dep[MaxN];
void dfs(int u)
{
dp[u][1]=mp[u];
for (int i=0,v;i<g[u].size();i++)
if (!dep[v=g[u][i]]){
dep[v]=dep[u]+1;
dfs(v);
dp[u][0]+=max(dp[v][0],dp[v][1]);
dp[u][1]+=dp[v][0];
}
for (int i=0,v;i<g[u].size();i++)
if (dep[v=g[u][i]]>dep[u]){
f[0][v]=u;
c[0][v].Init(
dp[u][0]-max(dp[v][0],dp[v][1]),
dp[u][1]-dp[v][0]
);
}
}
int lca(int x,int y)
{
int k=17;
if (dep[x]>dep[y])swap(x,y);
while(k--)
while(dep[f[k][y]]>=dep[x])
y=f[k][y];
if (x==y)return x;
k=17;
while(k--)
while(f[k][x]!=f[k][y])
{x=f[k][x];y=f[k][y];}
return f[0][x];
}
int getc(int u,int v,Matrix &S)
{
int k=17;S.I();
while(k--)
while(dep[f[k][u]]>dep[v])
{S=c[k][u]*S;u=f[k][u];}
return u;
}
void solve()
{
int a=read(),x=read()^1,b=read(),y=read()^1,
t=lca(a,b);
ll s0,s1,st0,st1;Matrix S;
if (dep[a]>dep[b]){swap(a,b);swap(x,y);}
if (t==a){
int tc=getc(b,a,S);
st0=S.a[0][y]+dp[b][y];
st1=S.a[1][y]+dp[b][y];
if (x){
s1=dp[a][1]-dp[tc][0]+st0;
s0=-INF;
}else {
s0=dp[a][0]-max(dp[tc][0],dp[tc][1])
+max(st0,st1);
s1=-INF;
}
}else {
int ta=getc(a,t,S);
st0=S.a[0][x]+dp[a][x];
st1=S.a[1][x]+dp[a][x];
s0=dp[t][0]-max(dp[ta][0],dp[ta][1])+max(st0,st1);
s1=dp[t][1]-dp[ta][0]+st0;
int tb=getc(b,t,S);
st0=S.a[0][y]+dp[b][y];
st1=S.a[1][y]+dp[b][y];
s0=s0-max(dp[tb][0],dp[tb][1])+max(st0,st1);
s1=s1-dp[tb][0]+st0;
}getc(t,0,S);
ll ans=max(
max(S.a[0][0],S.a[1][0])+s0,
max(S.a[0][1],S.a[1][1])+s1
);printf("%lld\n", ans<0 ? -1 : sum-ans);
}
int n,m;char typ[10];
int main()
{
n=read();m=read();scanf("%s",typ);
for (int i=1;i<=n;i++)
sum+=(mp[i]=read());
for (int i=1,f,t;i<n;i++){
f=read();t=read();
g[f].push_back(t);
g[t].push_back(f);
}dep[1]=1;dfs(1);
for (int j=1;j<17;j++)
for (int i=1;i<=n;i++){
f[j][i]=f[j-1][f[j-1][i]];
c[j][i]=c[j-1][f[j-1][i]]*c[j-1][i];
}
for (int i=1;i<=m;i++)solve();
return 0;
}
```
- [P3781 [SDOI2017]切树游戏](https://www.luogu.com.cn/problem/P3781)
**题意** : 给出一棵 $n$ 个点的树,有点权,均在 $[0,m)$ 内。
要求资瓷如下两种操作:
- 修改某个点的点权。
- 查询有多少个非空连通块,其点权异或和恰为 $k$。答案对 $10007$ 取模。
$n,q\leq 30000,m\leq 128$ ,修改不超过 $10^4$ 个,时限$\texttt{3s}$。
------------
先不考虑修改,可以把每个点当成一个集合幂级数 : $1+x^w$
然后对“每个非空连通块幂级数的异或卷积”求和,即可得到答案。
首先跑一个`DWT`变成点值,然后对每一位点值,就变成了如下问题 :
对“每个非空连通块幂级数的点值乘积”求和。
设 $f[u]$ 为 $u$ 子树内必选 $u$ 的答案,这样,每个连通块会在其最浅点被统计到。
假设子树 $v$ 转移到 $u$ ,可以选择不乘,也可以选择乘,能得到这样的转移 :
$f[u]\leftarrow f[u]f[v]+f[v]$
最后 $\sum\limits_{i=1}^nf[i]$ 即为答案。
暴力`DP`一次是 $O(nm)$ 的,无法通过。
考虑动态 `DP` ,把树剖了。
对于一条重链,设 $lf[i]$ 为该点的轻儿子`DP`值(+1)乘积。
注意到不可能每次求和来统计答案,所以我们还要额外记 $s[i]$ 表示子树内 $f[i]$ 的和, $ls[i]$ 为轻儿子的 $f$ 和。
那么可以写出转移 :
$f[i]=(f[i+1]+1)lf[i]=f[i+1]lf[i]+lf[i]$
$s[i]=s[i+1]+f[i]+ls[i]=s[i+1]+ls[i]+f[i+1]lf[i]+lf[i]$
然后我们来手玩一下怎么用 $lf[i],ls[i]$ 拼成一个合适的转移矩阵,假设为 $B$。
若 $f[i],s[i]$ 的向量为 $C$ , $f[i+1],s[i+1]$ 的向量为 $B$。
我们需要满足 $C=B*A$.
注意到转移式中有许多系数为 $1$ 的转移, $2\times 2$ 的矩阵可能无法满足需求,我们使用 $3\times 3$ 的。
使用待定系数法或者直接考虑递推式的含义不难写出:
$\begin{bmatrix}f[i]\\s[i]\\1\end{bmatrix}=\begin{bmatrix}lf[i]&0&lf[i]\\lf[i]&1&ls[i]+lf[i]\\0&0&1\end{bmatrix}*\begin{bmatrix}f[i+1]\\s[i+1]\\1\end{bmatrix}$
然后按照套路使用线段树维护即可。
这样的常数是 $3^3=27$ ,较大。事实上,由于矩阵比较特殊,可以进一步减小常数 :
$\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&b_1+a_1b_2\\c_1a_2+c_2&1&c_1b_2+d_1+d_2\\0&0&1\end{bmatrix}$
也就是说我们实际上只需要维护 $4$ 个数。
实际转移是 :
$\begin{cases}a_3=a_1a_2\\b_3=b_1+a_1b_2\\c_3=c_1a_2+c_2\\d_3=c_1b_2+d_1+d_2\end{cases}$
这样就把常数大大减小了。
但是注意,每条重链处理完毕时,需要对父亲的轻边信息进行单点修改。
此时会对 $lf$ 产生一个除法操作,然而在膜意义下可能没有逆元。
一种方法是给轻儿子也开线段树维护树的连乘积,另一种办法是记录膜意义下的 $0$ 有多少个。
一开始听说记录 $0$ 更好写,可是个人感觉细节有点多,而且不便于封装(这是最大的麻烦),所以还是选择写多一棵线段树来维护轻儿子,顺便以备将来贡献无法撤销时使用。
我们对于并行的 $m$ 组点值都采用上述操作,最终做一次暴力 $IDWT$ 就能得到答案。
最终复杂度是 $O(nm+qm(\log^2n+\log m))$。
Loj可过,但是由于某些毒瘤在洛谷上加了卡树剖的数据,并不能通过。
```cpp
#include<algorithm>
#include<vector>
#include<cstdio>
#define MaxN 30500
#define MaxM 130
using namespace std;
const int mod=10007;
int m,invm;
void FWT(int *f)
{
for (int l=1;l<m;l<<=1)
for (int p=0;p<m;p+=l+l)
for (int k=p;k<p+l;k++){
int s0=f[k];
f[k]+=f[k+l];
f[k+l]=s0-f[k+l];
}
for (int i=0;i<m;i++)f[i]=(f[i]+mod*mod)%mod;
}
void IFWT(int *f)
{FWT(f);for (int i=0;i<m;i++)f[i]=f[i]*invm%mod;}
inline int pm0(int x)
{return x<0 ? x+mod : x;}
inline int pm1(int x)
{return x>=mod ? x-mod : x;}
struct Data{
int a[MaxM];
void clear()
{for (int i=0;i<m;i++)a[i]=0;}
inline Data operator + (const Data &B) const
{Data C;for (int i=0;i<m;i++)C.a[i]=pm1(a[i]+B.a[i]);return C;}
inline Data operator - (const Data &B) const
{Data C;for (int i=0;i<m;i++)C.a[i]=pm0(a[i]-B.a[i]);return C;}
inline Data operator * (const Data &B) const
{Data C;for (int i=0;i<m;i++)C.a[i]=a[i]*B.a[i]%mod;return C;}
}one;
struct Matrix{
Data a,b,c,d;
inline Matrix operator * (const Matrix &B) const
{return (Matrix){a*B.a,b+a*B.b,c*B.a+B.c,c*B.b+d+B.d};}
};
int to,wfl,wfr;
template <class Type>
class SGT {
public:
Type a[MaxN<<2],wfc,s[MaxN];
int lim,id[MaxN],tim;
inline void up(int u){a[u]=a[u<<1]*a[u<<1|1];}
void build(int l,int r,int u=1)
{
if (l==r){a[u]=s[l];return ;}
int mid=(l+r)>>1;
build(l,mid,u<<1);
build(mid+1,r,u<<1|1);
up(u);
}
void chg(int l,int r,int u=1)
{
if (l==r){a[u]=wfc;return ;}
int mid=(l+r)>>1;
if (to<=mid)chg(l,mid,u<<1);
else chg(mid+1,r,u<<1|1);
up(u);
}
Type qry(int l,int r,int u=1)
{
if (wfl<=l&&r<=wfr)return a[u];
int mid=(l+r)>>1;
if (wfl<=mid&&wfr>mid)
return qry(l,mid,u<<1)*qry(mid+1,r,u<<1|1);
return wfl<=mid ? qry(l,mid,u<<1) : qry(mid+1,r,u<<1|1);
}
};
SGT<Matrix> T;
SGT<Data> L;
vector<int> g[MaxN];
struct Node
{int f,tf,son,siz,dep,ed,tl,tr;}b[MaxN];
void pfs1(int u)
{
b[u].siz=1;
for (int i=0,v;i<g[u].size();i++)
if (!b[v=g[u][i]].siz){
b[v].dep=b[b[v].f=u].dep+1;
pfs1(v);
b[u].siz+=b[v].siz;
if (b[v].siz>b[b[u].son].siz)
b[u].son=v;
}
}
Data f[MaxN],lf[MaxN],s[MaxN],ls[MaxN],sp[MaxN];
int mp[MaxN];
void pfs2(int u,int tf)
{
b[u].tf=tf;
T.id[u]=++T.tim;
sp[u].a[mp[u]]=1;FWT(sp[u].a);lf[u]=sp[u];
if (!b[u].son){f[u]=s[u]=sp[u];b[u].ed=u;return ;}
pfs2(b[u].son,tf);
int v;
for (int i=0;i<g[u].size();i++)
if (!b[v=g[u][i]].tf)
pfs2(v,v);
b[u].tl=L.tim+1;
for (int i=0;i<g[u].size();i++){
if ((v=g[u][i])!=b[u].f&&v!=b[u].son){
L.id[v]=++L.tim;
ls[u]=ls[u]+s[v];
lf[u]=lf[u]*f[v]+lf[u];
}
}b[u].tr=L.tim;
v=b[u].son;
f[u]=lf[u]*f[v]+lf[u];
s[u]=ls[u]+s[v]+f[u];
b[u].ed=b[v].ed;
}
Data ans;
void pathop(int u,int c)
{
sp[u].clear();
sp[u].a[mp[u]=c]=1;FWT(sp[u].a);
wfl=b[u].tl;wfr=b[u].tr;
if (0<wfl&&wfl<=wfr)lf[u]=sp[u]*L.qry(1,L.tim);
else lf[u]=sp[u];
Matrix S;
while(1){
to=T.id[u];
T.wfc=(Matrix){lf[u],lf[u],lf[u],ls[u]+lf[u]};
T.chg(1,T.tim);
wfl=T.id[u=b[u].tf];wfr=T.id[b[u].ed];
S=T.qry(1,T.tim);
if (u==1)break;
ls[b[u].f]=ls[b[u].f]-s[u]+S.d;s[u]=S.d;
to=L.id[u];L.wfc=S.b+one;
L.chg(1,L.tim);
wfl=b[b[u].f].tl;wfr=b[b[u].f].tr;
lf[b[u].f]=sp[b[u].f]*L.qry(1,L.tim);
u=b[u].f;
}ans=S.d;IFWT(ans.a);
}
void Init()
{
for (int i=1;i<mod;i++)
if (m*i%mod==1){invm=i;break;}
for (int i=0;i<m;i++)one.a[i]=1;
}
int n,q;char op[10];
int main()
{
scanf("%d%d",&n,&m);Init();
for (int i=1;i<=n;i++)scanf("%d",&mp[i]);
for (int i=1,f,t;i<n;i++){
scanf("%d%d",&f,&t);
g[f].push_back(t);
g[t].push_back(f);
}b[1].dep=1;pfs1(1);pfs2(1,1);
for (int i=1;i<=n;i++)
T.s[T.id[i]]=(Matrix){lf[i],lf[i],lf[i],ls[i]+lf[i]};
T.build(1,T.tim);
for (int i=1;i<=n;i++)
if (L.id[i])
L.s[L.id[i]]=f[i]+one;
if (L.tim)L.build(1,L.tim);
ans=s[1];IFWT(ans.a);
scanf("%d",&q);
for (int i=1,u,c;i<=q;i++){
scanf("%s",op);
if (op[0]=='Q'){
scanf("%d",&c);
printf("%d\n",ans.a[c]);
}else {
scanf("%d%d",&u,&c);
pathop(u,c);
}
}return 0;
}
```