CF1515F 题解

· · 题解

考虑取出一棵生成树，观察它是否合法。首先要满足一个条件就是 \sum a_i\ge (n-1)x，不然最后合并不起来

然后貌似没啥想法了，不如直接猜测这就是充要条件，事实上这是正确的。如果做过 NOI2020 制作菜品 就会知道一个结论：当 n\ge 2 时最大数加最小数 \ge x。可以证一下：

所以可以考虑第一次选最大的点，然后任选与它相邻的一个点，将它们合并即可。合并之后成为一个新点 a_i+a_j-x，n 减去 1，此时仍有 \sum a_i\ge (n-1)x，所以归纳就完成了。

那既然充要条件是 \sum a_i\ge (n-1)x，所以判完后任选一个生成树即可。

我的实现是并查集与边表的启发式合并，以及用线段树查找全局最大值

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;

typedef long long ll;
const int MAXN=3e5+5;
const ll INF=1e18;

int fa[MAXN],siz[MAXN];
int get(int x){
    if(fa[x]!=x)fa[x]=get(fa[x]);
    return fa[x];
}

int N,M,X;ll sum,a[MAXN];
struct edge{
    int v,i;
    edge(){}
    edge(int v,int i):v(v),i(i){}
};
vector<edge> V[MAXN];

struct data{
    ll mx;int pos;
    data(){}
    data(ll mx,int pos):mx(mx),pos(pos){}
    friend data operator+(const data& l,const data& r){
        return l.mx>r.mx?l:r;
    }
}T[MAXN<<2];
#define ls (o<<1)
#define rs (o<<1|1)
#define mid ((l+r)>>1)
void build(int o,int l,int r){
    if(l==r)T[o]=data(a[l],l);
    else build(ls,l,mid),build(rs,mid+1,r),T[o]=T[ls]+T[rs];
}
void ins(int o,int l,int r,int p,ll k){
    if(l==r)T[o].mx=k;
    else{
        if(p<=mid)ins(ls,l,mid,p,k);
        else ins(rs,mid+1,r,p,k);
        T[o]=T[ls]+T[rs];
    }
}

int main(){
    scanf("%d%d%d",&N,&M,&X);
    for(int i=1;i<=N;++i)scanf("%lld",&a[i]),sum+=a[i];
    if(sum<1ll*(N-1)*X){puts("NO");return 0;}
    puts("YES");
    for(int i=1;i<=N;++i)fa[i]=i;
    int u,v;
    for(int i=1;i<=M;++i){
        scanf("%d%d",&u,&v);
        if(get(u)!=get(v))fa[get(u)]=get(v),V[u].push_back(edge(v,i)),V[v].push_back(edge(u,i));
    }
    for(int i=1;i<=N;++i)fa[i]=i,siz[i]=1;
    build(1,1,N);
    for(int i=1;i<N;++i){
        int u=T[1].pos;
        while(1){
            int v=V[u].back().v;
            if(get(v)==u)V[u].pop_back();
            else{
                printf("%d\n",V[u].back().i);
                int x=get(v);
                if(siz[u]>siz[x]){
                    fa[x]=u,siz[u]+=siz[x],a[u]=a[u]+a[x]-X;
                    for(int k=0;k<V[x].size();++k)V[u].push_back(V[x][k]);
                    ins(1,1,N,x,-INF),ins(1,1,N,u,a[u]);
                }else{
                    fa[u]=x,siz[x]+=siz[u],a[x]=a[x]+a[u]-X;
                    for(int k=0;k<V[u].size();++k)V[x].push_back(V[u][k]);
                    ins(1,1,N,u,-INF),ins(1,1,N,x,a[x]);
                }
                break;
            }
        }
    }
    return 0;
}