BZOJ2395 [Balkan 2011]Timeismoney
BZOJ 分析 我们可以把每棵生成树的 $\displaystyle\sum_{e\in T}a_e$ 和 $\displaystyle\sum_{e\in T}b_e$ 看做二维坐标 $(x,y)$ 。于是我们就相当于要找一个 $x\times y$ 最小的点。 这个东西可以分三步求： 求出与 $x$ 轴和 $y$ 轴最近的点 这个还是很简单的。 把 $a_i$ 作为边权，求出的最小生成树...
BZOJ 分析 我们可以把每棵生成树的 $\displaystyle\sum_{e\in T}a_e$ 和 $\displaystyle\sum_{e\in T}b_e$ 看做二维坐标 $(x,y)$ 。于是我们就相当于要找一个 $x\times y$ 最小的点。 这个东西可以分三步求： 求出与 $x$ 轴和 $y$ 轴最近的点 这个还是很简单的。 把 $a_i$ 作为边权，求出的最小生成树...
Luogu 分析 对修改时间分治，假设当前的时间区间是 $[L,R]$。 考虑以下两种操作： 把 $[L,R]$ 中要修改的所有边修改成 $-\infty$，然后求一遍最小生成树。 发现，如果一条非 $-\infty$ 边在最小生成树中，那它以后一定也在最小生成树中，所以可以把它先加进去。于是可以把所有这样的边形成的连通块缩成一个点。 把 $[L,R]$ 中要修改的所有边修改为$\i...