自动搬运

查看原文

来自洛谷，原作者为

	tommymio Cruel world

搬运于2025-08-24 22:27:12，当前版本为作者最后更新于2021-03-05 19:38:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

两种做法。一种 $O(n \log n)$，另一种是 $O(n)$。

这个题显然考虑贪心。每次从连通块大小不为 $1$ 的连通块中删去一个最大的点是最优的，因为我们希望权值大的点尽可能少的被计入答案。那我们逆序模拟这个过程就好了。具体来说将所有点按权值从小到大排序，考虑加入每个点 $x$ 和它的连边，如果它的出边指向的 $y_i$ 已加入，那么就合并 $x$ 与 $y_i$ 所在的连通块。这个过程中使用 $\text{dsu}$ 维护连通块权值最大值即可。算法瓶颈在排序处 $O(n\log n)$。

第二种做法更有意思一点。我们尝试把贪心得到的值写成一个表达式：

$$\sum_{i=1}^n t_i-\max_{1\leq i\leq n} t_i+\sum_{i=1}^{n-1}\max(t_{x_i},t_{y_i}) $$

证明如下：考虑任意一棵子树 $T$，第一个删除的点是 $T$ 中的 $x$ 点，它在 $T$ 中权值是最大的。那么，设 $id_i$ 为以 $i$ 为根的子树内取到点权最大值的点的编号，则删去 $x\to y_k$ 这条边的花费为 $val_x+val_{id_{y_k}}$。我们注意到 $val_x$ 会作为边上两点权值 $\max$ 被计入答案，并且每个 $T$ 内的点只会以非 $\max$ 的形式被计入一次（举例：处理以 $id_{y_k}$ 为根的子树统计答案时不再会将 $x$ 与 $id_{y_k}$ 以非 $\max$ 的形式计入）。于是证毕。

直接计算此式即可。时间复杂度为 $O(n)$。

此处只贴上第一种做法的代码，第二种这么简单大家都会写吧（

#include<cstdio>
#include<vector>
#include<algorithm>
typedef long long ll;
int cnt=0;
std::vector<int> vec[100005];
int maxn[100005],vis[100005],fa[100005],id[100005]; 
inline int read() {
	register int x=0,f=1;register char s=getchar();
	while(s>'9'||s<'0') {if(s=='-') f=-1;s=getchar();}
	while(s>='0'&&s<='9') {x=x*10+s-'0';s=getchar();}
	return x*f; 
}
inline int max(const int &x,const int &y) {return x>y? x:y;}
inline int find(int x) {return x==fa[x]? x:fa[x]=find(fa[x]);}
inline bool cmp(int x,int y) {return maxn[x]<maxn[y];}
int main() {
	int n=read(); ll ans=0;
	for(register int i=1;i<=n;++i) maxn[i]=read(),fa[i]=id[i]=i;
	std::sort(id+1,id+1+n,cmp);
	for(register int i=1;i<n;++i) {int x=read(),y=read(); vec[x].push_back(y); vec[y].push_back(x);}
	for(register int i=1;i<=n;++i) {
		int x=id[i]; vis[x]=1;
		for(register int k=0;k<vec[x].size();++k) {
			int y=vec[x][k]; if(!vis[y]) continue;
			int fx=find(x),fy=find(y);
			if(fx!=fy) {
				ans+=maxn[fx]+maxn[fy];
				maxn[fx]=max(maxn[fx],maxn[fy]);
				fa[fy]=fx;
			}
		}
	}
	printf("%lld\n",ans);
	return 0;
}