P5631 最小 mex 生成树

如果删掉某种权值的边，仍然可以连成一棵生成树，那么显然答案是小于等于这个数的。因为我们必然可以不要这种边权来构成一棵树，这样这棵树的 mex 必然不会大于这个数。

然后一种暴力的做法就来了：删除某种权值的所有边并且跑生成树，看是否联通。复杂度是 $O(wn\log n)$ 。

考虑优化，我们可以分治来做（类似不要某个物品的背包），$solve(l,r)$ 表示 $[l,r]$ 之间的权值删去时来做生成树。分治的时候就是加入 $[l,mid]$ ，然后 $solve(mid + 1,r)$ ，再用可撤销并查集撤销刚刚的，加入右边，再 $solve(l,mid)$ 就完事了。

复杂度是 $O(n\log n\log w)$ ，在 luogu 跑的飞快。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "bitset"
#include "queue"
using namespace std;
#define MAXN 2000006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define chkmn( a , b ) ( (a) = ( (a) < (b) ? (a) : (b) ) )
#define chkmx( a , b ) ( (a) = ( (a) > (b) ? (a) : (b) ) )
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
#define P 998244353
typedef long long ll;

void rd( int& x ) {
    x = 0; char ch = ' ';
    while( ch > '9' || ch < '0' ) ch = getchar();
    while( ch >= '0' && ch <= '9' )  x = 10 * x + ch - '0' , ch = getchar();
}

int n , m;

vector<pii> e[MAXN];

int fa[MAXN] , siz[MAXN];
int find( int x ) { return fa[x] == x ? x : find( fa[x] ); }

int cure;
void solve( int l , int r ) {
    if( l == r ) {
        if( cure == n - 1 ) { printf("%d\n",l); exit(0); }
        return;
    }
    int mid = l + r >> 1 , last = cure;
    vi vec;
    rep( i , mid + 1 , r ) {
        for( pii& t : e[i] ) {
            int u = find( t.fi ) , v = find( t.se );
            if( u == v ) continue;
            if( siz[u] < siz[v] ) u ^= v , v ^= u , u ^= v;
            vec.pb( v );
            siz[u] += siz[v] , fa[v] = u;
            ++ cure;
        }
    }
    solve( l , mid );
    reverse( all( vec ) );
    for( int x : vec ) siz[fa[x]] -= siz[x] , fa[x] = x;
    cure = last;
    vec.clear();
    rep( i , l , mid ) {
        for( pii& t : e[i] ) {
            int u = find( t.fi ) , v = find( t.se );
            if( u == v ) continue;
            if( siz[u] < siz[v] ) u ^= v , v ^= u , u ^= v;
            vec.pb( v );
            siz[u] += siz[v] , fa[v] = u;
            ++ cure;
        }
    }
    solve( mid + 1 , r );
    reverse( all( vec ) );
    for( int x : vec ) siz[fa[x]] -= siz[x] , fa[x] = x;
    cure = last;
}

void solve() {
    cin >> n >> m;
    int u , v , w , mx = 0;
    rep( i , 1 , m ) {
        rd( u ) , rd( v ) , rd( w );
        e[w].eb( mp( u , v ) ); mx = max( mx , w );
    }
    rep( i , 1 , n ) fa[i] = i , siz[i] = 1;
    solve( 0 , mx + 1 );
}

signed main() {
//    freopen("input","r",stdin);
//    freopen("fuckout","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
    solve();
}