点分治优化dp学习笔记

· · 个人记录

参考 : 猫锟的WC2018课件，Pepcy CHEN的HDU5909题解

对于一类树上的连通块dp问题，合并子树(卷积)的复杂度很高，但是插入一个点或者自己跟自己合并(不妨叫它是点积)的复杂度可以接受，那么可以使用点分治来优化。

一个(大概是这一类题中最常见的)例子是连通块上的背包问题。

具体地，如果要对于每个连通块求一个什么东西，我们先考虑强制这个连通块经过根，可以发现在这种情况下，如果一个点在连通块中，那么它的父亲必须也在。所以我们先从根top-down地dfs，对于每个点进行选/不选的决策，如果不选那就copy一份维护dp的数据结构；如果选那就操作维护dp的数据结构，然后dfs儿子；最后把两个数据结构拍起来(点积)，我们就得到了这个点子树内的答案。当然最后要强制选重心。

每个连通块只会在第一次里面某个点被选为重心时统计一次，所以是正确的。

还是放道例题来具体说明罢。(然而只找到树上背包)

HDU5909 Tree Cuting

题意 : n(n\leq 1000)个点的树，点权为[0,m)(m\leq 1000)的整数，对于k\in[0,m)，分别求连通块\operatorname{xor}为k的方案数。时限2s。

考虑树上背包，我们显然可以设dp[u][i]表示以u为最靠上那个点，\operatorname{xor}值为i的方案数，转移就是把儿子们做个背包然后把自己扔进去。但是合并背包的复杂度不太能接受。

发现儿子们的背包合并是个位运算卷积的形式，神们肯定会说我会FWT!好的那么你得到了一个O(nm\log m)的做法，可过了。

但是我不会FWT既然是讲点分治优化dp，肯定要用点分治的方法来做。

考虑这个背包卷积比较困难，但是"点积"非常简单(就是加起来)，要插入一个点也非常简单。于是我们考虑点分治，对于一块 :

设dp[u][i]表示只考虑点u的子树和u到重心的链，每个连通块都包含重心，\operatorname{xor}值为i的方案数。那么如果不选u，就copy一份背包数组；如果选u，就把u插入背包，然后把背包扔给儿子们；最后把copy的背包数组和儿子们的背包拍起来(就是加起来)。这样一直搞到重心，最后把各重心的背包拍起来就是答案了。复杂度O(nm\log n)，常数比起FWT小不少。