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

解:

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

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

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

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

并查集当然做不了,直接上LCT板子呀!

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

总复杂度两个log

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
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;
}