动态DP-学习笔记
i207M
2018-11-13 08:35:16
## 动态DP
猫锟在WC2018讲的黑科技——动态DP，就是一个画风正常的DP问题再加上一个动态修改操作。
By RabbitHu.
重定义矩阵乘法：
$C_{i, j} = \max_{k = 1}^{n} (A_{i, k} + B_{k, j})$
类似于乘法和加法的五种运算律，这两种变化也满足“加法交换律”、“加法结合律”、“max交换律”、“max结合律”和“加法分配律“。那么这种矩阵乘法显然也满足矩阵乘法结合律，就像正常的矩阵乘法一样，可以用线段树维护。
## 树上最大带权独立集
$f_{i,0}$表示子树i中不选i的最大权独立集大小，$f_{i,1}$表示子树i中选i的最大权独立集大小。
但这是动态DP，我们需要树链剖分。假设我们已经完成了树链剖分，剖出来的某条重链看起来就像这样，右边的是在树上深度较大的点：
此时，比这条重链的top深度大且不在这条重链上的点的DP值都是已经求出来的（这可以做到）。我们**把它们的贡献，都统一于它们在这条重链上对应的那个祖先上**。
具体来说，设$g_{i,0}$表示不选i时，i不在链上的子孙的最大权独立集大小，$g_{i,1}$表示选i时，i不在链上的子孙再加上i自己的最大权独立集大小。
假如i右面的点是i+1，那么可以得出：
$f_{i, 0} = g_{i, 0} + \max(f_{i + 1, 0}, f_{i + 1, 1})$
$f_{i, 1} = g_{i, 1} + f_{i + 1, 0}$
矩阵：
$\begin{bmatrix}g_{i, 0} & g_{i, 0} \\g_{i, 1} & 0\end{bmatrix} * \begin{bmatrix}f_{i + 1, 0} \\ f_{i + 1, 1}\end{bmatrix} = \begin{bmatrix}f_{i, 0} \\ f_{i, 1}\end{bmatrix}$
那么基本思路就很清楚了：树剖，维护区间矩阵乘积。修改的时候，对于被修改节点到根节点路径上的每个重链（由下到上），先进行单点修改，然后求出这条重链的fa[top]在修改之后的g值，然后继续修改fa[top]所在重链。
## 动态DP加强版
要想通过这道题，我们需要建立“全局平衡二叉树”，具体来说，我们对每条重链单独建二叉树，每个点的权值为轻儿子sz之和+1，每次找到带权重心，分治下去。
这样的复杂度可以类比LCT，会比较快。
----------------
```cpp
namespace i207M
{
template<class T>il void in(T &x)
{
x=0; bool f=0; char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-') f=1;
c=getchar();
}
while(c>='0'&&c<='9') x=x*10+(c^'0'),c=getchar();
if(f) x=-x;
}
#define N 100005
#define M N<<2
int n;
int a[N];
int v[N<<1],nx[N<<1];
int head[N],cnte;
il void adde(int uu,int vv)
{
v[++cnte]=vv,nx[cnte]=head[uu],head[uu]=cnte;
}
struct Mat
{
int m[2][2];
int *operator[](int x)
{
return m[x];
}
Mat()
{
memset(m,0,sizeof m);
}
friend Mat operator*(const Mat &a,const Mat &b)
{
Mat res;
for(ri i=0; i<2; ++i)
for(ri k=0; k<2; ++k)
for(ri j=0; j<2; ++j)
res[i][j]=max(res[i][j],a.m[i][k]+b.m[k][j]);
return res;
}
} val[N],dat[M];
int fa[N],sz[N],hsn[N],dfn[N],dk,ot[N],ys[N],top[N];
int f[N][2];
void dfs(int x,int ff)
{
fa[x]=ff,sz[x]=1;
f[x][1]=a[x];
for(ri i=head[x]; i; i=nx[i])
if(v[i]!=ff)
{
dfs(v[i],x);
sz[x]+=sz[v[i]];
if(sz[v[i]]>sz[hsn[x]]) hsn[x]=v[i];
f[x][0]+=max(f[v[i]][0],f[v[i]][1]);
f[x][1]+=f[v[i]][0];
}
}
void efs(int x,int tp)
{
dfn[x]=++dk,ys[dk]=x,top[x]=tp,ot[tp]=dk;
if(hsn[x]) efs(hsn[x],tp);
for(ri i=head[x]; i; i=nx[i])
if(v[i]!=fa[x]&&v[i]!=hsn[x])
efs(v[i],v[i]);
}
const int rt=1;
#define gm int mid((l+r)>>1)
#define ls (x<<1)
#define rs (x<<1|1)
il void up(int x)
{
dat[x]=dat[ls]*dat[rs];
// WARNING: Lson, Rson
}
void build(int x,int l,int r)
{
if(l==r)
{
int u=ys[l],g0=0,g1=a[u];
for(ri i=head[u]; i; i=nx[i])
if(v[i]!=fa[u]&&v[i]!=hsn[u])
{
g0+=max(f[v[i]][0],f[v[i]][1]);
g1+=f[v[i]][0];
}
val[l][0][0]=val[l][0][1]=g0,val[l][1][0]=g1,val[l][1][1]=-1000000000;
dat[x]=val[l];
return;
}
gm;
build(ls,l,mid), build(rs,mid+1,r);
up(x);
}
void upd(int x,int l,int r,int p)
{
if(l==r)
{
dat[x]=val[l];
return;
}
gm;
if(p<=mid) upd(ls,l,mid,p);
else upd(rs,mid+1,r,p);
up(x);
}
Mat ask(int x,int l,int r,int ql,int qr)
{
if(ql<=l&&r<=qr) return dat[x];
gm;
if(qr<=mid) return ask(ls,l,mid,ql,qr);
else if(ql>mid) return ask(rs,mid+1,r,ql,qr);
else return ask(ls,l,mid,ql,qr)*ask(rs,mid+1,r,ql,qr);
}
Mat query(int x)
{
return ask(rt,1,n,dfn[x],ot[x]);
}
void pathupd(int u,int k)
{
val[dfn[u]][1][0]+=k-a[u];
a[u]=k;
Mat od,nw;
while(u)
{
od=query(top[u]);
upd(rt,1,n,dfn[u]);
nw=query(top[u]);
u=fa[top[u]];
val[dfn[u]][0][0]+=max(nw[0][0],nw[1][0])-max(od[0][0],od[1][0]);
val[dfn[u]][0][1]=val[dfn[u]][0][0];
val[dfn[u]][1][0]+=nw[0][0]-od[0][0];
}
}
void init()
{
dfs(1,0);
efs(1,1);
build(rt,1,n);
}
signed main()
{
#ifdef M207
freopen("in.in","r",stdin);
#endif
int cntq,x,y;
in(n),in(cntq);
for(ri i=1; i<=n; ++i) in(a[i]);
for(ri i=1,a,b; i<n; ++i)
{
in(a),in(b);
adde(a,b), adde(b,a);
}
init();
Mat t;
while(cntq--)
{
in(x),in(y);
pathupd(x,y);
t=query(1);
printf("%d\n",max(t[0][0],t[1][0]));
}
return 0;
}
}
```