整体dp学习笔记

· · 个人记录

神仙东西。例题会补上更多的。

对于一类每次给出一个特殊点集，求一些东西的树上dp问题，其中只有特殊点处的dp转移方程不同，其它点处转移完全相同，我们就可以考虑离线询问，使用线段树合并批量进行转移。下面给几道例题。

另外，广义地说，整体dp指的是，对于一类有大量相同或者说相似转移的dp，把dp的一维换成线段树(这一维可能是dp数组的一维，也可能是时间的一维)，用线段树批量处理相同的转移。

[SDOI2011]消耗战

考虑设dp(u)表示使u这个点和子树内所有特殊点断开的最小代价，枚举每个儿子，容易写出转移方程 :

若u的儿子v是关键点，那么dp(u)加上w(u,v)；

否则，dp(u)加上\min(w(u,v),dp(v))。

如果我们现在拿着所有询问的dp值组成的一个数组，那么发现如果一个儿子没有成为过特殊点，它的转移就是一个全局取\min并全局加；如果它成为过特殊点，我们可以单独转移它成为特殊点的那几次——因为这样的转移只有O(\sum k)次。使用线段树合并容易处理这两种操作。

具体怎么处理呢?

首先，这里的线段树仅仅是一个分治结构，而不是什么维护区间结合律信息的数据结构，它存在的意义就是利用 结构都相同 和 深度O(\log n) 来支持快速的单点修改和合并两个操作。

合并的时候，因为我们只关心叶子的信息也就是dp值，所以可以只考虑叶子，上面的都不用管。考虑如果两棵线段树上有一棵有某个叶子u，而另一棵没有，那么这个u的dp值应该没有变化，所以合并的时候不用管它，实际上我们的线段树合并算法确实不会管它；

如果两棵上都有u，那么我们应该进行一个转移，我们记录这个dp值是属于哪一种转移，然后由于合并算法确实会走到这里，我们走到这里再执行转移就好了。这里我的实现方法是先处理特殊转移，然后给这些特殊的叶子打标记，线段树合并时，走到它们就不再转移。

然后考虑这个题的加操作很简单；取\min操作，实际上并不需要搞吉老师线段树做全局取\min，我们可以直接打一个标记来搞定。最后走到根时，我们把根的线段树推一遍标记就能得到答案。注意合并和插入的时候都要处理好标记。

有的朋友可能会问，如果有一个方程，对于空结点的转移并不是什么也不做，那么我们该怎么办呢?实际上我们可以在线段树合并中一边走到空节点的时候给另一边打一个标记，这个技巧后面咕咕咕的例题会涉及。

代码先咕咕咕。

[NOIP2018]保卫王国

可以直接使用ddp的转移矩阵，用线段树维护一个每一位都是矩阵的dp数组。注意这次空节点不能不处理了，我们需要按照之前说的方法，不取特殊点地dp一遍，求出每个点子树内没有特殊点情况下的dp值，然后用这个来打标记。

当然也可以不用矩阵，直接进行转移。

[HNOI2014]世界树

我还不会，等我再想一想。