noone___'s blog
0%

动态dp

发表于 更新于 分类于
动态dp的例题，部分参考猫老师的PPT

序列上动态 $dp$

引入-普通的序列上动态 $dp$

已知长度 $n$ 的序列 $A$ ，$q$ 组询问中每次给定 $L,R$ ，求 $\max_{L\leq l\leq r\leq R} \sum_{i=l}^r a_i$

注：这是 $\text{WC2018}$ 猫锟的课件例题

可以用线段树 $(O(N+Q\log N))$ ，猫树 $O(N\log N+Q)$ ， 拓展 $\text{Tarjan}$ 离线 $(O(N+Q\log N))$ ，分块 $(O(N+Q\sqrt N))$ ，论文 $O(N+Q)$ 求出 $M_RM_{R-1}…M_{L+1}$ 的值，并乘 $\begin{bmatrix}A_L \\ 0\end{bmatrix}$ 求出答案

这不是重点

对于序列 $a$ 上操作，有如下的贪心算法：

记录 $cur,ans$ ，有转移：

重新定义矩阵运算，乘法改为加法，加法改为取 $\max$ ：

谔谔谔，注意 $mat_{1,2}$ 这个讨论了之前的 $cur,ans$ 都 $<a_i$ 的情况，一般来说重新定义的矩阵乘法中能处理该问题，但再输出答案时需要对此进行取 $\max$

至此，最大子区间和中每一位的转移可以以矩阵的形式被表示，单点修改对应单个矩阵的修改

可能有人发现矩阵的式子和猫老师的不太一样，原因是wtcl，按猫老师的式子写不出来＞﹏＜

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
const int INF=2147483647>>2;
const int N=5e4+100,M=3;
int a[N],n,m;

struct Matrix{
    int mat[M][M];
    Matrix(){ memset(mat,0,sizeof mat);}
    inline void clear(int x){ for(rei i=0;i<n;++i) mat[i][x]=0;}
    inline void debug(){ for(rei i=0;i<M;++i) for(rei j=0;j<M;++j) printf("%d%c",mat[i][j],j==M-1 ? 10 : 32);}
    inline void init(int l){
        mat[0][0]=mat[0][2]=mat[1][0]=mat[1][2]=a[l];
        mat[0][1]=mat[2][0]=mat[2][1]=-INF;
        mat[1][1]=mat[2][2]=0;
    }
    inline void change(int val){ mat[0][0]=mat[0][2]=mat[1][0]=mat[1][2]=val;}
    friend Matrix operator *(const Matrix a,const Matrix b){
        Matrix c;
        for(rei i=0;i<M;++i) for(rei j=0;j<M;++j) c.mat[i][j]=-INF;
        for(rei i=0;i<M;++i) for(rei j=0;j<M;++j) for(rei k=0;k<M;++k)
            c.mat[i][j]=max(c.mat[i][j],a.mat[i][k]+b.mat[k][j]);
        return c;
    }
}sum[N<<2];

namespace ST{
    inline void pushup(int now){ sum[now]=sum[now<<1]*sum[now<<1|1];}
    void build(int now,int l,int r){
        if(l==r) return sum[now].init(l),void();
        rei mid=l+r>>1;
        build(now<<1,l,mid),build(now<<1|1,mid+1,r);
        pushup(now);
    }
    void change(int now,int l,int r,int pos,int val){
        if(l==r) return sum[now].change(val);
        rei mid=l+r>>1;
        pos<=mid ? change(now<<1,l,mid,pos,val) : change(now<<1|1,mid+1,r,pos,val);
        pushup(now);
    }
    Matrix query(int now,int l,int r,int L,int R){
        if(l>=L && r <= R) return sum[now];
        rei mid=l+r>>1;
        if(L<=mid&&R>mid)
            return query(now<<1,l,mid,L,R)*query(now<<1|1,mid+1,r,L ,R);
        else if(L<=mid)
            return query(now<<1,l,mid,L,R);
        else return query(now<<1|1,mid+1,r,L,R);
    }
}

