直接说每次把每条边上都放最小的 $S$ 个守卫然后去掉 $S$ 最小点，合并边来递归不太合理。

首先递归后并不是一个形式完全相同的子问题，其次那样不好说明为什么最优的肯定是一颗树。

这里主要是写了题中结论的证明，对于具体代码实现写的比较简略。

结论

定义 $S_{\max}$ 为所有点 $S$ 的最大值，$S_{\min}$ 为所有点 $S$ 的最小值，$L(s)$ 为所有 $S_u<s$ 的点的导出子图，$f(G)$ 为图 $G$ 的连通块数量。

在不考虑加删边的情况下，有结论

$$ans=\sum\limits_{(u,v)\in E} \min(S_u,S_v)+\sum\limits_{i=S_{\min}+1}^{S_{\max}} f(L(s))$$

结论证明

转化

把船 $(u,v)$ 放在 $u,v$ 中 $S$ 小的点旁边，并在船上放 $\min(S_u,S_v)$ 个守卫，然后忽略掉这些守卫。

定义一个守卫在点 $u$ 为守卫所在的船停在 $u$ 旁边，在连通块内即为在连通块内的点上。

对守卫进行分级，按 $s$ 从 $S_{\min}+1$ 到 $S_{\max}$ ，每次考虑 $L(s)$ 中的每个连通块，若其中有剩余守卫则把它的等级赋为 $s$ ，最后剩余的未赋级守卫等级赋为 $+\infty$。

经过边 $(u,v)$ 视为从船上扔下 $S_u-S_v$ 个等级最低的守卫到边上，若为负数视为捡回边上的守卫。

必要性

引理 1

对于 $s\neq +\infty$ ，若两个等级为 $s$ 的守卫在同一个点，其中必然有一个会经过 $S_u\ge s$ 的点。

引理 1 证明

由于赋级方式，任意两个等级为 $s$ 的守卫初始在 $L(s)$ 的不同连通块中。

所以初始不存在上述情况，且两个等级为 $s$ 的守卫间任意路径都要经过 $S_u\ge s$ 的点。

引理 2

等级为 $s$ 的守卫不能走到 $S_u\ge s$ 的点。

引理 2 证明

考虑反证法。

若存在一些等级为 $s$ 的守卫走到了 $S_u\ge s$ 的点，考虑其中 $s$ 最小，操作次数最少的守卫。

它的路径上必然有一条边 $(u,v)$ 满足 $S_u<s,S_v\ge s$。

由于 $s$ 等级最小，点 $u$ 上只能有等级大于 $S_u$ 的守卫。

由于 $s$ 没有在边上被扔掉，扔掉的守卫等级只能在 $[S_u+1,s]$ 内，因此区间内必然有某个等级的守卫在 $S_u$ 上出现了两个。

1. 若此等级小于 $s$ ，由于引理 1，这与 $s$ 最小冲突。

2. 若扔掉的守卫等级为 $s$ ，由于引理 1，这与操作次数最少冲突。

引理 3

对于 $s\neq +\infty$ 一个点上至多只能有一个等级为 $s$ 的守卫。

引理 3证明

由于引理 1 和引理 2，显然成立。

必要性证明

若人数小于结论中 $ans$ 必然存在一个 $s\le S_{\max}$ 使得 $L(s)$ 中某个连通块内没有等级大于等于 $s$ 的点。

根据引理 3，到块外点 $v$ 前一步所在的点 $u$ 上，只能有 $s-S_u-1$ 个守卫，数量小于 $s-S_u$ 小于等于 $|S_v-S_u|$ ，所以必须有块外守卫进块才能把客人送出块。

但块外守卫进块需要先有船从块内走到块外点旁边，这在没有块外点进块时是不可行的。

充分性

引理 4

用一组操作把乘客从 $u$ 送到 $v$ 后，可以不动乘客的反过来进行操作（顺序和边走向均取反），把守卫位置还原，称反过来进行的操作为逆操作。

引理 4 证明

由于转化方式，操作合法的充要条件为过程中经过某个点时护卫人数始终大于等于 $0$ ，因此引理 4 显然成立。

引理 5

若可以把乘客从 $u$ 运送到 $v$ 则 $v$ 到 $u$ 也可以。

引理 5 证明

先不送乘客，进行 $u$ 到 $v$ 的操作 ，之后在 $v$ 接上乘客再进行引理 4 中逆操作并在 $u$ 放下乘客。

