题解【P6122 [NEERC2016]Mole Tunnels】
传送门。
$\texttt{Description}$
有一棵 $n$ 个节点的完全二叉树，第 $i$ 个点最多贮存 $c_i$ 只鼹鼠，有 $m$ 只鼹鼠依次醒来，对于 $\forall k\in[1,m]$ 输出前 $k$ 只鼹鼠醒来后最少的运动长度总和。
$1\le n\le 10^5$。
$\texttt{Solution}$
考虑暴力建图：
- 从 $s$ 向每只鼹鼠睡觉的地方连一条容量为 $1$，费用为 $0$ 的边。表示有 $1$ 只鼹鼠在某个洞里。
- 对于树上一个点，连向它能到达的点，容量为 $\infty$，费用为 $1$。表示一条边可以经过多只鼹鼠，但是需要一个单位的长度。
- 每个点向 $t$ 连一条容量为 $c_i$，费用为 $0$ 的边，表示一个终点的容量。
但这样建图是 $\Theta(nm)$ 的，边数也是 $nm$ 级别的，显然 $\text{TLE}$。
那么唯一的办法，就是用摸你肺用流的思路来优化。
考虑加入了第 $i$ 个点，$s$ 与前 $i-1$ 个点之间的流量肯定是满流了，因为不会有无解的情况，所以每个点都到达相应的目的地。
回顾最小费用最大流的代码，现需要找到一条从 $s\to t$ 的增广路。
而只有点 $i$ 满足 $s$ 与 $i$ 的残余流量非 $0$，所以只需要找到 $i\to t$ 的增广路。也就是距离 $i$ 最短，并且还有食物的点。
考虑 $\texttt{DP}$。
我们设 $f_i$ 表示第 $i$ 个点到它为根的子树中的一个还有食物点的最近点的距离，$g_i$ 表示相应的点的编号。
子树外的点是无法进行 $\texttt{DP}$ 的，但是我们可以暴力向上跳父亲，因为这是一棵完全二叉树，树高是 $\log n$ 的。所以对于每一个父亲 $j$ 将 $f_i$ 对 $f_j$ 进行更新。复杂度是 $\Theta(\log n)$ 的。
第一步，我们先找到距离 $i$ 最近的点，设为 $v$，并求出 $v$ 对应的 $i$ 的祖先 $u$，累计路径距离。
之后对于 $i\to u$ 路径上的所有边容量减一，并暴力修改 $f$ 和 $g$ 的值。当然 $v\to u$ 路径上也应该进行相应的修改，只不过流量加一，因为我们这里走的是反向边。
最后暴力从 $u$ 跳根修改即可。