qifan AK IOI

· · 题解

题传

显然对于每一个连通块若 \sum_{i=1}^{|S|}a_{S_i}\ne\sum_{i=1}^{|S|}b_{S_i} 无解，否则我们必然珂以构造出一组解（不考虑步数限制）。

上面最后一句话引导我们想到图的连通性是解题要点，冗余的边没用，将图缩小到树，即随便求一棵原图的生成森林，在上面求解。

当一个点满足了 a_i=b_i，我们称其是锁定的，现在考虑一个非常暴力地做法。

对于一棵子树，假设其除了根节点外的点都已经锁定，那么我们不再使用儿子取满足根的条件，而是用子树外所有未锁定的点（当我们只做了子树的时候，这些点显然还是能构成一个连通块）去满足，这里假设根的现状是 a>b （小于同理），具体操作如下：

  1. 从当前根出发进行向外的 dfs，设递归到 x

  2. 每当递归完 x 的一个后继结点 y 之后，将 x 内的值尽可能地推向 y。

  3. 回溯。

特别的，当第二布中 x 为子树的根时，我们将 x 需要减小到的下界从 0 调到 b。

其实这就类似于让所有非锁定结点（相对于根的位置）尽量往后面挪，腾出位置把 a-b 的水排出来。（小于就相当于把所有的水往根聚拢）。

分析：每次都至少会让当前子树的根锁定，在一轮中每个点只会与自己的父亲产生一次交换，因此交换次数（应该是）最多只有 O(n(n-1)) 次的，十分宽裕。

复杂度 O(n^2+m)。

Code