竟然朋友之间可以传递故事，那么，我们设两两有间接或直接的朋友关系的为一个友好集合，那么我们只要每一个友好集合买一次就好了。

那应该怎么买呢？由于题面让我们求的是【最少的价钱】，那我们可以考虑每一个集合让出钱出的最少的来买。

现在我们就要找一个数据结构维护这个集合了，需要支持：

• 连边(朋友之间）
• 找出钱出的最少的。

（我为什么想到了LCT?)

如果我们每一次连边都满足出钱少的连向出钱多的，那么就可以用并查集来维护了！

最后统计答案，只需要扫一遍，对于每一个人，如果他所在的集合中出钱最少的还没有买，那么就买。

总时间复杂的 \(O(n+m\log n)\)（并查集使用路径压缩优化）

#include <bits/stdc++.h>
#define int long long
using namespace std;

int a[1000005];

namespace UnionFind{
    int fa[1000005];
    int find(int x){
        if(fa[x]==x)return fa[x];
        else return fa[x]=find(fa[x]);
    }
    void merge(int x,int y){
        if(a[find(x)]>a[find(y)]){
            fa[find(x)]=find(y);
        }
        else{
            fa[find(y)]=fa[find(x)];
        }
    }
}

int n,m;
int isroot[1000005];
int ret=0;

signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        UnionFind::fa[i]=i;
    }
    for(int i=1,liwenx,daniel2020;i<=m;i++){
        cin>>liwenx>>daniel2020;
        UnionFind::merge(liwenx,daniel2020);
    }
    for(int i=1;i<=n;i++){
        int rt=UnionFind::find(i);
        if(!isroot[rt]){
            ret+=a[rt];
            isroot[rt]=1;
        }
    }
    cout<<ret;
    return 0;
}

（其实这道题应该评绿，评蓝有点高）