引理 6

只要连通块中有一个生成树中任意一条边 $(u,v)$ 都能从 $u$ 护送乘客到 $v$ 或反过来，连通块内任意起点终点就都可以护送客人从起点到终点。

引理 6 证明

根据引理 5 和引理 4，任意两点按树上路径每次走边后逆操作回去不改变守卫分布即可继续走。

充分性证明

放置守卫的策略为将 $s$ 从 $S_{\min}+1$ 推到 $S_{\max}$ 的过程中每次对 $L(s)$ 的每个连通块，选择任意一个块内点放一个守卫。（即放在该点旁边的一个船上。）

归纳证明这种策略下 $L(s')$ 中一个连通块内任意两点间只用等级小于 $s'$ 的守卫即可互达。

$s'=S_{\min}+1$ 时所有连通块都为单点，显然成立。

根据引理 6，从 $s'$ 推到 $s'+1$ 时只需考虑 $S_x < s', S_y=s'$ 且 $x$ 和 $y$ 之间有边的点对 $(x,y)$ 是否可行。

进行构造。

将 $s$ 从 $s'$ 推到 $S_x +1$ 的过程中每次把和 $x$ 一个连通块内的任意一个等级为 $s$ 的守卫当作客人护送到 $x$。

由于归纳条件，用等级小于 $s$ 的护卫就可以到达 $x$，然后用引理 4 中逆操作还原。

因为等级小于 $s$ 的守卫位置不变，可以确保归纳条件在等级小于 $s$ 时仍成立。

此时 $x$ 上已有等级在 $[S_x+1,s']$ 的守卫各一个，可以直接从 $x$ 走到 $y$。

图 $\rightarrow$ 树

只保留增大 $s$ 时改变图连通性的边，相当于保留以 $\max(s_u,s_v)$ 为边权的最小生成树，则图变为一颗树，且答案后一半不变，前一半变小。

这个调整方式不一定最优，这个的后一半贡献最优，但前一半贡献可能可以更小。

算贡献

考虑把 $S$ 最大的点当根，把 $\min(S_u,S_v)$ 的贡献算在深度较浅点上，把连通块的贡献算在其中深度最浅点的父节点上，则点 $u$ 的贡献为 $S_u$ 乘以 $u$ 的子节点个数。

贡献被转化为

$$\sum\limits_{i=1}^{n} S_i\times (deg_i-1)+S_{\max}=\sum\limits_{i=1}^{n} S_i\times deg_i-\sum\limits_{i=1}^{n} S_i+S_{\max}$$

这个形式直接把第一个求和的贡献放在边上，转化为边 $(u,v)$ 有 $S_u+S_v$ 的贡献。

贪心

记添加 $k$ 条边后可以得到的树为 $k$-ST， 其中权值和最小的为 $k$-MST ，原图中存在的为旧边，新添加的为新边，两颗树的距离为将一颗变为另一颗所需添加或删除边的数量。

设 $X$ 为任一 $k$-MST， $Y$ 为与 $X$ 距离最短的 $(k-1)$-MST， 它们之间距离小于等于 $2$。

引理 7

对于任意两颗树 $X,Y$ ，设 $e\in X\setminus Y$ ，存在 $f\in Y\setminus X$ 使得 $X-e+f$ 和 $Y-f+e$ 都是树。

引理 7 证明

设 $X$ 中断开 $e$ 后会形成两个连通块，点集分别为 $S,T$ ，则引理相当于 $f$ 中 $e$ 两端点的路径上存在一条边 $(u,v)$ 满足 $u\in S, v\in T$ ，由于 $e$ 中两端点分别属于 $S$ 和 $T$ ，显然存在这条边。

贪心证明

由于引理 7，考虑在 $X$ 中取一条 $Y$ 中没有出现的新边 $e$ ，则会对应一个 $f$。

若 $f$ 为新边，则 $X-e+f$ 仍为 $k$-ST ，$Y-f+e$ 仍为 $(k-1)$-ST。

1. 若边权不相等，两者中有一个调整后比调整前优，与 $X,Y$ 都为 MST 冲突。

2. 若边权相等，调整 $Y$ 为 $Y-f+e$ ，所需修改边数变少，与距离最短冲突。

因此 $f$ 为旧边，有 $X-e+f$ 为 $(k-1)$-ST，$Y-f+e$ 为 $k$-ST ，若 $X-e+f$ 不为 $(k-1)$-MST ，则 $Y$ 的权值和小于 $X-e+f$ ， $Y-f+e$ 权值和小于 $X-e+f-f+e$ ，小于 $X$ ，与 $X$ 为 $k$-MST 冲突。

$X-e+f$ 为 $(k-1)$-MST ，其与 $X$ 距离显然为 $2$。

实现

显然 $k\ge n-1$ 时树为以 $S$ 最小点为中心的菊花，若新边可以加在旧边的位置，对于 $k\le n-1$ ，从 $k$ 到 $k-1$ 必然删一条新边，加一条旧边。

每次选择权值最小的方式即可，枚举删的新边分裂为两个连通块，加的旧边必然是两个连通块间权值最小的边。

用一个堆维护删每条新边答案增加量，$n$ 个堆维护删每条新边后不包含 $S$ 最小值点的连通块往外连的所有边，从 $k$ 推到 $k-1$ 时维护堆的变化即可，用延迟删除的方式维护比较好。

代码

#include<bits/stdc++.h>
#define pii pair<int, int>
#define mkp make_pair
#define ll long long
using namespace std;
const int maxn=2e5+5;
int n,m,q,rt,mx,fa[maxn],s[maxn];
priority_queue<pii> PQ,pq[maxn];
ll ans,prt[maxn];
int get_fa(int x)
{
	if(x==fa[x]) return x;
	return fa[x]=get_fa(fa[x]);
}
inline bool check(int x,int y)
{
	return get_fa(x)!=get_fa(y);
}
inline int calc(int x)
{
	return -pq[x].top().first-s[x]-s[rt];
}
void merge(int x,int y)
{
	x=get_fa(x),y=get_fa(y);
	fa[x]=y;
	if(pq[x].size()>pq[y].size()) swap(pq[x],pq[y]);
	while(!pq[x].empty())
	{
		pq[y].push(pq[x].top());
		pq[x].pop();
	}
	while(!pq[y].empty() && !check(y,pq[y].top().second)) pq[y].pop();
	if(!pq[y].empty() && get_fa(rt)!=y) PQ.push(mkp(-calc(y),y));
}
int main()
{
	int u,v;
	pii tp;
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++) cin>>s[i];
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v;
		pq[u].push(mkp(-(s[u]+s[v]),v));
		pq[v].push(mkp(-(s[u]+s[v]),u));
	}
	s[0]=2e9;
	for(int i=1;i<=n;i++)
	{
		mx=max(mx,s[i]),fa[i]=i;
		if(s[rt]>s[i]) rt=i;
	}
	for(int i=1;i<=n;i++)
		if(!pq[i].empty() && i!=rt) PQ.push(mkp(-calc(i),i));
	ans+=1ll*s[rt]*(n-2)+mx;
	for(int i=n-1;i<=q;i++) prt[i]=ans;
	for(int i=n-2;i>=0;i--)
	{
		while(pq[PQ.top().second].empty() || PQ.top().first!=-calc(PQ.top().second)) PQ.pop();
		tp=PQ.top();
		PQ.pop();
		ans-=tp.first;
		merge(tp.second,pq[tp.second].top().second);
		prt[i]=ans;
	}
	for(int i=0;i<=q;i++) cout<<prt[i]<<'\n';
	return 0;
}

