LOJ分析考虑反着看整个过程,那么相当于每个点有 $y_i$ 只老鼠和 $x_i$ 个洞,所有老鼠都必须进洞。$u,v$ 匹配的代价是 $dep_u+dep_v-2dep_{\operatorname{LCA}(u,v)}$。因此我们开两个堆维护子树中老鼠和洞的 $dep$,每次把儿子的堆合并,然后取堆顶匹配,再把反悔操作加入堆中即可。然而这样并不能保证所有老鼠都进洞,所以我们把老鼠的 $d...
LuoguBZOJLOJUOJ分析神仙题。设 $f_i(x)$ 表示以 $i$ 为根的子树,全部在第 $x$ 秒引爆的最小代价。可以发现这个函数是一个分段函数,每一段都是一个一次函数,并且从左往右斜率递增。考虑子节点的函数合并到父节点时会怎么样。假设子节点与父节点之间的边长为 $l$ ,子节点的函数是 $f_v(x)$ ,父节点的函数是 $f_u(x)$ ,$f_v(x)$ 的最小值在 $[...
LuoguBZOJ(权限题)分析左偏树板子。M操作就是合并两个堆。K操作就是取出堆中最小的数,然后pop()一下。特判一下K操作时Kill了一个已死的人的情况,此时输出0。代码//It is made by M_sea #include <algorithm> #include <iostream> #include <cstdlib> #include ...