我们知道对于树上背包，若每个结点上只有总大小为 $O(1)$ 的物品，则总复杂度为 $O(n^2)$；若再限制背包大小为 $m$，则总复杂度为 $O(nm)$。

Read More

关于树上背包的上下界优化，当时 fz 推荐我读的是 ouuan 的文章（cnblogs github pages），但是，我现在认为那里面的复杂度证明存在问题。

Read More

Erdos-Ginzburg-Ziv Theorem

对任意 $2n-1$ 个整数，可以从中选出 $n$ 个使得这 $n$ 个数的和是 $n$ 的倍数。

形式化的，对任意 $a_1,\dots,a_{2n-1}\in \mathbb Z$，存在两两不同的 $i_1,\dots,i_n$ 使得：
$$
a_{i_1}+\dots+ a_{i_n}\equiv 0\pmod n
$$

Read More

定义：对任意 $u,v$，存在 $u\to v$ 或 $v\to u$ 的有向图为竞赛图。也可以说是有向完全图。

Read More

广义串并联图指不存在同胚于 $K_4$ 的子图的图，其中，我们称两个图同胚当且仅当这两个图可由同一个图通过边细分变换得到，边细分指删去一条边，新建一个点，并将新点与原边的两个端点连边。

Read More