灾难

算法 : 支配树 + \(lca\)

裸的支配树

code

「AHOI _ HNOI2018」毒瘤

算法 : 虚树 + dp

85分

如果不考虑非树边，那么这道题可以直接求独立集个数。

因为非树边不超过 \(11\) 条，所以可以对非树边进行容斥。强制某条非树边两端的点被选择。然后容斥。

这样复杂度不高，但是过不去。

100分

发现在每次容斥时，只有某些关键点处的转移会改变，关键点之间的转移是固定的。那么考虑先把固定点之间的转移系数求出来。然后建虚树，在虚数上 dp。

设 \(f_{u,0/1}\) 表示 dp 到点 \(u\) , 点 \(u\) 是/否被选择的方案数.

那么显然关键点之间的转移形如 \(\begin{cases}f_{u, 0} = k_{v,0,0}f_{v, 0} + k_{v, 1, 0}f_{v, 1}\\f_{u, 1} = k_{v, 0, 1}f_{v, 0} + k_{v, 1, 1} f_{v, 1}\end{cases}\)

所以关键在于求出转移系数。求系数就和求独立集个数一样了。相当于舍去每个关键点的子树，然后求独立集个数。

code

「SHOI2017」寿司餐厅

算法 : 网络流

这道题是最大权闭合子图。如果选择了 \(d_{i, j}\) 就一定要选它的所有子段，即 \(d_{i, j - 1}\) 和 \(d_{i + 1, j}\) 以及它们的所有子段, 所以需要从 \(d_{i, j}\) 向 \(d_{i, j - 1}\) 和 \(d_{i + 1, j}\) 连边。特殊的如果选择了 \(d_{i, i}\) 会产生 \(a_i\) 的代价。所以 \(d_{i, i}\) 要向 \(val_{i}\) 连边。\(val_{i}\) 的值为 \(-a_i\) . 同时还要向 \(Val_{a_i}\) 连边， \(Val_{a_i}\) 值为 \(ma_i^2\)。然后跑最大权闭合子图就行.

code

「2017 山东三轮集训 Day6」C

没有修改操作

那就是可持久化trie的板子. 把可持久化trie建出来，然后二分就行。

只有 \(xor\) 操作

还是可持久化trie的板子。可以参考异或粽子。

全部

对于 \(And\) 和 \(Or\) 操作。其实是把trie的左右子树合并。有效的合并最多有 \(logx\) 次。所以在存在有效合并的情况下直接暴力重构复杂度正确。