[链分治 + FWT ] LOJ#2269 [SDOI2017]切树游戏

学习自 这里

可以想到看成有根树之后,设 \(f(i,j)\) 表示 以 \(i\) 为根的子树,权值异或和为 \(j\) 的方案数。合并两个子树的 \(f\) 就是异或卷积,设 \(F_i=f(i,*)\) ,则 \[ F_i=x^{v_i}*\prod (F_{ch(i)}+x^0) \] 为了统计答案,设 \(h(i,j)=\sum_{k \in tree(i)} f(k,j)\) ,能维护 \(h\) 就能询问了。设 \(H_i=h(i,*)\) ,有 \[ H_i=F_i+\sum H_{ch(i)} \] 考虑如何实现修改单点权,快速维护这些信息。

这里有一种方法,就是所谓基于变换合并的树上动态 DP 的链分治算法

Read More

插头DP——学习笔记

插头DP

状压 \(DP\) ,用于处理棋盘上的路径这类的问题。 所谓插头,就是在 \(DP\) 中被轮廓线所截的边界上的路径端点。

可以发现,在轮廓线上方的都是一个一个没有交叉的倒 \(U\) 形的路径,这表明插头之间是两两配对的。可以用括号序列表示一个状态。

Read More

仙人掌相关

基础

定义:每条边至多在一个简单环上的图。仙人掌是特殊的图,但没有树特殊,需要考虑环。

我们把一个环中 \(dfn\) 最小的点叫做环的根。

子仙人掌:以 \(r\) 为根的仙人掌上的点 \(p\) 的子仙人掌是从仙人掌中去掉 \(p\)\(r\) 的简单 路径上的所有边之后,\(p\) 所在的连通块

Read More