zxy 模拟赛

应该是最近质量最高的模拟赛了！

数轴上有 $n$ 个位置，在位置 $i$ 上可以覆盖位置 $[i-p_i,i)$ 或者 $(i,i+p_i]$ ，如果最后位置 $i$ 没有被覆盖则会产生 $a_i$ 的代价，最小化代价和，并输出这个代价。

关键点：我们把未被覆盖的 $a_i$ 看做是用 $a_i$ 的代价覆盖了 $i$ 这个点，那么我们从左到右依次决策，覆盖就变成了一个前缀！

于是就令 $f(i,j)$ 表示我已经决策了前 $i$ 个位置的覆盖，且覆盖了前缀 $[1,j]$ 的最小代价，转移大概长这样：

向右覆盖： $f(i-1,i)\to f(i,i+p[i])$ 。
向左覆盖：枚举这个前缀由 $[j,i)$ 往右覆盖组成， $f(j-1,i-p_i-1)\to f(i,\max(i-1,\max\{p_t+t|t\in[j,i)\})$ 。
覆盖自己： $f(i-1,j)\to f(i,j)$ ， $f(i,i-1)+a_i\to f(i,i)$ 。

每次转移完要取后缀 $\min$ ，这样我们得到了 $O(n^2)$ 的做法。显然只有 $|i-j|\leq 30$ 的状态是有用的，就 $O(np)$ 了。

但是我连 $O(n^2)$ 都没想出来，唉，还是菜了啊！

$n+1$ 个点的图，编号为 $0 \sim n$ ，一共有两类边：

$n$ 条边，小 Y 会给你 $n$ 个整数， $a_1,a_2,\dots,a_n$ , 其中 $a_i$ 表示 $0$ 号节点与 $i$ 号节点有一条边权为 $a_i$ 的边；
$m$ 条边，连接 $u,v$ ( $u,v \in [1,n]$ ) ，长度为 $w$ 。

$q$ 次修改，每次给出两个数 $x,y$ , 表示将 $a_x$ 改为 $y$ ，然后你需要输出最小生成树大小。

首先我们假定二类边是联通的，如果不连通就加入 $+\infty$ 边，那么二类边显然只有 MST 有用。

进一步地，我们考虑对这个图做 Kruskal 的过程，其实可以只维护 $[1,n]$ 的连通性，并记录每个连通块是否与 $0$ 相连，就可以判断某条边是否需要被加入了。换句话来讲，我们只关心二类边的 Kruskal 重构树，只要这个一样那么整个图的 MST 就一样。

那么我们直接把二类边替换成一条 Kruskal 重构树与其一致的链（具体地，对二类边跑一遍 Kruskal，合并两个连通块时将其链首尾相接），问题就变成了：将链划分成若干区间，区间内链上的边连满，还得选出一条边连 $0$ ，求最小代价。

这个就直接记 $f_{i,0/1}$ 表示考虑了前 $i$ 个点，前面的连通块都连 $0$ 了，第 $i$ 个点所在的连通块有/没有连 $0$ 的最小代价，然后动态 DP 了。