CF1633E Spanning Tree Queries
题意
有一个由 $n$ 个点 $m$ 条边组成的无向带权联通图，有 $k$ 个询问.
每次询问给出一个 $x$，对于每一条边，重新定义边权为 $|w-x|$ ($w$ 为原边权)，求新图上的最小生成树的边权和
$n\le 50, m\le 300, k\le 10^7$
题解
发现存在区间使得 $x$ 在区间内变化时，边权和可以表示为 $a+bx$，其中 $a$，$b$ 为常数
这样的区间需要满足的性质是，当 $x$ 在区间内变化时，图上的每条边大小关系都不会改变 (由kruskal，确定最小生成树上有哪些边)，且原边权 $w$ 与 $x$ 的大小关系不会改变 (可以打开绝对值)
显然这样的区间个数是 $\mathcal{O}(m^2)$ 级别的，下面给出证明
我们构造这样的区间
根据上面两个条件，令临界点 $p$ 使得 $\exists i, j$ 满足 $|w_i-p|>|w_j-p|$ 且 $|w_i-(p+1)|\le|w_j-(p+1)|$
或 $\exists i$ 满足 $w_i\ge p$ 且 $w_i<p+1$
即 $p=\lfloor\frac{w_i+w_j-1}{2}\rfloor$ 或 $w_i$
对所有临界点排序，相邻两个临界点 $p_1, p_2$ 之间的区间 $(p_1, p_2]$ 就是我们所构造的区间，显然这样的区间是满足上面条件的
不同的 $p$ 只有 $\mathcal{O}(m^2)$ 种，对应的区间个数也只有 $\mathcal{O}(m^2)$ 个
按证明中的构造方法构造出所有区间
对于每个区间，打开边权的绝对值，然后含参跑kruskal，得到 $a+bx$ 形式的答案
查询时二分 $x$ 所在的区间，带入 $x$ 求值即可
总的时间复杂度为 $\mathcal{O}(m^3\log m+k)$
CF1633E Spanning Tree Queries