LOJ分析考虑反着看整个过程,那么相当于每个点有 $y_i$ 只老鼠和 $x_i$ 个洞,所有老鼠都必须进洞。$u,v$ 匹配的代价是 $dep_u+dep_v-2dep_{\operatorname{LCA}(u,v)}$。因此我们开两个堆维护子树中老鼠和洞的 $dep$,每次把儿子的堆合并,然后取堆顶匹配,再把反悔操作加入堆中即可。然而这样并不能保证所有老鼠都进洞,所以我们把老鼠的 $d...
UOJ分析这个东西相当于洞有容量上限和额外代价,因此可以考虑模拟费用流。我们维护两个堆,分别代表洞和老鼠,然后从左往右扫如果当前是老鼠,取出一个代价最小的洞,代价即为 $x+cost$;后面有可能反悔,即让右边的一个洞匹配这只老鼠,所以要向老鼠堆中加入 $-(x+cost)-x$。如果当前是洞,取出一只代价最小的老鼠,代价即为 $y+cost+w$;后面有可能反悔,即让右边的一只老鼠匹配这个...
LuoguLOJ分析至少有 $L$ 个下标相同 $\Longleftrightarrow$ 至多有 $K-L$ 个下标不同。考虑一个费用流模型,即从源点向 $a$ 中所有点连容量为 $1$、费用为 $a_i$ 的边,从 $b$ 中所有点向汇点连容量为 $1$、费用为 $b_i$ 的边,从 $a_i$ 向 $b_i$ 连容量为 $1$、费用为 $0$ 的边,再新建两个点 $C,D$,从 $C$...