int main(){
    scanf("%d",&n);
    for(rei i=1;i<=n;++i) scanf("%d",&a[i]);
    ST::build(1,1,n);
    scanf("%d",&m);
    while(m--){
        rei op,x,y; scanf("%d%d%d",&op,&x,&y);
        if(op){
            Matrix ans=ST::query(1,1,n,x,y);
            ans.debug();
            puts("");
            printf("%d\n",max(ans.mat[1][0],ans.mat[1][2]));//唔，就是这里，对应上面的注意
        }
        else ST::change(1,1,n,x,y);
    }
    getchar(),getchar();
    return 0;
}

更复杂一点的序列上动态 $dp$

CF750E New Year and Old Subsequence

给定一个数字序列，每次询问一个区间，求区间内至少删去几个字符可以是该串包含子序列 $2017$ ，且不包含 $2016$

好吧猫老师还有需要支持单点修改的

没有删除操作的话就不怎么算是动态dp了（

首先由题得，这里的矩阵乘法中加法将被定义为取 $\min$

用 $0/1/2/3/4$ 替代 $\varnothing/2/20/201/2017$

设 $f_{i,0/1/2/3/4}$ 表示最少需要删去多少个字符才能在 $[1,i]$ 中包含 $\varnothing/2/20/201/2017$

有转移：

注意不成立的时候值应设为 $INF$

如此常系数齐次线性递推式可以变成矩阵形式

同上，线段树维护一下矩阵乘即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct Matrix{
    ...
    inline void init(int l){
        memset(mat,INF,sizeof mat);
        for(rei i=0;i<M;++i) mat[i][i]=0;
        if(s[l]=='2') mat[0][0]=1,mat[0][1]=0;
        if(s[l]=='0') mat[1][1]=1,mat[1][2]=0;
        if(s[l]=='1') mat[2][2]=1,mat[2][3]=0;
        if(s[l]=='7') mat[3][3]=1,mat[3][4]=0;
        if(s[l]=='6') mat[3][3]=1,mat[4][4]=1;
    }
    friend Matrix operator *(const Matrix a,const Matrix b){
        Matrix c;
        for(rei i=0;i<M;++i) for(rei j=0;j<M;++j) c.mat[i][j]=INF;
        for(rei i=0;i<M;++i) for(rei j=0;j<M;++j) for(rei k=0;k<M;++k)
            c.mat[i][j]=min(c.mat[i][j],a.mat[i][k]+b.mat[k][j]);
        return c;
    }
}sum[N<<2];

树上动态 $dp$

概述

树上动态 $dp$ 指一类支持树上单点修改全局查询题，一些信息可以通过暴力的线性树形 $dp$ 求出，一些问题需要支持子树或链上询问 $dp$ 值

转化

显然这类问题无法继续套用序列上的算法，而一种思路就是将其转化为序列问题—树链剖分—每一条重链都是一个序列上的问题

对于每一个节点的 $dp$ 值，如果其儿子都计算完毕，则可以计算该点的 $dp$ 值。于是可以选择任意符合该条件的顺序进行 $dp$

与之类似的，如果一条重链 $A$ 的顶端节点的父亲在重链 $B$ 中，就令 $A$ 的父亲重链为 $B$ ，由此能得到一颗重链树

如果按照重链树的顺序，且每条重链从下往上计算，则是合法的，因为每个儿子不是某条子重链的顶端(轻儿子)，就是重儿子

  • 为什么是重链剖分
    • 重链至多 $\log n$条，时间复杂度不劣
    • 一条重链在 $dfn$ 上的区间连续
    • 重链的链尾都是叶子节点，易于处理起始状态

转移

对于一条重链上的问题

来自猫老师的PPT

轻儿子的 $dp$ 值已经被计算，和节点本身的值可一起被视作输入

而修改的时候，按照重链树形一条一条往上改，每次会单点修改重链上一个点的本身或者轻边的信息

由此，问题被转化为了 $\log n$ 条重链上做序列动态 $dp$ 问题

例题-单点修改，区间询问

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

给出一棵树，每个点有点权，要求支持单点点权修改，查询以 $1$ 为根的一颗子树的最大权独立集

最大权独立集：相连的点不同时选得到的权值最大的点集

首先考虑弱化版，即没有修改操作

暴力 $dp$ ：设 $f_{i,c}$ 表示以 $i$ 为根的子树中满足 $c=[i 在所选独立集中]$ 的最大独立集，有转移：

