P4234 最小差值生成树

· · 题解

二分、线段树分治

一眼 LCT，然而由于我不会 LCT，这里是另一种做法。

看到 LCT 容易想到动态图连通性从而想到线段树分治，本题中 LCT 能够配合双指针动态删边加边，线段树分治做不到。

我们充分发扬人类智慧，类比二分加单调栈 O(n \log n) 替代单调队列 O(n) 的传奇做法，首先二分答案，这样加边和删边的顺序可以提前得到，然后跑线段树分治判断在加边删边过程中是否出现生成树即可。

总体时间复杂度 O(m \log m \log n \log V)，其中 V 为边权的值域。

不开 O2 也能过。

#include<bits/stdc++.h>
using namespace std;
struct Edge{int x,y,w;}e[200'005];
int n,m,ans,mem,sum,f[50'005],h[50'005],tim[200'005];
vector<pair<int,int>> v[1'600'005];
vector<Edge> c[1'600'005];
pair<int,int> p[200'005];
inline int ask(int x){
    while(x!=f[x]) x=f[x];
    return x;
}
inline void combine(int x,int y){
    x=ask(x),y=ask(y);
    f[x]=y,h[y]+=h[x]==h[y];
}
void update(int u,int l,int r,int ql,int qr,pair<int,int> x){
    if(l>=ql&&r<=qr) return v[u].push_back({x});
    int mid=(l+r)>>1;
    if(ql<=mid) update(u*2,l,mid,ql,qr,x);
    if(qr>mid) update(u*2+1,mid+1,r,ql,qr,x);
}
void segsort(int u,int l,int r){
    for(auto [i,j]:v[u]){
        int x=ask(i),y=ask(j);
        if(h[x]>h[y]) swap(x,y);
        if(x!=y) c[u].push_back({x,y,h[x]==h[y]}),combine(x,y);
    }
    sum+=c[u].size(),mem=max(mem,sum);
    int mid=(l+r)>>1;
    if(l!=r) segsort(u*2,l,mid),segsort(u*2+1,mid+1,r);
    reverse(c[u].begin(),c[u].end());
    for(auto [x,y,w]:c[u]) f[x]=x,h[y]-=w;
    sum-=c[u].size(),c[u].clear(),v[u].clear();
    c[u].shrink_to_fit(),v[u].shrink_to_fit();
}
bool fail(int x){
    int l=1,r=1,now=0,maxlen=0;
    while(l<=m){
        while(r<=m&&e[r].w-e[l].w<=x) tim[r]=++now,++r;
        maxlen=max(maxlen,r-l),p[l]={tim[l],++now},++l;
    }
    if(maxlen<n-1) return 1;
    for(int i=1;i<=m;i++) update(1,1,now,p[i].first,p[i].second,{e[i].x,e[i].y});
    for(int i=1;i<=n;i++) f[i]=i,h[i]=1;
    mem=0,segsort(1,1,now);
    return mem!=n-1;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>e[i].x>>e[i].y>>e[i].w;
    sort(e+1,e+m+1,[](auto x,auto y){return x.w<y.w;});
    int l=0,r=e[m].w-e[1].w;
    while(l<=r){
        int mid=(l+r)>>1;
        if(fail(mid)) l=mid+1;
        else ans=mid,r=mid-1;
    }
    cout<<ans<<'\n';
    return 0;
}