动态DP
何为动态DP？
将画风正常的DP加上修改操作。
举个例子？
给你一个长度为(n)的数列，从中选出一些数，要求选出的数互不相邻，最大化选出的数的和。
考虑DP，状态设计为(f[i][1/0])表示考虑了前(i)个数，第(i)个数选/不选的最大和。
状态转移方程显然为：
很简单对不对？
改成这样呢？
给你一个长度为(n)的数列。有(m)次操作，每次操作修改其中一个位置上的数或者从整个数列中选出一些数，要求选出的数不相邻，询问选出的数的和的最大值。
怎么做？
每次修改完重新暴力DP一遍？
不好意思，(n,m leq 100000)。
那怎么办？
呦嚯，完蛋。
我们发现(f[i-1][0/1])到(f[i][0/1])的转移可以写成矩阵乘法的形式。
需要注意的是这里的矩阵乘法和一般的矩阵乘法略有不同，即用(max)替换原来的(+)，用(+)代替原来的( imes)。
然后就可以使用线段树维护矩阵连乘，得到单次修改(O(logn))，单次询问(O(1))的优秀算法了。
出在树上？
题意
给定一棵(n)个点的树，点带点权。
有(m)次操作，每次操作给定
(x,y)，表示修改点(x)的权值为(y)。
你需要在每次操作之后求出这棵树的最大权独立集的权值大小。
(n,m leq 100000)。
暴力出奇迹？对于这道题来说不存在的。
题解
简而言之就是带修改树上最大权独立集。
首先，如果一个点的点权小于(0)，我们可以认为其为(0)，显然这样不会影响答案。（后来想想这步好像没啥用）
其实刚才那道例题是这道题的链的特殊情况。
但这也启发了我们要把树上的问题转化为序列上的问题，于是我们想到了树剖。
(f[x][1/0])表示以(x)为根的子树中，结点(x)选/不选时的最大权独立集。(g[x][1/0])表示以(x)为根的子树中，不考虑以(heavychild[x])为根的子树，结点(x)选/不选时的最大权独立集。
这里的(g)数组就类似于上一题的(a)数组。
树剖后使用线段树维护每条重链上的矩阵连乘，转移矩阵与上题类似。
（(ver)代表(heavychild[x])）
（(g)的下标好像有点挤）
这样就可以实现带修改了。具体来说，就是在线段树上修改->跳重链->处理这个轻子树的影响->在线段树上修改->跳重链->处理这个轻子树的影响->...如此循环直到处理完(top)为(1)的重链为止。
时间复杂度(O(nlog^2n))。
要注意矩阵乘法部分如果和我写的一样的话线段树上需要倒着乘（矩阵乘法无交换律）。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <algorithm>
#define rin(i,a,b) for(int i=(a);i<=(b);i++)
#define rec(i,a,b) for(int i=(a);i>=(b);i--)
#define trav(i,a) for(int i=head[(a)];i;i=e[i].nxt)
using std::cin;
using std::cout;
using std::endl;
typedef long long LL;
inline LL read(){
LL x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
const int MAXN=100005;
int n,m;
int ecnt,head[MAXN];
LL w[MAXN];
int fa[MAXN],dep[MAXN],siz[MAXN],pc[MAXN],top[MAXN],id[MAXN],ed[MAXN],num[MAXN],tot;
LL f[MAXN][2];
int loc,ql,qr;
struct Edge{
int to,nxt;
}e[MAXN<<1];
struct Mat{
LL g[2][2];
Mat(){memset(g,0xc0,sizeof g);}
friend Mat operator * (Mat x,Mat y){
Mat ret;
rin(i,0,1) rin(j,0,1) rin(k,0,1)
ret.g[i][j]=std::max(ret.g[i][j],x.g[i][k]+y.g[k][j]);
return ret;
}
}tr[MAXN<<2],sav[MAXN];
inline void add_edge(int bg,int ed){
ecnt++;
e[ecnt].to=ed;
e[ecnt].nxt=head[bg];
head[bg]=ecnt;
}
void dfs1(int x,int pre,int depth){
fa[x]=pre;
dep[x]=depth;
siz[x]=1;
int maxsiz=-1;
trav(i,x){
int ver=e[i].to;
if(ver==pre) continue;
dfs1(ver,x,depth+1);
siz[x]+=siz[ver];
if(siz[ver]>maxsiz){
maxsiz=siz[ver];
pc[x]=ver;
}
}
}
void dfs2(int x,int topf){
top[x]=topf;
id[x]=++tot;
num[tot]=x;
if(!pc[x]) return;
dfs2(pc[x],topf);
trav(i,x){
int ver=e[i].to;
if(ver==fa[x]||ver==pc[x]) continue;
dfs2(ver,ver);
}
}
void dfs3(int x){
f[x][1]=w[x];
trav(i,x){
int ver=e[i].to;
if(ver==fa[x]) continue;
dfs3(ver);
f[x][0]+=std::max(f[ver][0],f[ver][1]);
f[x][1]+=f[ver][0];
}
}
#define mid ((l+r)>>1)
#define lc (o<<1)
#define rc ((o<<1)|1)
void build(int o,int l,int r){
if(l==r){
int x=num[l];
LL g0=0,g1=w[x];
trav(i,x){
int ver=e[i].to;
if(ver==fa[x]||ver==pc[x]) continue;
g0+=std::max(f[ver][0],f[ver][1]);
g1+=f[ver][0];
}
tr[o].g[0][0]=tr[o].g[1][0]=g0;
tr[o].g[0][1]=g1;
tr[o].g[1][1]=-1e18;
sav[l]=tr[o];
return;
}
build(lc,l,mid);
build(rc,mid+1,r);
tr[o]=tr[rc]*tr[lc];
}
void upd(int o,int l,int r){
if(l==r){
tr[o]=sav[l];
return;
}
if(loc<=mid) upd(lc,l,mid);
else upd(rc,mid+1,r);
tr[o]=tr[rc]*tr[lc];
}
Mat query(int o,int l,int r){
if(ql<=l&&r<=qr) return tr[o];
if(ql>mid) return query(rc,mid+1,r);
else if(qr<=mid) return query(lc,l,mid);
else return query(rc,mid+1,r)*query(lc,l,mid);
}
#undef mid
#undef lc
#undef rc
inline Mat subquery(int x){
ql=id[x],qr=ed[x];
return query(1,1,n);
}
inline void pathupd(int x,LL y){
if(w[x]==y) return;
LL temp=w[x];
w[x]=y;
bool flag=1;
Mat pre,now;
while(x){
if(flag){
sav[id[x]].g[0][1]+=y-temp;
pre=subquery(top[x]);
loc=id[x];
upd(1,1,n);
now=subquery(top[x]);
flag=0;
}
else{
sav[id[x]].g[0][0]+=std::max(now.g[0][0],now.g[0][1])
-std::max(pre.g[0][0],pre.g[0][1]);
sav[id[x]].g[1][0]=sav[id[x]].g[0][0];
sav[id[x]].g[0][1]+=now.g[0][0]-pre.g[0][0];
pre=subquery(top[x]);
loc=id[x];
upd(1,1,n);
now=subquery(top[x]);
}
x=fa[top[x]];
}
}
int main(){
n=read(),m=read();
rin(i,1,n) w[i]=std::max(read(),0ll);
rin(i,2,n){
int u=read(),v=read();
add_edge(u,v);
add_edge(v,u);
}
dfs1(1,0,1);
dfs2(1,1);
dfs3(1);
rin(i,1,n)
ed[top[i]]=std::max(ed[top[i]],id[i]);
build(1,1,n);
while(m--){
int x=read();
LL y=std::max(read(),0ll);
pathupd(x,y);
Mat ans=subquery(1);
printf("%lld
",std::max(ans.g[0][0],ans.g[0][1]));
}
return 0;
}
值得一提的是，可以使用(Link-Cut Tree)或全局平衡二叉树以达到更优的(O(nlogn))的时间复杂度。