2A
题意：\(1\sim n\) 排在数轴上，定义 \(con_{i, j} =[i, j\text{ 直接或间接连通}]\)，当前局面的代价为 \(\sum_{i < j} con_{i, j} \times a_{j - i}\)。
初始连满 \(\frac{n(n - 1)}{2}\) 条边，求恰好删去 \(0, 1, \cdots, \frac{n(n - 1)}{2}\) 条边后的最小代价。\(n \le 100, a_{i} \le a_{i + 1}\)。
在一个大小为 \(m\) 的连通块中，不管是 \(m - 1\) 条边还是 \(\frac{m(m - 1)}{2}\) 条边，其贡献都是一样的。
注意到 \(a\) 单调不降，连通块一定是一段连续区间，否则不优，调整法证明。
设前 \(f(i, k)\) 表示前 \(i\) 个点中恰好连了 \(k\) 条边的最小代价，\(f(i, k) \gets f(i - 1, k)\)。
考虑用 \(i\) 所在连通块转移，枚举左端点 \(j\)，新增代价 \(w = \sum_{l} a_l \times (m - l)\)，新增边数 \(d \in [m - 1, \frac{m(m - 1)}{2}]\)。
\(f(i, k) \gets w + \min f(j - 1, k - d)\)，st 表预处理能做到 \(O(1)\) 转移。时间 \(O(n^4)\)，空间 \(O(n^3\log n)\)，不是很牛。
对于每个方案，我们都可以将其连通块中的边连满，但代价不变。
\(f^\prime(i, k)\) 表示前 \(i\) 个点恰好连 \(k\) 条边，且每个连通块边都连满的答案，\(f^\prime(i, k) \gets w + f^\prime(j - 1, k - \frac{m(m - 1)}{2})\)。
由于 \(f\) 是单调不降的，\(f(k)\) 的方案一定能对应到某个 \(f^\prime(l > k)\) 的方案，有 \(f(k) = \min_{l \ge k} f^\prime (l)\)。
1A
题意：\(n\) 个点 \(q\) 次操作，\(1 \le n, q \le 10^5\)。
- 连接 \(u, v\)，数据保证无重边自环。
- 给定 \(k\)，每次可以删掉度数不大于 \(k\) 的点，求可以删多少点（没有真删点，无后续影响）。
考虑最终局面的几种情况：
- 所有点都被删掉。
- 留下 \(r > k\) 个点，注意任意 \(i\) 满足 \(d_i >k\)，即边数是 \(O(k^2)\) 的，\(k\) 是 \(O(\sqrt m)\) 的。
对于 \(k > O(\sqrt m)\)，答案一定就是 \(n\)。
对于 \(k \le O(\sqrt m)\)，考虑暴力怎么做：类似拓扑排序，不断删掉度数 \(\le k\) 的点并更新度数。
加边不好处理，删边好处理，把 \(k\) 相同的询问按时间轴从后往前一起处理，时间复杂度 \(O((n + q)\sqrt q)\)。
B
洛谷P7830，强制在线。
C
CF1033F，加强了数据范围。