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\) 用线段树维护。。