基于变换合并的树上动态DP的链分治算法和全局平衡二叉树
引入
在有些dp中，转移可以用一种具有结合律的变换描述，并且可以快速合并
因此我们使用数据结构维护，来支持修改并快速得到全局或某个子结构的dp值
直接看例题吧
例题
例题一 【模板】动态dp
题意
给定一棵 $n$ 个点的树，第 $i$ 个点有点权 $a_i$。
有 $m$ 次操作，每次操作给定 $x,y$，表示修改点 $x$ 的权值为 $y$。
你需要在每次操作之后求出这棵树的最大权独立集的权值大小。
$n,m\le10^5$
分析
一个弱化
对于没有修改的情况，我们有一种简单的 $\mathcal O(n)$ 树形dp
钦定一个根节点
令 $f_{u,0/1}$ 表示以 $u$ 为根的子树， $u$ 号点不选/选时的最大权独立集的权值大小
$$
\begin{align}
f_{u,0}&=\sum_{u\to v}max(f_{v,0},f_{v,1})\
f_{u,1}&=a_u+\sum_{u\to v}f_{v,0}
\end{align}
$$
另一个弱化
对于树是一条链的情况，上述dp可以大大简化
树链剖分
考虑树剖，令 $son_u$ 表示 $u$ 的重儿子
dp转化为
$$
\begin{align}
f_{u,0}&=max(f_{son_u,0},f_{son_u,1})+\sum_{u\to v,v\ne son_u}max(f_{v,0},f_{v,1})\
f_{u,1}&=a_u+f_{son_u,0}+\sum_{u\to v,v\ne son_u}f_{v,0}
\end{align}
$$
记
$$
\begin{align}
g_{u,0}&=\sum_{u\to v,v\ne son_u}max(f_{v,0},f_{v,1})\
g_{u,1}&=a_u+\sum_{u\to v,v\ne son_u}f_{v,0}
\end{align}
$$
从而
$$
\begin{align}
f_{u,0}&=max(f_{son_u,0},f_{son_u,1})+g_{u,0}\
f_{u,1}&=f_{son_u,0}+g_{u,1}
\end{align}
$$
矩阵
我们用重新定义的线性变换来描述这个转移
- 把乘法变成加法
- 把加法变成取max
$$
\begin{bmatrix}
g_{u,0} & g_{u,0} \
g_{u,1} & -\infty
\end{bmatrix}
\begin{pmatrix}
f_{son_u,0} \
f_{son_u,1}
\end{pmatrix}
\begin{pmatrix}
f_{u,0} \
f_{u,1}
\end{pmatrix}
$$
可以自己验证一下
并且可以证明这个这样的矩阵乘法是具有结合律的
需要求一个点的dp值的时候，只需要将这个点走重儿子走到底的矩阵乘起来就好了
考虑到一个点跳到根只会经过 $\mathcal O(\log n)$ 条轻边，我们用线段树维护矩阵的积，修改的时候反复执行如下操作
- 修改当前点的矩阵
- 跳到重链的顶端，计算dp值，更新父亲的 $g$，并跳到父亲处
单次修改复杂度是 $\mathcal O(\log^2n)$，查询 $\mathcal O(\log n)$
单位矩阵是
$$
\begin{bmatrix}
0 & -\infty \
-\infty & 0
\end{bmatrix}
$$
代码
1 |
|
例题二 动态dp【加强版】
题意
同上
强制在线
$n,m\le10^6$
分析
数据范围要求了更优秀的复杂度，有人会想到 $\mathcal O((n+q)\log n)$ 的LCT，但是LCT实际表现并不理想..
考虑到这里不需要一些link, cut和换根操作，我们可以构造一种类似Link-Cut Trees的静态结构
全局平衡二叉树
概述
像LCT一样，把每条重链用一棵辅助二叉树维护，辅助树之间用虚边连接，重链之间也构成了一棵有根树
每个节点需要维护自己所在的重链的辅助树的子树矩阵积
事实上前面的线段树也是一种类似的结构，只是每棵都保持了绝对的平衡，导致复杂度 $\mathcal O(\log^2n)$
而我们需要找到一种给辅助树定制合适形态的方法，做到全局平衡
构造
定义点 $u$ 的权重 $w_u=size_u-size_{son_u}$，即所有轻儿子的size和+1
构造一条重链的辅助树的时候，令带权重心为根，左右递归构造即可
复杂度
可以证明这样总的一棵全局平衡二叉树的深度是 $\mathcal O(\log n)$ 的
具体可以参考文末的资料1
这样我们只需要在这棵树上向上跳并更新，在跳虚边的时候注意类似的特判（更新父亲的 $g$）
代码
由于是第一次写，这里构造全局平衡二叉树的写法和下面的例题三略有不同
1 |
|
例题三 洪水
题意
你有一棵 $n$ 个点的树，第 $i$ 个点的点权是 $a_i$
有 $q$ 次操作
C x y表示修改第 $x$ 个点的点权为 $y$Q x表示询问删除一些点使得 $x$ 的子树中的每个叶子与 $x$ 不连通的最小代价
其中删除一个点的代价是它的点权，总代价是每个删除的点的代价的和
$n,q\le2*10^5$
分析
dp
考虑静态的dp，令 $f_u$ 表示以 $u$ 为根的子树的答案，有
$$f_u=min(a_u,\sum_{u\to v}f_v)$$
令 $son_u$ 表示 $u$ 的重儿子，则
$$f_u=min(a_u,f_{son_u}+\sum_{u\to v,v\ne son_u}f_v)$$
记$$g_u=\sum_{u\to v,v\ne son_u}f_v$$
特殊地令叶子节点 $g_i=\infty$
则
$$f_u=min(a_u,f_{son_u}+g_u)$$
变换
这可以看做一个变换 $trans_{a,b}(x)=min(a,x+b)$ ，用这种方式可以解决在重链上的转移
一个节点的答案就是这个点到所在重链的底端的变换反顺序作用在 $0$ 上
而两个这样的变换合并后仍然是同样的形式
$$
\begin{align}
&trans_{c,d}(trans_{a,b}(x))\
=&trans_{c,d}(min(a,x+b))\
=&min(c,min(a,x+b)+d)\
=&min(c,min(a+d,x+b+d))\
=&min(min(c,a+d),x+b+d)\
=&trans_{min(c,a+d),b+d}(x)
\end{align}
$$
复杂度
如果用例题一的方法直接线段树维护，可以做到修改 $\mathcal O(\log^2n)$，询问 $\mathcal O(\log n)$
而使用全局平衡二叉树可以做到 $\mathcal O(\log n)$
询问
由于这里的询问不是全局，我们要把重链上深度不比 $x$ 小的所有点的变换合并起来，这在二叉树上走一下就好了
代码
1 |
|
例题四 切树游戏
总结
动态dp还是很神奇的
全局平衡二叉树，zx2003说拿这个卡掉多一个 $\log$ 的不好，那就不好吧..
不过代码大概确实比树剖线段树短
参考资料
杨哲《SPOJ375 QTREE 解法的一些研究》
陈俊锟《〈神奇的子图〉命题报告及其拓展》
基于变换合并的树上动态DP的链分治算法和全局平衡二叉树