再考虑完整的问题：怎样再重链里快速修改并查询该链的 $dp$ 值

不妨设点 $i$ 的编号就是 $i$ ，$g_{i,0/1}$ 表示点 $i$ 的轻儿子可取可不取/都不取的最大权独立集，那么有：

由此易得，在重链上：

观察式子不难发现，前两项看作输入的一部分，仅有最后一项和 $f_{i+1,}$ 有关，这里着重说明*如何构造矩阵的转移：

首先发现 $c=1$ 时 $g_{i,1},a_i$ 都仅与 $i$ 有关，考虑如何合并：更改 $g_{i,0/1}$ 的定义为： $i$ 号点只考虑轻儿子取自己的最大权独立集

那么式子变为 $f_{i,c}=g_{i,c}+\max\{f_{i+1,0},f_{i+1,1}-\infin\times c\}$

先将 $f$ 的转移方程拆开并变形：

然后把已知状态和要转移的状态写在一起：

$1\times 2$ 的矩阵形成了 $1\times 2$ 的矩阵，那么矩阵 $X$ 为 $2\times 2$

把位置对应上去有：

那么有：

再考虑矩阵乘法的顺序：初始信息位于叶子节点，即链尾处，由于 $dfn$ ，链尾在区间右端，链头在左端，所以矩阵乘法应是转移矩阵在前，要维护的在后，即：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
const int N=1e5+5;
const int M=2;
const int INF=0x7F7F7F7F;

int n,m;
int head[N],Next[N<<1],ver[N<<1],tot;
int A[N];
int fa[N],Size[N],depth[N],dfn[N],top[N],id[N],son[N],End[N],cnt;
int dp[N][2];

inline void add(int x,int y){ ver[++tot]=y; Next[tot]=head[x];head[x]=tot;}

struct Matrix{
    int mat[M][M];
    Matrix(){ memset(mat,0,sizeof mat);}
    inline void clear(int x){ for(rei i=0;i<n;++i) mat[i][x]=0;}
    inline void debug(){ for(rei i=0;i<M;++i) for(rei j=0;j<M;++j) printf("%d%c",mat[i][j],j==M-1 ? 10 : 32);}
    // inline void init(int l){
    // 	mat[0][0]=mat[0][2]=mat[1][0]=mat[1][2]=a[l];
    // 	mat[0][1]=mat[2][0]=mat[2][1]=-INF;
    // 	mat[1][1]=mat[2][2]=0;
    // }
    // inline void change(int val){ mat[0][0]=mat[0][2]=mat[1][0]=mat[1][2]=val;}
    friend Matrix operator *(const Matrix a,const Matrix b){
        Matrix c;
        for(rei i=0;i<M;++i) for(rei j=0;j<M;++j) c.mat[i][j]=-INF;
        for(rei i=0;i<M;++i) for(rei j=0;j<M;++j) for(rei k=0;k<M;++k)
            c.mat[i][j]=max(c.mat[i][j],a.mat[i][k]+b.mat[k][j]);
        return c;
    }
}sum[N<<2],val[N];

namespace ST{
    inline void pushup(int now){ sum[now]=sum[now<<1]*sum[now<<1|1];}
    void build(int now,int l,int r){
        if(l==r) return sum[now]=val[ dfn[l] ],void();
        rei mid=l+r>>1;
        build(now<<1,l,mid),build(now<<1|1,mid+1,r);
        pushup(now);
    }
    void change(int now,int l,int r,int pos){
        if(l==r) return sum[now]=val[ dfn[pos] ],void();
        rei mid=l+r>>1;
        pos<=mid ? change(now<<1,l,mid,pos) : change(now<<1|1,mid+1,r,pos);
        pushup(now);
    }
    Matrix query(int now,int l,int r,int L,int R){
        if(l>=L && r <= R) return sum[now];
        rei mid=l+r>>1;
        if(L<=mid && R>mid) return query(now<<1,l,mid,L,R)*query(now<<1|1,mid+1,r,L ,R);
        else if(L<=mid) return query(now<<1,l,mid,L,R);
        else return query(now<<1|1,mid+1,r,L,R);
    }
}

