A simple Blog for wyx I've been down the bottle hoping.
基于变换合并的树上动态 DP 的链分治算法学习笔记
发表于: | 分类: Oi | 评论:0 | 阅读:86

写在前面

这是一篇有关链分治算法的学习笔记……我完全就是照着 immortalCO 论文和 他的博客 里面写的学的

先丢链接immortalCO ,论文的话直接去uoj找17年的集训队论文就好了

不保证都能看懂,不保证看了之后都会…… 建议读不懂论文的可以上这看看有没有启发


大家都做过不少树形dp了吧,但是通常都是静态的dp,我们来先举个栗子

经典例题1 树上最大权独立集

  • 给定一棵树,每个点有点权,要求不能选择相邻的两个点,求选择点的权值的最大和

  • $n \le 10^5 $

这题都会做吧……

$f(x)$ 表示 $x$ 选择 $x$ 并且子树合法得到的权值的最大和

$g(x)$ 表示 $x$ 不选,并且子树合法得到的权值的最大和

$$f(x) = val_x + \sum \limits_{p\in son_x} g(p), g(x) = \sum\limits_{p \in son_x} max(f(p), g(p))$$

对这就是普及组水平题目了,那么我现在加上这样一个操作

  • 修改一个点的点权

还有这种操作?

好像每次都重新做一次肯定是GG了……

先考虑一个序列怎么做,那显然就是一个傻逼线段树就搞完了

对于一段区间我们考虑维护一个二元组$ans(a,b)$其中$a+b\le 2$,为1表示改端点要被选择,为0则表示该端点不被选择,然后考虑合并区间的时候就直接$2^2$枚举$mid,mid+1$的状态$x,y$,并保证$x+y<2$然后一切就变得傻逼了

那么对于树怎么做呢?

先考虑dp,我们不妨换一个思路,注意到这是dp,那也就是说我只要做完了子树,然后用所有儿子更新了一次,那么这个位置的dp值就是一定的,不随dp的顺序变化而变化,所以我们考虑沿用树链剖分那套理论,优先dp一下重链,每次去掉一条重链,然后考虑分治处理其他的轻链

考虑如何转移,我们按照分治的倒序进行更新即重链链头的深度从大到小的顺序进行更新,在维护的时候我们对于每条重链都开一个线段树,注意到线段维护的时候维护的区间$[l,r]$表示把链取出来从上到下数第$[l,r]$个点的贡献,注意到这个贡献需要算他们的轻儿子

那么显然对于这个东西的更新和序列上的就是完全相同的了

然后考虑如何更新一个轻儿子对线段树上一个单点的更新,注意到我们对于一个单点实际有意义的值就是(0,0)或者(1,1),这两个值其实就是$f(x),g(x)$貌似我们没有办法获取有关轻儿子的信息,但是注意到一个事实:每一个轻儿子实际上都是一个新的重链的链头,那么这个轻儿子的信息直接在他所在的重链上就可以直接获取了

最后考虑一个修改,我们先定位到他所在的重链上,更改这个链的信息,然后更改这个链链头的父亲的信息,然后递归处理上面那条重链上刚才被修改的点,直至修改到根所在重链

一个细节是这个修改的复杂度不能以度数为代价,而要直接计算差量在线段树中直接更新,这样复杂度就是$n\log^2(n)$了。这也就说明这个算法要求维护的信息具有逆运算。

那么如果没有逆运算怎么办?

也非常简单,我们可以对于一个点把它所有的轻儿子再单开出一个线段树,这样就可以直接单点修改一个点,然后依赖线段树的合并操作实现正运算解决问题,注意到这个复杂度其实还是$n\log^2(n)$

至此问题已经被完美的解决。复杂度为$n\log^2(n)$

最后再摸一下immortalCO

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP