就是各种套路，遇到了就记录一下吧

dp

容斥

硬币购物

题意：有四种钱 \(c_i\)，有数量限制 \(d_i\)，问凑 \(s\) 元的方案数

没有约束就是完全背包，有约束的话就减去已经拿了 \(d_i+1\) 的方案数，然后发现会多减，需要容斥

ds

分治

静态树的三度化

在各种树分治中都还是很常见的，就讲一讲，

一个点 \(u\) 的儿子集合为 \(son_u\)

我们构造若干个虚节点 \(v_1\cdots v_n\)，其中 \(n\) 为 \(son_u\) 的大小

进行重新连边

\[\begin{align*} s_i\in son_u\\ s_i\rightarrow v_i\\ v_{i+1}\rightarrow v_i\\ v_1\rightarrow u \end{align*} \]

也就是搞成一条链的形式，然后把原本的儿子挂到链上，也可以写成线段树一样的递归写法，有时候常数会小一点，不过挺难打的

树上启发式合并

放到分治里面是因为 \(dsu\ on\ tree\) 能够解决的问题和分治类似，并且分析也是差不多

举例

一个大小为 \(n\) 的有根树的点有颜色，求每个子树内有多少不同的颜色，\(O(n)=10^6\)

最暴力的做法是用桶维护答案， \(O(1)\) 求出叶子答案，然后从叶子一路合并到根就做完了，但这样是 \(O(n^2)\) 的

因为只需要答案，所以可以选择直接继承重儿子的桶用来存答案，然后发现一个点的合并次数等于其到根路径上的轻边数，于是就是 \(O(n\log n)\) 了