P1552 [APIO2012] 派遣
每个点作为管理者，只需要计算其子树内，最多有多少个人加起来不大于 \(M\)，考虑维护前 \(k\) 小的元素。
可以使用左偏树合并。
然而其实可以平衡树合并，每次在平衡树上二分。
P2685 [TJOI2012] 桥
首先，Boss 镇守的桥一定是最短路上的边，使得我们不得不改变线路。
考虑对于每条非最短路的路径，如果走了这条，是哪些边可能被短掉了？
对于每条边，计算强制经过这条边的最短路。
再维护 \(L_u\) 表示 \(u\)，从 \(1\) 开始走最短路到 \(u\)，最多与 \(1\to n\) 的最短路重合到第几个点。
\(R_u\) 表示从 \(n\) 开始，同理。
\(L_u,R_u\) 可以用 BFS 维护。
那么 \([L_u,R_u]\) 这个区间里的边被断掉，就可能走这条路。考虑区间求 \(\min\) 用线段树维护。
P3160 [CQOI2012] 局部极小值
考虑从小到大加入数，如果一个点是局部极小值，那么在其加入之前不能周围有数。
发现局部最小值的位置也最多 \(8\) 个，可以对其状压 dp，维护的是当前放了多少数，有哪些局部最小值被放了。
但是我们这样求的话，不能保证一个非局部极小值的点不是局部最小。
可以容斥，设当前有 \(x\) 个局部最小值，那么减去 \(x+1\) 方案数，加回 \(x+2\) 方案数......
加的那些局部最小值位置可以随便填，考虑 dfs 求出所有方案。