Luogu P5631 最小mex生成树

题意：点数1e6边数2e6求最小mex生成树

解：

线段树分治+可撤销并查集

首先可以想到一个显然的暴力：枚举最终的答案，将边权等于该答案的边全都删去的情况下看是否能有生成树

那么可以发现，暴力的过程中，有大量的在并查集上的操作是重复的。能不能对此进行优化呢？

考虑分治。solve(L,R)用来运算边权在L到R之间的边都不选的情况。可以发现，当L==R时，检查并查集是不是包含了所有点即可判断当前答案能否生成树。如果递归顺序是从小到大，那么只要搜到答案即可退出。当需要递归进下一层时，将另一边的边全部加入即可。那么如何在递归到上层时将加入边的操作撤销呢？

并查集当然做不了，直接上LCT板子呀！

如果一个并查集不进行路径压缩，只是按大小启发式合并（按秩合并这里更难写，但是复杂度相同），并存下每个节点的子树的大小，那么由于子树信息永远不会被修改，撤销时按顺序把子树信息在父亲那减掉，再把子树的父亲指向自己即可。

总复杂度两个log

const int maxn=2222222;
int n,m;
pair<int,pii> e[maxn];
int fa[maxn],size[maxn];
void init(int n)
{
    rep(i,1,n) {fa[i]=i;size[i]=1;}
}
int getfa(int x)
{
    while (fa[x]!=x) x=fa[x];
    return x;
}
int unite(int x,int y)
{
    int fx=getfa(x),fy=getfa(y);
    if (fx==fy) return 0;
    if (size[fx]>size[fy]) swap(fx,fy);
    size[fy]+=size[fx];
    fa[fx]=fy;
    return fx;
}
void undo(int x)
{
    if (x==0) return;
    size[fa[x]]-=size[x];
    fa[x]=x;
}
void solve(int l,int r,int L,int R)
{
    if (l==r)
    {
        if (size[getfa(1)]==n) {cout<<l<<endl;exit(0);}
        return;
    }
    int mid=(l+r)>>1;

    int pos;
    
    stack<int> s;
    for (pos=R;pos>=L&&e[pos].first>mid;pos--) s.push(unite(e[pos].second.first,e[pos].second.second));
    solve(l,mid,L,pos);
    while (!s.empty()) {undo(s.top());s.pop();}

    for (pos=L;pos<=R&&e[pos].first<=mid;pos++) s.push(unite(e[pos].second.first,e[pos].second.second));
    solve(mid+1,r,pos,R);
    while (!s.empty()) {undo(s.top());s.pop();}
}
int main()
{
    read(n,m);
    init(n);
    rep(i,1,m) read(e[i].second.first,e[i].second.second,e[i].first);
    sort(e+1,e+m+1);
    solve(0,e[m].first+1,1,m);
    return 0;
}