题目链接

题面：

题意：
每次选择一个能选择的极大连通块，连通块内的点的权值都大于0。
每次操作使得选择的极大联通块内的所有点的点权值-1。
问使得图上所有的点的点权值全为0，需要进行多少次操作。

题解：

可以发现，并查集每个连通块上的根节点是权值最小的点。那么并查集的每个根节点就是最先减到0，使得这个连通块分裂成多个连通块的点。
f a t h e r x father_x fatherx​是我在合并并查集时，x的父亲节点。如果某个点没有 f a t h e r x father_x fatherx​那么就说明他是这个连通块最小的点。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#include<list>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
//#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=998244353;
const double eps=1e-1;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=100100;
const int maxp=1100;
const int maxm=500100;
const int up=100000;

int head[maxn],ver[maxn<<2],nt[maxn<<2],tot=1;
int f[maxn],b[maxn],id[maxn];
bool ha[maxn],fa[maxn];

void add(int x,int y)
{
    ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}

bool cmp(const int &i,const int &j)
{
    return b[i]>b[j];
}

int fi(int x)
{
    if(f[x]!=x)
        f[x]=fi(f[x]);
    return f[x];
}

int main(void)
{
    int tt;
    scanf("%d",&tt);
    while(tt--)
    {
        int n,m;
        scanf("%d%d",&n,&m);

        tot=1;
        for(int i=1;i<=n;i++)
        {
            head[i]=0;
            f[i]=id[i]=i;
            ha[i]=fa[i]=false;
            scanf("%d",&b[i]);
        }
        sort(id+1,id+n+1,cmp);

        int x,y;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            add(x,y);
            add(y,x);
        }

        ll ans=0;
        for(int k=1;k<=n;k++)
        {
            int x=id[k];
            ha[x]=true;
            for(int i=head[x];i;i=nt[i])
            {
                int y=fi(ver[i]);
                if(!ha[y]||y==x) continue;
                f[y]=x;
                fa[y]=true;
                ans=ans+b[y]-b[x];
            }
        }
        for(int i=1;i<=n;i++)
            if(!fa[i]) ans=ans+b[i];

        printf("%lld\n",ans);
    }
    return 0;
}