12.7 构造：

最优化

1.模拟小样例
2.构造答案上界

构造方案

1.打表，找规律

图论构造

1.限制/操作涉及两个元素，可以考虑建图

强化限制

1.限制太宽松，可以强化限制在逐渐解除限制。

增量法 & 递归构造

1.从1开始逐渐加入元素
2.分治 or 简化为子问题

操作复杂

1.构造简单变化（如交换两元素）
2.组合，得到更容易处理的限制

12.7树

树的重心

1.树中所有点到某个点的距离和中，到重心的距离和是最小的；
如果有两个重心，那么到它们的距离和一样

2.把两棵树通过一条边相连得到一棵新的树，那么新的树的重
心在连接原来两棵树的重心的路径上。

3.在一棵树上添加或删除一个叶子，那么它的重心最多只移动
一条边的距离

1.有绝对值考虑用重心去除

树上启发式合并

树哈希

h_u=1+\Sigma_{v \in E_u} rand(h_v)

树链剖分

点分治 & 点分树

树上dp

12.10 dp选讲

计数

组合计数

1.组合数

2.斯特林数

\cdot 第二类斯特林数：n个不同的球放进m个相同的盒子的方
案数
\cdot 递推公式：
S(i, j) = j \times S(i – 1, j) + S(i – 1, j – 1), 1 \le j \le i – 1。
边界条件为：S(i, i) = 1(0 \le i), S(i, 0) = 0(1 \le i)
\cdot 方幂转下降幂m^n=\sum_{i=0}^{min(n, m)} S(n, i) m^{\underline i}

12.14字符串

弱周期引理:x为周期串，y为周期串，x+y为周期串，则len \le gcd(|x|,|y|)