动态DP小记

command_block · 2020-06-08 14:43:37 · 个人记录

最近你可能在本Blog看到许多这样的小记,这完全属于省选之前的游击战术,内容不保证严谨,也不保证大多数人能看懂。

如果省选过后有时间我会来仔细更新并且把这些文字去掉的。

P4719 【模板】"动态 DP"&动态树分治

首先要得到一个朴素的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 ,原因请读者自己思考。

#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"&动态树分治（加强版）

当然,也可以使用全局平衡二叉树来维护,这样复杂度是 O(n\log n) 的。

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。

#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 保卫王国

首先有最小点覆盖=全集-最大独立集。

那么就可以直接套用前面模板题的做法,不选就是把权值置为 \inf ,选就是 -\inf。

但是此题的询问之间互不影响,所以没必要动用带修链分治结构,只需要倍增就够了。

预处理从某个点向上跳 2^i 的转移矩阵连乘积,然后我们就能把某个点被钦定的DP值快速向祖先转移。

若 a 是 b 的祖先,直接将 b 倍增到 a 的直接儿子,然后从原来的 a 中挖掉旧贡献,加入新贡献,再次倍增到根。

若 a,b 无祖先关系,则都倍增至 lca(a,b) 的直接儿子,然后仍然是挖和补,再次倍增到根。

其实本质就是在虚树上DP,所以说扩展到 k 个点一样能做 (

写起来似乎比直接剖还要长,细节也不少……唯一的好处是(表面上)考察的都是noip级算法。

#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]切树游戏

题意 : 给出一棵 n 个点的树,有点权,均在 [0,m) 内。

要求资瓷如下两种操作:

修改某个点的点权。
查询有多少个非空连通块,其点权异或和恰为 k。答案对 10007 取模。

------------ 先不考虑修改,可以把每个点当成一个集合幂级数 : $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可过,但是由于某些毒瘤在洛谷上加了卡树剖的数据,并不能通过。

#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;
}