void dfs1(int x,int fath){
    Size[x]=1; depth[x]=depth[fath]+1;
    for(rei i=head[x];i;i=Next[i]){
        rei y=ver[i]; if(y==fath) continue;
        fa[y]=x; dfs1(y,x);
        Size[x]+=Size[y];
        if(Size[y]>Size[ son[x] ] || !son[x]) son[x]=y;
    }
}

void dfs2(int x,int anc=1){
    id[x]=++cnt; dfn[cnt]=x; top[x]=anc;
    End[anc]=max(End[anc],cnt);
    dp[x][0]=0; dp[x][1]=A[x];
    val[x].mat[0][0]=val[x].mat[0][1]=0;
    val[x].mat[1][0]=A[x];
    if(son[x]!=0){
        dfs2(son[x],anc);
        dp[x][0]+=max(dp[ son[x] ][0],dp[son[x]][1]);
        dp[x][1]+=dp[ son[x] ][0];
    }
    for(rei i=head[x];i;i=Next[i]){
        rei y=ver[i]; if(y==fa[x]||y==son[x]) continue;
        dfs2(y,y);
        dp[x][0]+=max(dp[y][0],dp[y][1]); dp[x][1]+=dp[y][0];
        val[x].mat[0][0]+=max(dp[y][0],dp[y][1]);//子儿子可选可不选的最大独立集
        val[x].mat[0][1]=val[x].mat[0][0];//同上
        val[x].mat[1][0]+=dp[y][0];//子儿子不能选
    }
}

