文章目录
广义矩阵乘法动态DP例题：洛谷4719以下内容是本人做题经验，如有雷同，纯属抄袭；如有不对，纯属不懂，还请指正
广义矩阵乘法
众所周知，矩阵满足乘法交换律，前一个矩阵的列必须是后一个矩阵的行
n×pn\times pn×p的AAA矩阵和p×mp\times mp×m的BBB矩阵相乘得到CCC矩阵
Ci,j=∑k=1pAi,k×Bk,jC_{i,j}=\sum_{k=1}^pA_{i,k}\times B_{k,j}Ci,j=k=1∑pAi,k×Bk,j
假设矩阵D=A∗B∗CD=A*B*CD=A∗B∗C，考虑DDD是如何生成的
Di,j=∑k=1n((∑p=1nAi,p×Bp,k)×Ck,j)D_{i,j}=\sum_{k=1}^n\left ( (\sum_{p=1}^nA_{i,p}\times B_{p,k}) \times C_{k,j} \right)Di,j=k=1∑n((p=1∑nAi,p×Bp,k)×Ck,j)=∑k=1n(∑p=1n(Ai,p×Bp,k×Ck,j))=\sum_{k=1}^n\left ( \sum_{p=1}^n(A_{i,p}\times B_{p,k} \times C_{k,j})\right)=k=1∑n(p=1∑n(Ai,p×Bp,k×Ck,j))=∑k=1n(Ai,p×∑p=1n(Bp,k×Ck,j))=\sum_{k=1}^n\left ( A_{i,p}\times \sum_{p=1}^n(B_{p,k} \times C_{k,j})\right)=k=1∑n(Ai,p×p=1∑n(Bp,k×Ck,j))=A∗(B∗C)=A*(B*C)=A∗(B∗C)
性质
如果把乘法和加法换成其他运算，opt1,opt2opt1,opt2opt1,opt2
只要满足opt1对opt2满足分配律，则其也满足矩阵的结合律
就好比乘法对加法满足分配律
因为a∗(b+c)a*(b+c)a∗(b+c)，与aaa先乘进括号再相加的答案a∗b+a∗ca*b+a*ca∗b+a∗c一样
opt1：仁兄，稳住
——opt2：你要搞爪子，我憋不住了
opt1：不要占着茅坑，先让我来
然后opt1解放了，离开了，只剩下opt2继续解决
再举个减法和取最大值的例子
我们知道max(b−a,c−a)=max(b,c)−amax(b-a,c-a)=max(b,c)-amax(b−a,c−a)=max(b,c)−a
所以我们也可以说减法对取最大值满足分配律
有了这个进阶版本，我们就可以将一般平常写的矩阵中的乘法和加法操作换掉
动态DP
很多题目并不是静态的，往往伴随着修改原内容的操作，导致DP值不再正确
暴力的想法，则是每次修改，就重新做一遍DP
显然这样除了TLE别无出路
然而这个时候——动态DP孕育而生
动态DP，如其名，生来就是解决这种改变影响之前的DP值的问题
一半来说优化算法都是往logloglog级下压
动态DP就是借助广义矩阵来进行快速优化的
这类题目，原始的转移一定可以用矩阵乘法来加速做
然后修改，就变成了加速矩阵的修改
一般还会在线段树上进行矩阵的合并
例题：洛谷4719
Step1：考虑没有修改
就是一道非常板的树形DP
设f[i][0/1]f[i][0/1]f[i][0/1]表示是否选iii时，子树iii的最大值，111选，000不选
{f[i][0]=∑j∈sonimax(f[j][1],f[j][0])f[i][1]=∑j∈sonif[j][0]\left\{ \begin{aligned} f[i][0]=\sum_{j∈son_i}max(f[j][1],f[j][0])\\ f[i][1]=\sum_{j∈son_i}f[j][0]&&&&&&&&&&&&&&&&&&&&&&&&&\\ \end{aligned} \right. ⎩⎪⎪⎪⎨⎪⎪⎪⎧f[i][0]=j∈soni∑max(f[j][1],f[j][0])f[i][1]=j∈soni∑f[j][0]
Step2：考虑特殊的链形式，假设仍然没有修改
也就是说iii只有一个儿子jjj，就没有之前所谓的求和罢了
{f[i][0]=max(f[j][1],f[j][0])f[i][1]=f[j][0]+w[i]\left\{ \begin{aligned} f[i][0]=max(f[j][1],f[j][0])\\ f[i][1]=f[j][0]+w[i]&&&&&&&&&&&&&&&&&&&&&&&&&\\ \end{aligned} \right. {f[i][0]=max(f[j][1],f[j][0])f[i][1]=f[j][0]+w[i]
这里就可以用到前面所说的加法对于求最大值有分配律
人为的给f[i][1]f[i][1]f[i][1]转移添加一个最大值，f[i][1]=max(f[j][0])+w[i]f[i][1]=max(f[j][0])+w[i]f[i][1]=max(f[j][0])+w[i]
那么就可以构造矩阵进行矩阵加速了
矩阵相乘时，为了防止f[j][1]f[j][1]f[j][1]对f[i][1]f[i][1]f[i][1]造成贡献
此题可以将其矩阵位置上设个极小值
[00w[i]−INF]×[f[j][0]f[j][1]]=[f[i][0]f[i][1]]\begin{bmatrix} 0&0\\ w[i]&-INF\\ \end{bmatrix}\times \begin{bmatrix} f[j][0]\\ f[j][1] \end{bmatrix}=\begin{bmatrix} f[i][0]\\ f[i][1]\\ \end{bmatrix}[0w[i]0−INF]×[f[j][0]f[j][1]]=[f[i][0]f[i][1]]
Step3：考虑一般形式，仍然没有修改
可以将加速矩阵重新构造为
[f′[i][0]f′[i][0]f′[i][1]−INF]×[f[j][0]f[j][1]]=[f[i][0]f[i][1]]\begin{bmatrix} f'[i][0]&f'[i][0]\\ f'[i][1]&-INF\\ \end{bmatrix}\times \begin{bmatrix} f[j][0]\\ f[j][1] \end{bmatrix}=\begin{bmatrix} f[i][0]\\ f[i][1]\\ \end{bmatrix}[f′[i][0]f′[i][1]f′[i][0]−INF]×[f[j][0]f[j][1]]=[f[i][0]f[i][1]]
f′[i][0]f'[i][0]f′[i][0]表示除了儿子jjj贡献之外的f[i][0]f[i][0]f[i][0]f′[i][1]f'[i][1]f′[i][1]表示除了儿子jjj贡献之外的f[i][1]f[i][1]f[i][1]
意思就是我们要将儿子分为两种，一种是特殊转移的，另一种就是剩下的
也就是说这个儿子灰常忒殊，加上我们已经会做链的形式了
自然而然想到树链剖分中的重儿子
对于重儿子直接维护这个矩阵，一条重链的矩乘可以用线段树压为logloglog
轻儿子就暴力转移即可
轻儿子暴力转移一次到父亲，然后父亲就爬自己所在的那条重链
Step4：现在考虑修改
有了树链剖分，修改也变得可操作了
假设修改了iii点，除了iii和其父亲的fff会受到影响，其余是不变的
所以我们只需要修改子树iii和iii的祖先的fff值即可
首先更新不考虑重儿子的f[i][1]f[i][1]f[i][1]的值，更新iii的矩阵（每个点都有一个加速矩阵）
然后对iii所在重链，进行单点修改操作，更新fff和矩阵
然后爬到新的重链，设到达的点为xxx，之前重链的顶端对新的重链而言是轻儿子
所以要更新f′[x][0]f'[x][0]f′[x][0]和f′[x][1]f'[x][1]f′[x][1]
以此类推，一路往上修改，时间复杂度O(logn2)O(\log n^2)O(logn2)
#include <cstdio>#include <vector>#include <cstring>#include <iostream>using namespace std;#define inf 1e12#define maxn 100005#define int long longstruct matrix {int c[2][2];matrix(){}matrix( int x1, int x2, int x3, int x4 ) {c[0][0] = x1, c[0][1] = x2, c[1][0] = x3, c[1][1] = x4;}void clear() {memset( c, 0, sizeof( c ) );}int *operator [] ( int x ) {return c[x]; }matrix operator * ( matrix v ) const {matrix ans;ans.clear();for( int i = 0;i < 2;i ++ )for( int j = 0;j < 2;j ++ )for( int k = 0;k < 2;k ++ )ans[i][j] = max( ans[i][j], c[i][k] + v[k][j] );return ans;}}tree[maxn << 2], tmp[maxn];vector < int > G[maxn];int n, m, cnt;int a[maxn];int siz[maxn], f[maxn], son[maxn];int dfn[maxn], id[maxn], top[maxn], bot[maxn];int dp[maxn][2];void dfs1( int u, int fa ) {siz[u] = 1, f[u] = fa;for( int i = 0;i < G[u].size();i ++ ) {int v = G[u][i];if( v == fa ) continue;dfs1( v, u );siz[u] += siz[v];if( siz[v] > siz[son[u]] || ! son[u] )son[u] = v;}}void dfs2( int u, int t ) {top[u] = t, dfn[u] = ++ cnt, id[cnt] = u;if( son[u] ) dfs2( son[u], t ), bot[u] = bot[son[u]];else bot[u] = u;for( int i = 0;i < G[u].size();i ++ ) {int v = G[u][i];if( v == f[u] || v == son[u] ) continue;else dfs2( v, v );}}void dfs( int u ) {dp[u][0] = 0, dp[u][1] = a[u];for( int i = 0;i < G[u].size();i ++ ) {int v = G[u][i];if( v == f[u] ) continue;dfs( v );dp[u][1] += dp[v][0];dp[u][0] += max( dp[v][1], dp[v][0] );}}void build( int num, int l, int r ) {if( l == r ) {int u = id[l], f1 = a[u], f0 = 0;for( int i = 0;i < G[u].size();i ++ ) {int v = G[u][i];if( v == f[u] || v == son[u] ) continue;f1 += dp[v][0], f0 += max( dp[v][0], dp[v][1] );}tree[num] = tmp[l] = matrix( f0, f0, f1, -inf );return;}int mid = ( l + r ) >> 1;build( num << 1, l, mid );build( num << 1 | 1, mid + 1, r );tree[num] = tree[num << 1] * tree[num << 1 | 1];}void modify( int num, int l, int r, int pos ) {if( l == r ) {tree[num] = tmp[l]; return; }int mid = ( l + r ) >> 1;if( pos <= mid ) modify( num << 1, l, mid, pos );else modify( num << 1 | 1, mid + 1, r, pos );tree[num] = tree[num << 1] * tree[num << 1 | 1];}matrix query( int num, int l, int r, int L, int R ) {if( L <= l && r <= R ) return tree[num];int mid = ( l + r ) >> 1;if( R <= mid ) return query( num << 1, l, mid, L, R );else if( mid < L ) return query( num << 1 | 1, mid + 1, r, L, R );else return query( num << 1, l, mid, L, R ) * query( num << 1 | 1, mid + 1, r, L, R );}void modify( int u, int w ) {tmp[dfn[u]][1][0] += w - a[u], a[u] = w;while( u ) {matrix last = query( 1, 1, n, dfn[top[u]], dfn[bot[u]] );modify( 1, 1, n, dfn[u] );matrix now = query( 1, 1, n, dfn[top[u]], dfn[bot[u]] );u = f[top[u]];if( ! u ) break;int p = dfn[u];tmp[p][0][0] = tmp[p][0][1] = tmp[p][0][0] + max( now[0][0], now[1][0] ) - max( last[0][0], last[1][0] );tmp[p][1][0] = tmp[p][1][0] + now[0][0] - last[0][0];}}signed main() {scanf( "%lld %lld", &n, &m );for( int i = 1;i <= n;i ++ )scanf( "%lld", &a[i] );for( int i = 1, u, v;i < n;i ++ ) {scanf( "%lld %lld", &u, &v );G[u].push_back( v );G[v].push_back( u ); }dfs1( 1, 0 );dfs2( 1, 1 );dfs( 1 );build( 1, 1, n );for( int i = 1, x, y;i <= m;i ++ ) {scanf( "%lld %lld", &x, &y );modify( x, y ); matrix ans = query( 1, 1, n, 1, dfn[bot[1]] );printf( "%lld\n", max( ans[0][0], ans[1][0] ) );}return 0;}
