地震后的幻想乡
问题就是求出i条边连通图的个数。
考虑斯特林反演，然后转一下期望，由于期望是均匀的，可以把期望转化成排名的期望（离散化），据题目要求还要处理最小生成树，边的排名在最小生成树中可以转化为用k条边联通整个图的概率。
至此，问题已经变成了图的联通性问题（边的选取问题），用一开始的方法计算。
Summer Dichotomy
用2−SAT就可以水过，讲一下二分图做法。
首先无交集肯定无解，所有老师两两有交，就可以任意选组，否则如果我们考虑其中一组的人数为 n1=min，另一组的人数为 n_2 = \max ( l_i )
如果 n_1 < n_2，那么 n_1 增大或 n_2 减小都会导致某个老师无法选组的情况。
那么就可以算出最优的一个 n_1 和 n_2 的选取方案，再根据这个方案对老师进行一次二分图染色判定。
具体地先从只可能被分到某一组的老师开始，如果不是二分图就无解。
Dynamic Shortest Path
将最短路看成DP，维护增量，我们赋值一个新边权:对于一条边(x,y) 我们把它的边权赋值为dis[x]+e[i].w−d[y]。
考虑如何维护，对于变化点，可以用 bfs 处理。
因为更新c条边 所以最短路最多增加c。
邮局 加强版
二维决策单调性推得 O(nk)，证明 ，打表更可做一点。
引入，wqs二分的题目往往有下列特点：
如果不限制选的个数，那么很容易求出最优方案。（所以一般用来优化 dp）
选的物品越多，权值越 大 / 小。
判断能否使用的方法：
打表看 (i,g(i)) 拟合出的图形是凸包。
满足两个特点。
常用第二种方法，感性理解。感觉可以用 \text{WQS} 二分，那就大胆用 \text{WQS} 二分。
变成 1D/1D 后满足决策单调性，用一开始的方法就可以过了。
Game with Strings
比较套路的状压期望。
