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 ...