提示：本文中所有图片使用 GitHub Pages 托管，如果网络不好可能要使用一些特殊手段才可以看到。

题意

给定一个 $N$ 个岛屿 $M$ 条船的图，每条船双向连接两个岛屿。第 $i$ 个岛屿有一个不安全值 $S_i$。

每时每刻有若干守卫出现在船上，并且必须满足安全法则：对于任意岛屿，停靠在其旁边的船的守卫数量均不少于它的不安全值。

而守卫的分配必须满足：对于任意起点 $s$ 和终点 $t$，从 $s$ 到 $t$ 存在一种经过若干条船的方案，使得每时每刻船上守卫的数量均满足安全法则。在一个岛屿，守卫可以自由地从某个岛屿停靠的一条船来到该岛屿停靠的另一条船。

你需要对于任意的 $k$（$0 \leq k \leq Q$），给图中增加 $k$ 条船并取消一部分船使得岛屿之间仍然连通，船连接的两个岛屿可以任意分配。你需要最小化所需要的守卫数量总和并求出这个值。

子任务 1

先考虑 $1 \leq S_i \leq 2$，$Q = 0$，且所有船形成一条链的情况。在 $Q = 0$ 时，我们只需要考虑守卫的分配即可。

显然每时每刻每艘船的守卫数量都至少为 $1$。不妨令全局减少一个守卫，即 $S_i$ 变为 $0$ 或者 $1$。注意到如果一个岛屿的不安全值变为 $0$，那么这个岛屿可以直接忽略（因为船到达这个岛屿不影响船上的守卫数量，也不可能产生船无法通行的情况），并且连续的船可以视为一条。