inline void update_path(int x,int z){
    val[x].mat[1][0]+=z-A[x];//还存有子儿子不能选的值,不能直接赋值为z
    A[x]=z;//更新对应点的值
    Matrix last,now;
    while(x!=0){
        last=ST::query(1,1,n,id[ top[x] ],End[ top[x] ]);
        ST::change(1,1,n,id[x]);//找到需要更改的地方，进行更新
        now=ST::query(1,1,n,id[ top[x] ],End[ top[x] ]);
        x=fa[ top[x] ];//一直找重链，直到顶端
        val[x].mat[0][0]+=max(now.mat[0][0],now.mat[1][0])-max(last.mat[0][0],last.mat[1][0]); //之前可选可不选-现在可选可不选
        val[x].mat[0][1]=val[x].mat[0][0];
        val[x].mat[1][0]+=now.mat[0][0]-last.mat[0][0]; //之前不选-现在不选
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(rei i=1;i<=n;++i) scanf("%d",&A[i]);
    for(rei i=1,x,y;i<n;++i) scanf("%d%d",&x,&y),add(x,y),add(y,x);
    dfs1(1,0); dfs2(1);
    ST::build(1,1,n);
    for(rei i=1,x,y;i<=m;++i){
        scanf("%d%d",&x,&y);
        update_path(x,y);
        Matrix ans=ST::query(1,1,n,id[1],End[1]);
        printf("%d\n",max(ans.mat[0][0],ans.mat[1][0]));
    }
    getchar(),getchar();
    return 0;
}

P5024 [NOIP2018 提高组] 保卫王国

一棵树，有点权，要求最小权覆盖集，其中每组询问指定两个点的状态(选/不选)

最小权覆盖集=全集-最大权独立集

强制选择/不选相当于把该点权值改为 $\pm INF$

参考模板题即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include<bits/stdc++.h>
#define ll long long
#define rei long long
// #define int long long
// #define int long long
using namespace std;

const int N=1e5+100;
const int M=2;
// const ll INF=LONG_LONG_MAX;
const int INF=0x3f3f3f3f;
int n,m;
int head[N],Next[N<<1],ver[N<<1],tot;
ll a[N],sigma;
int fa[N],Size[N],depth[N],dfn[N],top[N],id[N],son[N],End[N],cnt;
ll dp[N][2];
char buff[20];

inline void add(int x,int y){ ver[++tot]=y; Next[tot]=head[x];head[x]=tot;}

struct Matrix{
    long long mat[M][M];
    Matrix(){ memset(mat,-INF,sizeof mat);}
    inline void clear(int x){ for(rei i=0;i<n;++i) mat[i][x]=0;}
    inline void debug(){ for(rei i=0;i<M;++i) for(rei j=0;j<M;++j) printf("%d%c",mat[i][j],j==M-1 ? 10 : 32);}
    // inline void init(int l){
    // 	mat[0][0]=mat[0][2]=mat[1][0]=mat[1][2]=a[l];
    // 	mat[0][1]=mat[2][0]=mat[2][1]=-INF;
    // 	mat[1][1]=mat[2][2]=0;
    // }
    // inline void change(int val){ mat[0][0]=mat[0][2]=mat[1][0]=mat[1][2]=val;}
    friend Matrix operator *(const Matrix a,const Matrix b){
        Matrix c;
        for(rei i=0;i<M;++i) for(rei j=0;j<M;++j) c.mat[i][j]=-INF;
        for(rei i=0;i<M;++i) for(rei j=0;j<M;++j) for(rei k=0;k<M;++k)
            c.mat[i][j]=max(c.mat[i][j],a.mat[i][k]+b.mat[k][j]);
        return c;
    }
}sum[N<<2],val[N];

namespace ST{
    inline void pushup(int now){ sum[now]=sum[now<<1]*sum[now<<1|1];}
    void build(int now,int l,int r){
        if(l==r) return sum[now]=val[ dfn[l] ],void();
        rei mid=l+r>>1;
        build(now<<1,l,mid),build(now<<1|1,mid+1,r);
        pushup(now);
    }
    void change(int now,int l,int r,int pos){
        if(l==r) return sum[now]=val[ dfn[pos] ],void();
        rei mid=l+r>>1;
        pos<=mid ? change(now<<1,l,mid,pos) : change(now<<1|1,mid+1,r,pos);
        pushup(now);
    }
    Matrix query(int now,int l,int r,int L,int R){
        if(l>=L && r <= R) return sum[now];
        rei mid=l+r>>1;
        if(L<=mid && R>mid) return query(now<<1,l,mid,L,R)*query(now<<1|1,mid+1,r,L ,R);
        else if(L<=mid) return query(now<<1,l,mid,L,R);
        else return query(now<<1|1,mid+1,r,L,R);
    }
}

void dfs1(int x,int fath){
    Size[x]=1; depth[x]=depth[fath]+1;
    for(rei i=head[x];i;i=Next[i]){
        rei y=ver[i]; if(y==fath) continue;
        fa[y]=x; dfs1(y,x);
        Size[x]+=Size[y];
        if(Size[y]>Size[ son[x] ] || !son[x]) son[x]=y;
    }
}

void dfs2(int x,int anc=1){
    id[x]=++cnt; dfn[cnt]=x; top[x]=anc;
    End[anc]=max(End[anc],cnt);
    dp[x][0]=0; dp[x][1]=a[x];
    val[x].mat[0][0]=val[x].mat[0][1]=0;
    val[x].mat[1][0]=a[x];
    if(son[x]!=0){
        dfs2(son[x],anc);
        dp[x][0]+=max(dp[ son[x] ][0],dp[son[x]][1]);
        dp[x][1]+=dp[ son[x] ][0];
    }
    for(rei i=head[x];i;i=Next[i]){
        rei y=ver[i]; if(y==fa[x]||y==son[x]) continue;
        dfs2(y,y);
        dp[x][0]+=max(dp[y][0],dp[y][1]); dp[x][1]+=dp[y][0];
        val[x].mat[0][0]+=max(dp[y][0],dp[y][1]);//子儿子可选可不选的最大独立集
        val[x].mat[0][1]=val[x].mat[0][0];//同上
        val[x].mat[1][0]+=dp[y][0];//子儿子不能选
    }
}

inline void update_path(int x,ll z){
    val[x].mat[1][0]+=z;
    Matrix last,now;
    while(x!=0){
        last=ST::query(1,1,n,id[ top[x] ],End[ top[x] ]);
        ST::change(1,1,n,id[x]);//找到需要更改的地方，进行更新
        now=ST::query(1,1,n,id[ top[x] ],End[ top[x] ]);
        x=fa[ top[x] ];//一直找重链，直到顶端
        val[x].mat[0][0]+=max(now.mat[0][0],now.mat[1][0])-max(last.mat[0][0],last.mat[1][0]); //之前可选可不选-现在可选可不选
        val[x].mat[0][1]=val[x].mat[0][0];
        val[x].mat[1][0]+=now.mat[0][0]-last.mat[0][0]; //之前不选-现在不选
    }
}

signed main(){
    scanf("%lld%lld%s",&n,&m,buff);
    for(rei i=1;i<=n;++i) scanf("%lld",&a[i]),sigma+=a[i];
    for(rei i=1,x,y;i<n;++i) scanf("%lld%lld",&x,&y),add(x,y),add(y,x);
    dfs1(1,0),dfs2(1);
    ST::build(1,1,n);
    for(rei i=1,x,y,v1,v2;i<=m;++i){
        scanf("%lld%lld%lld%lld",&x,&v1,&y,&v2);
        if(!v1 && !v2 && (fa[x]==y || fa[y]==x)){ puts("-1"); continue;}
        update_path(x,v1 ? -INF : INF),update_path(y,v2 ? -INF : INF);
        sigma+=(!v1 ? INF : 0)+(!v2 ? INF : 0);
        Matrix ans=ST::query(1,1,n,id[1],End[1]);
        ll res=sigma-max(ans.mat[0][0],ans.mat[1][0]);
        sigma-=(!v1 ? INF : 0)+(!v2 ? INF : 0);
        update_path(x,v1 ? INF : -INF),update_path(y,v2 ? INF : -INF);
        printf("%lld\n",res);
    }
    getchar(),getchar();
    return 0;
}

P3781 [SDOI2017]切树游戏

给定一颗有点权无根树，一颗树的价值为其所有点权值的异或和，支持两种操作：单点修改，查询有多少棵树满足价值为 $k$

照例先考虑暴力 $dp$ ：

设 $f_{i,j}$ 表示深度最小点(最高点)异或和为 $j$ 的连通块个数，答案即为 $\sum_{i=1}^n f_{i,k}$

易得转移为：$\displaystyle{f_{u,k}=\sum_{i\oplus j=k} f_{u,i}\times f_{v,j}+f_{u,k}}$

枚举 $i,j$ 有复杂度 $O(nm\times 128^2)$

观察到式子的下标是异或卷积的形式，$FWT$ 显然能优化到 $O(nm\times 128\log 128)$ ，但可以一直使用 $FWT$ 的数组计算，仅在开始结尾做 $FWT$ 的转化，时间复杂度可被简化为 $O((n+\log 128)\times 128)$

注意：如此后异或卷积 $a=b*c$ 为 $FWT_a=FWT_b · FWT_c$ ，即逐位相乘

考虑额外记录 $h_{i,k}$ 表示 $i$ 子树中 $f_{i,k}$ 的和，使 $dp$ 有子树的阶段性

再考虑到易于转移(过于简洁)的 $dp$ 式子，发现这是一个支持单点修改，查询的树上动态 $dp$ ，具体过程见上面，这里略

再从生成函数(多项式？) 的角度来更好的表达 $dp$ 过程：

对于每个节点 $u$ 上的所有 $f_{u,*}$ ，考虑用一个生成函数来表示所有的情况，即:

其中 $z$ 就是无实意的未知数( $x$ )，其项数 $i$ 表示子树权值为 $i$ ，前面的系数自然就是权值为 $i$ 的情况数

那么 $dp$ 转移能被简化为：

$val_u$ 是节点 $u$ 的权值，后面的 $z^0$ 作用显然： 设 $u$ 有两个子节点 $v1,v2$ ，将式子展开后能看出 $z^0$ 的作用：

显而易见，$z^0$ 保证了对于 $u$ 的子节点不同的选择方法，进一步展开后能发现选 $\{v1,v2\},\{v1\},\{v2\},\{\varnothing\}$ 的不同方案都被涵盖

对于重链上每个点 $i$ ，将 $i$ 的所有轻儿子 $lson_i$ 的 $F_{lson,z}+z^0$ 做卷积就能考虑所有轻儿子对于该子树的贡献，即

类比于 $F_{i,z}$ 的定义，对于 $h_{i,*}$ 定义 $H_{i,z}$

对于每个点再记录 $LH_{i,z}$ 表示点 $i$ 的每个轻儿子的 $H_{lson_i,z}$ 的和，即

由此，可以用线段树维护每个点的轻边的信息，而求出 $F_{hson,z},H_{hson,z}$ 后就能维护父亲重链的信息

对于一条重链，设重链上点深度从小到大为 $p_1,…,p_c$ ，那么有：

那么能得到矩阵转移：

这个 $3\times 3$ 的矩阵转移会导致要做 $27$ 次生成函数乘法，考虑如何优化

猫老师告诉我们，矩阵乘法对形如 $\begin{bmatrix}a & b & 0 \\ 0 & 1 & 0 \\ c & d & 1\end{bmatrix}$ 的矩阵是封闭的，即：

这样就优化为了 $4$ 次生成函数乘法

至此，这道 树剖后矩阵乘法卷积维护前缀和转多项式生成函数套个 $FWT$ 后上线段树 的题就完成了。。。吗？

树剖在洛谷上被卡掉了qwq，$80$ 分走人

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
#include <bits/stdc++.h>
#define rei register int
using namespace std;

const int M=130,N=3e4+100;
const int inv2=5004,mod=1e4+7;
int n,m,Q,tot,cnt;
int e[M][M],inv[mod+5],v[N],tmp1[M],tmp2[M];
int head[N],Next[N<<1],ver[N<<1];
int fa[N],depth[N],top[N],Size[N],pos[N],repos[N],hson[N],bot[N];
int F[N][M],H[N][M],lH[N][M];

inline int add(int x){ return x>=mod ? x-mod : x;}
inline void add(int x,int y){ ver[++tot]=y,Next[tot]=head[x],head[x]=tot;}

struct mat{
    int x,y;
    //神奇的方法：lF(x)->将值写成x*0^y的形式 如果有除以0的情况就将y--
    inline void put_val(int k){ k ? (x=k,y=0) : (x=1,y=1);}
    friend mat operator *(mat A,int B){
        (!B) ? ++A.y : A.x=A.x*B%mod;
        return A;
    }
    friend mat operator /(mat A,int B){
        (!B) ? --A.y : A.x=A.x*inv[B]%mod;
        return A;
    }
    inline int val(){ return y ? 0 : x;}
}lF[N][M];

inline void FWT(int *f,int n,int x){
    for(rei i=1;i<n;i<<=1) for(rei j=0;j<n;j+=(i<<1)) for(rei k=0;k<i;++k){
        rei t1=f[j+k],t2=f[j+i+k];
        f[j+k]=add(t1+t2),f[j+i+k]=add(t1-t2+mod);
        if(x==-1) f[j+k]=f[j+k]*inv2%mod,f[j+i+k]=f[j+i+k]*inv2%mod;
    }
}

namespace Tr{
    void dfs1(int x,int fath){
        fa[x]=fath,depth[x]=depth[fath]+1,Size[x]=1;
        for(rei i=head[x];i;i=Next[i]){
            rei y=ver[i]; if(y==fath) continue;
            dfs1(y,x),Size[x]+=Size[y];
        }
    }
    void dfs2(int x,int anc){
        rei heavy=0,MAX=0; pos[x]=++cnt,repos[cnt]=x;
        for(rei i=head[x];i;i=Next[i]){
            rei y=ver[i]; if(y==anc || Size[y]<=MAX) continue;
            MAX=Size[y],heavy=y;
        }
        if(!heavy) return bot[ top[x] ]=pos[x],void();
        hson[x]=heavy,top[heavy]=top[x],dfs2(heavy,x);
        for(rei i=head[x];i;i=Next[i]){
            rei y=ver[i]; if(y==anc || y==heavy) continue;
            top[y]=y,dfs2(y,x);
        }
    }
}

namespace INIT{
    void dfs(int x,int anc){
        for(rei i=0;i<m;++i) F[x][i]=e[ v[x] ][i];
        for(rei i=head[x];i;i=Next[i]){
            rei y=ver[i];
            if(y==anc) continue;
            dfs(y,x);
            for(rei j=0;j<m;++j){
                F[x][j]=add(F[x][j]+F[x][j]*F[y][j]%mod);
                H[x][j]=add(H[x][j]+H[y][j]);
            }
        }
        for(rei i=0;i<m;++i) H[x][i]=add(H[x][i]+F[x][i]);
    }
    void getl(){
        for(rei x=1;x<=n;++x){
            for(rei i=0;i<m;++i) lF[x][i].put_val(e[0][i]),lH[x][i]=0;
            for(rei i=head[x];i;i=Next[i]){
                rei y=ver[i];
                if(y==fa[x] || y==hson[x]) continue;
                for(rei j=0;j<m;++j){
                    lF[x][j]=lF[x][j]*add(1+F[y][j]);
                    lH[x][j]=add(lH[x][j]+H[y][j]);
                }
            }
        }
    }
}

namespace ST{
    struct tree_node{
        int a[M],b[M],c[M],d[M];
        friend tree_node operator *(tree_node A,tree_node B){
            tree_node C;
            for(rei i=0;i<m;++i) C.a[i]=C.b[i]=C.c[i]=C.d[i]=0;
            for(rei i=0;i<m;++i) {
                C.a[i]=A.a[i]*B.a[i]%mod;
                C.b[i]=add(A.b[i]+A.a[i]*B.b[i]%mod);
                C.c[i]=add(B.a[i]*A.c[i]%mod+B.c[i]);
                C.d[i]=add(B.b[i]*A.c[i]%mod+add(A.d[i]+B.d[i]));
            }
            return C;
        }
    }tr[N<<2];
    inline void pushup(int now){ tr[now]=tr[now<<1|1]*tr[now<<1];}//注意合并的顺序啊啊啊
    inline void update(int i,int x){
        for(rei j=0;j<m;++j){
            tr[i].a[j]=tr[i].b[j]=tr[i].c[j]=tr[i].d[j]=lF[x][j].val()*e[ v[x] ][j]%mod;
            tr[i].d[j]=add(tr[i].d[j]+lH[x][j]);
        }
    }
    void build(int now,int l,int r){
        if(l==r) return update(now,repos[l]),void();
        rei mid=l+r>>1;
        build(now<<1,l,mid),build(now<<1|1,mid+1,r);
        pushup(now);
    }
    tree_node query(int now,int l,int r,int L,int R){
        if(L<=l&&r<=R) return tr[now];
        rei mid=l+r>>1;
        if(R<=mid) return query(now<<1,l,mid,L,R);
        if(mid+1<=L) return query(now<<1|1,mid+1,r,L,R);
        return query(now<<1|1,mid+1,r,L,R)*query(now<<1,l,mid,L,R);
    }
    void change(int now,int l,int r,int x){
        if(l==r) return update(now,repos[l]),void();
        rei mid=l+r>>1;
        x<=mid ? change(now<<1,l,mid,x) : change(now<<1|1,mid+1,r,x);
        pushup(now);
    }
    inline void getans(int x){
        tree_node re=query(1,1,n,pos[x],bot[x]);
        for(rei i=0;i<m;++i) tmp1[i]=re.c[i],tmp2[i]=re.d[i];//F,H
    }
}

inline void change(int x,int new_v){
    v[x]=new_v;
    while(x){
        rei y=fa[ top[x] ];
        ST::getans(top[x]);
        if(y) for(rei i=0;i<m;++i) lF[y][i]=lF[y][i]/add(tmp1[i]+1), lH[y][i]=add(lH[y][i]-tmp2[i]+mod);
        ST::change(1,1,n,pos[x]),ST::getans(top[x]);
        if(y) for(rei i=0;i<m;++i) lF[y][i]=lF[y][i]*add(tmp1[i]+1),lH[y][i]=add(lH[y][i]+tmp2[i]);
        x=y;
    }
}

int main(){
    char op[10]; scanf("%d%d",&n,&m);
    for(rei i=1;i<=n;++i) scanf("%d",&v[i]);
    for(rei i=1,x,y;i<n;++i) scanf("%d%d",&x,&y),add(x,y),add(y,x);
    for(rei i=0;i<m;++i) e[i][i]=1,FWT(e[i],m,1);
    inv[1]=1;
    for(rei i=2;i<mod;++i) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    Tr::dfs1(1,0),top[1]=1;
    Tr::dfs2(1,0);
    INIT::dfs(1,0),INIT::getl();
    ST::build(1,1,n);
    scanf("%d",&Q);
    while(Q--){
        scanf("%s",op); rei x,y;
        if(op[0]=='C') scanf("%d%d",&x,&y),change(x,y);
        else{
            scanf("%d",&x),ST::getans(1);
            FWT(tmp2,m,-1),printf("%d\n",tmp2[x]);
        }
    }
    getchar(),getchar();
    return 0;
}