此时链上所有岛屿的不安全值均为 $1$，那么只需要为所有船再分配一个守卫即可。

注：图中圆圈表示一个岛屿，其中数字表示不安全值；蓝色的图形表示船，其中数字表示当前方案为其分配的守卫数量。

子任务 2

考虑去掉 $1 \leq S_i \leq 2$ 的限制，这时思路是类似的，每次找出不安全值最小的岛屿，就可以全局减去这个值并统计答案，并忽略一部分不安全值变为 $0$ 的岛屿。

根据上图观察可以发现，非两端的位置 $i$（$1 < i < N$）会对答案产生 $S_i$ 的贡献。此外，最后剩下的一个最大值会对答案产生额外第一份贡献。所以此时的答案就是 $\sum\limits_{i=2}^{n-1} S_i + \max\limits_{i=1}^n S_i$。

子任务 3

考虑把上述做法推广到所有船形成一棵树的情况。

取出不安全值最小的一个岛屿之后，仍然按照之前的做法全局减去这个最小值并计算对答案的贡献。这时候要注意的一点是，该岛屿相连的船需要被合并为同一条船，这条船可以使 $d(i)$ 个岛屿两两连通，在后面的计算中也只会对答案产生一次贡献。

于是只需要维护当前船的数量即可。把岛屿按照不安全值从小到大排序依次处理，设船的数量为 $C$，则每次对答案的贡献为 $C \times (d(u) - 1)$，并把当前船的数量减去 $d(u) - 1$ 条即可。

把贡献平摊到所有岛屿上，容易发现岛屿 $u$ 会对答案产生 $(d(u) - 1) \times S_u$ 的贡献。以及最后剩下的最大值会对答案再次产生一份贡献。

子任务 4

现在忽略给定的船形成一棵树的条件，那么我们就需要取消一部分的船。因为少取消一条船就会使得守卫数量更大，所以此时存在一种最优秀的方案只需要考虑一棵生成树。

考虑怎么找出这样一棵生成树。考虑把子任务 3 中的答案式进行转化，把贡献转化到边上，即 $\sum\limits_{(u,v) \in E}(S_u + S_v) - \sum\limits_{i=1}^n S_i + \max\limits_{i=1}^n S_i$。于是我们只需要令边权为两个端点的 $S$ 值的和，求出最小生成树即可。

子任务 5 & 6

接下来考虑 $Q \neq 0$ 的情况。这时需要加上 $k$ 条边，然后选出一个最小生成树。从 $k = k_0$ 变为 $k = k_0 + 1$ 时，加上的边变多了一条。

显然 $k$ 的值从 $k_0$ 变为 $k_0 + 1$ 时，一定存在一种最优秀的方案只需要修改 $k = k_0$ 时最优解的一条边。

于是只需要每次贪心地找出最优秀的修改方案即可。以 $S$ 值最小的结点为根进行深度优先搜索，钦定一条边为删掉的边，那么需要加上的边的一个端点一定是根结点，另一个端点必须在删掉的边对应的子树中，找出子树中 $S$ 值最小的结点即可。时间复杂度 $\Theta(n^2)$。

子任务 7

考虑优化，把整个过程倒过来做。初始状态显然是以 $S$ 值最小的结点为中心的菊花图，接下来每次删除一条边再加上一条原图中给定的边。

每次删除一条边，整个图变为两个连通块，只需要找一条原图中连接这两个连通块的边权最小的边添加即可。具体实现可以对每个结点维护一个 std::priority_queue 表示还未与该结点合并的结点中，原图中的边的边权以及对应的另一个结点编号。再维护一个 std::set 表示所有连通块之间加边删边的净贡献。使用并查集维护连通块，合并时使用启发式合并即可做到时间复杂度 $O(n \log^2 n)$。