Intro

首先要明确一点，LCT的应用场合是什么？

回想以前的树上操作，树的拓扑结构都是不发生变化的，然后一般利用树链剖分结合线段树实现logn或logn^2的单次操作。

而LCT其实也是一个广义的“树链剖分”，它在树的拓扑结构发生变化时(例如要求能满足断开边，再连接新边的操作)，仍然能满足logn或logn^2的单次操作复杂度

实链剖分

  • 对于一个点连向它所有儿子的边 , 我们自己选择一条边进行剖分，我们称被选择的边为实边，其他边则为虚边（当然，有可能所有儿子都是虚边）。
  • 对于实边，我们称它所连接的儿子为实儿子。
  • 对于一条由实边组成的链，我们同样称之为实链。

辅助树

  • 在一条实链中的所有点，使用同一个splay维护。这个splay被称为辅助树。每棵辅助树维护的是一棵树，一些辅助树构成了LCT，其维护的是整个森林。
  • 辅助树由多棵 Splay 组成，每棵 Splay 维护原树中的一条路径，且中序遍历这棵 Splay 得到的点序列，从前到后对应原树“从上到下”的一条路径。
  • 原树每个节点与辅助树的 Splay 节点一一对应。
  • 每棵 Splay 的根节点的父亲节点本应是空，但在 LCT 中每棵 Splay 的根节点的父亲节点指向原树中 这条链 的父亲节点（即链最顶端的点的父亲节点）。这类父亲链接与通常 Splay 的父亲链接区别在于儿子认父亲，而父亲不认儿子，对应原树的一条 虚边。因此，每个连通块恰好有一个点的父亲节点为空。
  • 由于辅助树的以上性质，我们维护任何操作都不需要维护原树，辅助树可以在任何情况下拿出一个唯一的原树，我们只需要维护辅助树即可。

图解详见OI-WIKI

模板

洛谷P3690 【模板】Link Cut Tree

如此强大的数据结构，板子却出奇的短，不得不说还是蛮神奇的

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<bits/stdc++.h>
#define R register int
#define I inline void
#define G if(++ip==ie)if(fread(ip=buf,1,SZ,stdin))
#define lc c[x][0]
#define rc c[x][1]
using namespace std;
const int SZ=1<<19,N=3e5+9;
char buf[SZ],*ie=buf+SZ,*ip=ie-1;
inline int in(){
	G;while(*ip<'-')G;
	R x=*ip&15;G;
	while(*ip>'-'){x*=10;x+=*ip&15;G;}
	return x;
}
int f[N],c[N][2],v[N],s[N],st[N];
bool r[N];
inline bool nroot(R x){//判断节点是否为一个Splay的根（与普通Splay的区别1）
	return c[f[x]][0]==x||c[f[x]][1]==x;
}//原理很简单，如果连的是轻边，他的父亲的儿子里没有它
I pushup(R x){//上传信息
	s[x]=s[lc]^s[rc]^v[x];
}
I pushr(R x){R t=lc;lc=rc;rc=t;r[x]^=1;}//翻转操作
I pushdown(R x){//判断并释放懒标记
	if(r[x]){
		if(lc)pushr(lc);
		if(rc)pushr(rc);
		r[x]=0;
	}
}
I rotate(R x){//一次旋转
	R y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];
	if(nroot(y))c[z][c[z][1]==y]=x;c[x][!k]=y;c[y][k]=w;//额外注意if(nroot(y))语句，此处不判断会引起致命错误（与普通Splay的区别2）
	if(w)f[w]=y;f[y]=x;f[x]=z;
	pushup(y);
}
I splay(R x){//只传了一个参数，因为所有操作的目标都是该Splay的根（与普通Splay的区别3）
	R y=x,z=0;
	st[++z]=y;//st为栈，暂存当前点到根的整条路径，pushdown时一定要从上往下放标记（与普通Splay的区别4）
	while(nroot(y))st[++z]=y=f[y];
	while(z)pushdown(st[z--]);
	while(nroot(x)){
		y=f[x];z=f[y];
		if(nroot(y))
			rotate((c[y][0]==x)^(c[z][0]==y)?x:y);
		rotate(x);
	}
	pushup(x);
}
/*当然了，其实利用函数堆栈也很方便，代替上面的手工栈，就像这样
I pushall(R x){
	if(nroot(x))pushall(f[x]);
	pushdown(x);
}*/
I access(R x){//访问
	for(R y=0;x;x=f[y=x])
		splay(x),rc=y,pushup(x);
}
I makeroot(R x){//换根
	access(x);splay(x);
	pushr(x);
}
int findroot(R x){//找根（在真实的树中的）
	access(x);splay(x);
	while(lc)pushdown(x),x=lc;
	splay(x);
	return x;
}
I split(R x,R y){//提取路径
	makeroot(x);
	access(y);splay(y);
}
I link(R x,R y){//连边
	makeroot(x);
	if(findroot(y)!=x)f[x]=y;
}
I cut(R x,R y){//断边
	makeroot(x);
	if(findroot(y)==x&&f[y]==x&&!c[y][0]){
		f[y]=c[x][1]=0;
		pushup(x);
	}
}
int main()
{
	R n=in(),m=in();
	for(R i=1;i<=n;++i)v[i]=in();
	while(m--){
		R type=in(),x=in(),y=in();
		switch(type){
		case 0:split(x,y);printf("%d\n",s[y]);break;
		case 1:link(x,y);break;
		case 2:cut(x,y);break;
		case 3:splay(x);v[x]=y;//先把x转上去再改，不然会影响Splay信息的正确性
		}
	}
	return 0;
}

练习

容易发现，由于一个地方的目的地是恒定的，所以天然形成了森林的结构，这里又涉及到改边的操作，LCT呼之欲出

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
58
59
60
61
62
63
#include<cstdio>
#include<cstdlib>
#define R register int
#define I inline void
#define G ch=getchar()
#define gc G;while(ch<'-')G
#define in(z) gc;z=ch&15;G;while(ch>'-')z*=10,z+=ch&15,G;
const int N=200009;
int f[N],c[N][2],s[N];
inline bool nroot(R x){
    return c[f[x]][0]==x||c[f[x]][1]==x;
}
I pushup(R x){
    s[x]=s[c[x][0]]+s[c[x][1]]+1;
}
I rotate(R x){
    R y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];
    if(nroot(y))c[z][c[z][1]==y]=x;c[x][!k]=y;c[y][k]=w;
    if(w)f[w]=y;f[y]=x;f[x]=z;
    pushup(y);
}
I splay(R x){
    R y,z;
    while(nroot(x)){
        y=f[x];z=f[y];
        if(nroot(y))
            rotate((c[y][0]==x)^(c[z][0]==y)?x:y);//fixed
        rotate(x);
    }
    pushup(x);
}
I access(R x){
    for(R y=0;x;x=f[y=x])
        splay(x),c[x][1]=y,pushup(x);
}//以上是轻量化的LCT板子
int main()
{
    register char ch;
    R n,m,j,k;
    in(n);
    for(j=1;j<=n;++j){
        s[j]=1;
        in(k);
        if(j+k<=n)f[j]=j+k;//如果弹飞了就不连边
    }
    in(m);
    while(m--){
        gc;
        if(ch&1){
            in(j);++j;
            access(j);splay(j);//直接查询
            printf("%d\n",s[j]);
        }
        else{
            in(j);in(k);++j;
            access(j);splay(j);
            c[j][0]=f[c[j][0]]=0;//直接断边
            if(j+k<=n)f[j]=j+k;//直接连边
            pushup(j);
        }
    }
    return 0;
}

维护树链信息

LCT 通过 Split(x,y) 操作，可以将树上从点 x 到点 y 的路径提取到以 y 为根的 Splay 内，树链信息的修改和统计转化为平衡树上的操作，这使得 LCT 在维护树链信息上具有优势。此外，借助 LCT 实现的在树链上二分比树链剖分少一个 logn 的复杂度。

练习

「国家集训队」Tree II

对树上 u,v 两点之间的路径进行修改时，先 Split(u,v)。

此题要求进行在辅助树上的子树加，子树乘，子树求和操作，所以我们除了一般 LCT 需要维护的子树翻转标记，还要维护子树加法标记和子树乘法标记。处理标记的方法和在 Splay 上是一样的。

在打上和下传加法标记时，子树权值和的变化量和子树中的结点数有关，所以我们还要维护子树的大小 siz。

在下传标记时，需要注意顺序，先下传乘法标记再下传加法标记。子树翻转和子树加乘两种标记没有冲突。

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
#define int long long
const int maxn = 100010;
const int mod = 51061;
int n, q, u, v, c;
char op;
struct Splay {
  int ch[maxn][2], fa[maxn], siz[maxn], val[maxn], sum[maxn], rev[maxn],
      add[maxn], mul[maxn];
  void clear(int x) {
    ch[x][0] = ch[x][1] = fa[x] = siz[x] = val[x] = sum[x] = rev[x] = add[x] =
        0;
    mul[x] = 1;
  }
  int getch(int x) { return (ch[fa[x]][1] == x); }
  int isroot(int x) {
    clear(0);
    return ch[fa[x]][0] != x && ch[fa[x]][1] != x;
  }
  void maintain(int x) {
    clear(0);
    siz[x] = (siz[ch[x][0]] + 1 + siz[ch[x][1]]) % mod;
    sum[x] = (sum[ch[x][0]] + val[x] + sum[ch[x][1]]) % mod;
  }
  void pushdown(int x) {
    clear(0);
    if (mul[x] != 1) {
      if (ch[x][0])
        mul[ch[x][0]] = (mul[x] * mul[ch[x][0]]) % mod,
        val[ch[x][0]] = (val[ch[x][0]] * mul[x]) % mod,
        sum[ch[x][0]] = (sum[ch[x][0]] * mul[x]) % mod,
        add[ch[x][0]] = (add[ch[x][0]] * mul[x]) % mod;
      if (ch[x][1])
        mul[ch[x][1]] = (mul[x] * mul[ch[x][1]]) % mod,
        val[ch[x][1]] = (val[ch[x][1]] * mul[x]) % mod,
        sum[ch[x][1]] = (sum[ch[x][1]] * mul[x]) % mod,
        add[ch[x][1]] = (add[ch[x][1]] * mul[x]) % mod;
      mul[x] = 1;
    }
    if (add[x]) {
      if (ch[x][0])
        add[ch[x][0]] = (add[ch[x][0]] + add[x]) % mod,
        val[ch[x][0]] = (val[ch[x][0]] + add[x]) % mod,
        sum[ch[x][0]] = (sum[ch[x][0]] + add[x] * siz[ch[x][0]] % mod) % mod;
      if (ch[x][1])
        add[ch[x][1]] = (add[ch[x][1]] + add[x]) % mod,
        val[ch[x][1]] = (val[ch[x][1]] + add[x]) % mod,
        sum[ch[x][1]] = (sum[ch[x][1]] + add[x] * siz[ch[x][1]] % mod) % mod;
      add[x] = 0;
    }
    if (rev[x]) {
      if (ch[x][0]) rev[ch[x][0]] ^= 1, swap(ch[ch[x][0]][0], ch[ch[x][0]][1]);
      if (ch[x][1]) rev[ch[x][1]] ^= 1, swap(ch[ch[x][1]][0], ch[ch[x][1]][1]);
      rev[x] = 0;
    }
  }
  void update(int x) {
    if (!isroot(x)) update(fa[x]);
    pushdown(x);
  }
  void print(int x) {
    if (!x) return;
    pushdown(x);
    print(ch[x][0]);
    printf("%lld ", x);
    print(ch[x][1]);
  }
  void rotate(int x) {
    int y = fa[x], z = fa[y], chx = getch(x), chy = getch(y);
    fa[x] = z;
    if (!isroot(y)) ch[z][chy] = x;
    ch[y][chx] = ch[x][chx ^ 1];
    fa[ch[x][chx ^ 1]] = y;
    ch[x][chx ^ 1] = y;
    fa[y] = x;
    maintain(y);
    maintain(x);
    maintain(z);
  }
  void splay(int x) {
    update(x);
    for (int f = fa[x]; f = fa[x], !isroot(x); rotate(x))
      if (!isroot(f)) rotate(getch(x) == getch(f) ? f : x);
  }
  void access(int x) {
    for (int f = 0; x; f = x, x = fa[x]) splay(x), ch[x][1] = f, maintain(x);
  }
  void makeroot(int x) {
    access(x);
    splay(x);
    swap(ch[x][0], ch[x][1]);
    rev[x] ^= 1;
  }
  int find(int x) {
    access(x);
    splay(x);
    while (ch[x][0]) x = ch[x][0];
    splay(x);
    return x;
  }
} st;
main() {
  scanf("%lld%lld", &n, &q);
  for (int i = 1; i <= n; i++) st.val[i] = 1, st.maintain(i);
  for (int i = 1; i < n; i++) {
    scanf("%lld%lld", &u, &v);
    if (st.find(u) != st.find(v)) st.makeroot(u), st.fa[u] = v;
  }
  while (q--) {
    scanf(" %c%lld%lld", &op, &u, &v);
    if (op == '+') {
      scanf("%lld", &c);
      st.makeroot(u), st.access(v), st.splay(v);
      st.val[v] = (st.val[v] + c) % mod;
      st.sum[v] = (st.sum[v] + st.siz[v] * c % mod) % mod;
      st.add[v] = (st.add[v] + c) % mod;
    }
    if (op == '-') {
      st.makeroot(u);
      st.access(v);
      st.splay(v);
      if (st.ch[v][0] == u && !st.ch[u][1]) st.ch[v][0] = st.fa[u] = 0;
      scanf("%lld%lld", &u, &v);
      if (st.find(u) != st.find(v)) st.makeroot(u), st.fa[u] = v;
    }
    if (op == '*') {
      scanf("%lld", &c);
      st.makeroot(u), st.access(v), st.splay(v);
      st.val[v] = st.val[v] * c % mod;
      st.sum[v] = st.sum[v] * c % mod;
      st.mul[v] = st.mul[v] * c % mod;
    }
    if (op == '/')
      st.makeroot(u), st.access(v), st.splay(v), printf("%lld\n", st.sum[v]);
  }
  return 0;
}

维护连通性

检查是否连通

借助 LCT 的 Find() 函数，可以判断动态森林上的两点是否连通。如果有 Find(x)==Find(y)，则说明 x,y 两点在一棵树上，相互连通。

「SDOI2008」洞穴勘测

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 10010;
struct Splay {
  int ch[maxn][2], fa[maxn], tag[maxn];
  void clear(int x) { ch[x][0] = ch[x][1] = fa[x] = tag[x] = 0; }
  int getch(int x) { return ch[fa[x]][1] == x; }
  int isroot(int x) { return ch[fa[x]][0] != x && ch[fa[x]][1] != x; }
  void pushdown(int x) {
    if (tag[x]) {
      if (ch[x][0]) swap(ch[ch[x][0]][0], ch[ch[x][0]][1]), tag[ch[x][0]] ^= 1;
      if (ch[x][1]) swap(ch[ch[x][1]][0], ch[ch[x][1]][1]), tag[ch[x][1]] ^= 1;
      tag[x] = 0;
    }
  }
  void update(int x) {
    if (!isroot(x)) update(fa[x]);
    pushdown(x);
  }
  void rotate(int x) {
    int y = fa[x], z = fa[y], chx = getch(x), chy = getch(y);
    fa[x] = z;
    if (!isroot(y)) ch[z][chy] = x;
    ch[y][chx] = ch[x][chx ^ 1];
    fa[ch[x][chx ^ 1]] = y;
    ch[x][chx ^ 1] = y;
    fa[y] = x;
  }
  void splay(int x) {
    update(x);
    for (int f = fa[x]; f = fa[x], !isroot(x); rotate(x))
      if (!isroot(f)) rotate(getch(x) == getch(f) ? f : x);
  }
  void access(int x) {
    for (int f = 0; x; f = x, x = fa[x]) splay(x), ch[x][1] = f;
  }
  void makeroot(int x) {
    access(x);
    splay(x);
    swap(ch[x][0], ch[x][1]);
    tag[x] ^= 1;
  }
  int find(int x) {
    access(x);
    splay(x);
    while (ch[x][0]) x = ch[x][0];
    splay(x);
    return x;
  }
} st;
int n, q, x, y;
char op[maxn];
int main() {
  scanf("%d%d", &n, &q);
  while (q--) {
    scanf("%s%d%d", op, &x, &y);
    if (op[0] == 'Q') {
      if (st.find(x) == st.find(y))
        printf("Yes\n");
      else
        printf("No\n");
    }
    if (op[0] == 'C')
      if (st.find(x) != st.find(y)) st.makeroot(x), st.fa[x] = y;
    if (op[0] == 'D') {
      st.makeroot(x);
      st.access(y);
      st.splay(y);
      if (st.ch[y][0] == x && !st.ch[x][1]) st.ch[y][0] = st.fa[x] = 0;
    }
  }
  return 0;
}

维护边双连通分量

将边双连通分量缩成点，每次添加一条边，所连接的树上的两点如果相互连通，那么这条路径上的所有点都会被缩成一个点

「AHOI2005」航线规划

可以发现，u,v 两点之间的所有可能路径必须经过的边的数量为将所有边双连通分量缩成点之后 u 所在点和 v 所在点之间的路径上的结点数再减一。

但是问题来了，缩点之后如何删边呢？我们会发现极难实现

所以逆向考虑，离线询问后，从最终状态的倒着求解，改删边为加边

加入一条边时，如果两点原来不连通，则在 LCT 上连接两点；否则提取出加这条边之前 LCT 上这两点之间的路径，遍历辅助树上的这个子树，相当于遍历了这条路径，将这些点合并，利用并查集维护合并的信息。

用合并后并查集的代表元素代替原来树上的路径。注意之后的每次操作都要找到操作点在并查集上的代表元素进行操作。

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
const int maxn = 200010;
int f[maxn];
int findp(int x) { return f[x] ? f[x] = findp(f[x]) : x; }
void merge(int x, int y) {
  x = findp(x);
  y = findp(y);
  if (x != y) f[x] = y;
}
struct Splay {
  int ch[maxn][2], fa[maxn], tag[maxn], siz[maxn];
  void clear(int x) { ch[x][0] = ch[x][1] = fa[x] = tag[x] = siz[x] = 0; }
  int getch(int x) { return ch[findp(fa[x])][1] == x; }
  int isroot(int x) {
    return ch[findp(fa[x])][0] != x && ch[findp(fa[x])][1] != x;
  }
  void maintain(int x) {
    clear(0);
    if (x) siz[x] = siz[ch[x][0]] + 1 + siz[ch[x][1]];
  }
  void pushdown(int x) {
    if (tag[x]) {
      if (ch[x][0]) tag[ch[x][0]] ^= 1, swap(ch[ch[x][0]][0], ch[ch[x][0]][1]);
      if (ch[x][1]) tag[ch[x][1]] ^= 1, swap(ch[ch[x][1]][0], ch[ch[x][1]][1]);
      tag[x] = 0;
    }
  }
  void print(int x) {
    if (!x) return;
    pushdown(x);
    print(ch[x][0]);
    printf("%d ", x);
    print(ch[x][1]);
  }
  void update(int x) {
    if (!isroot(x)) update(findp(fa[x]));
    pushdown(x);
  }
  void rotate(int x) {
    x = findp(x);
    int y = findp(fa[x]), z = findp(fa[y]), chx = getch(x), chy = getch(y);
    fa[x] = z;
    if (!isroot(y)) ch[z][chy] = x;
    ch[y][chx] = ch[x][chx ^ 1];
    fa[ch[x][chx ^ 1]] = y;
    ch[x][chx ^ 1] = y;
    fa[y] = x;
    maintain(y);
    maintain(x);
    if (z) maintain(z);
  }
  void splay(int x) {
    x = findp(x);
    update(x);
    for (int f = findp(fa[x]); f = findp(fa[x]), !isroot(x); rotate(x))
      if (!isroot(f)) rotate(getch(x) == getch(f) ? f : x);
  }
  void access(int x) {
    for (int f = 0; x; f = x, x = findp(fa[x]))
      splay(x), ch[x][1] = f, maintain(x);
  }
  void makeroot(int x) {
    x = findp(x);
    access(x);
    splay(x);
    tag[x] ^= 1;
    swap(ch[x][0], ch[x][1]);
  }
  int find(int x) {
    x = findp(x);
    access(x);
    splay(x);
    while (ch[x][0]) x = ch[x][0];
    splay(x);
    return x;
  }
  void dfs(int x) {
    pushdown(x);
    if (ch[x][0]) dfs(ch[x][0]), merge(ch[x][0], x);
    if (ch[x][1]) dfs(ch[x][1]), merge(ch[x][1], x);
  }
} st;
int n, m, q, x, y, cur, ans[maxn];
struct oper {
  int op, a, b;
} s[maxn];
map<pair<int, int>, int> mp;
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) st.maintain(i);
  for (int i = 1; i <= m; i++)
    scanf("%d%d", &x, &y), mp[{x, y}] = mp[{y, x}] = 1;
  while (scanf("%d", &s[++q].op)) {
    if (s[q].op == -1) {
      q--;
      break;
    }
    scanf("%d%d", &s[q].a, &s[q].b);
    if (!s[q].op) mp[{s[q].a, s[q].b}] = mp[{s[q].b, s[q].a}] = 0;
  }
  reverse(s + 1, s + q + 1);
  for (map<pair<int, int>, int>::iterator it = mp.begin(); it != mp.end(); it++)
    if (it->second) {
      mp[{it->first.second, it->first.first}] = 0;
      x = findp(it->first.first);
      y = findp(it->first.second);
      if (st.find(x) != st.find(y))
        st.makeroot(x), st.fa[x] = y;
      else {
        if (x == y) continue;
        st.makeroot(x);
        st.access(y);
        st.splay(y);
        st.dfs(y);
        int t = findp(y);
        st.fa[t] = findp(st.fa[y]);
        st.ch[t][0] = st.ch[t][1] = 0;
        st.maintain(t);
      }
    }
  for (int i = 1; i <= q; i++) {
    if (s[i].op == 0) {
      x = findp(s[i].a);
      y = findp(s[i].b);
      st.makeroot(x);
      st.access(y);
      st.splay(y);
      st.dfs(y);
      int t = findp(y);
      st.fa[t] = st.fa[y];
      st.ch[t][0] = st.ch[t][1] = 0;
      st.maintain(t);
    }
    if (s[i].op == 1) {
      x = findp(s[i].a);
      y = findp(s[i].b);
      st.makeroot(x);
      st.access(y);
      st.splay(y);
      ans[++cur] = st.siz[y] - 1;
    }
  }
  for (int i = cur; i >= 1; i--) printf("%d\n", ans[i]);
  return 0;
}

练习

「WC2006」水管局长

方法同上，倒着来，如果有边双的话直接缩点

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
#include<algorithm>
#include<iostream>
#define N 1500000
#include<cstdio>
using namespace std;
int re[N],c[N][2],mx[N],val[N],fa[N];
int s[N],top;

bool isroot(int now)
{
    return !fa[now]||(c[fa[now]][0]!=now&&c[fa[now]][1]!=now);
}
void down(int now)
{
    if(re[now])
    {
        re[now]^=1;
        re[c[now][0]]^=1;
        re[c[now][1]]^=1;
        swap(c[now][0],c[now][1]);
    }
}
void update(int now)
{
    mx[now]=now;
    if(val[ mx[c[now][0]] ]>val[mx[now]]) mx[now]=mx[c[now][0]];
    if(val[ mx[c[now][1]] ]>val[mx[now]]) mx[now]=mx[c[now][1]];
}
void rotate(int now)
{
    int F=fa[now],Y=fa[F];
    int r=c[F][0]==now,l=r^1;
    
    if(!isroot(F)) if(c[Y][0]==F) c[Y][0]=now;else c[Y][1]=now;
    
    fa[now]=Y;fa[F]=now;
    c[F][l]=c[now][r];
    fa[c[now][r]]=F;
    c[now][r]=F;
    update(F); 
    update(now);
}
void splay(int now)
{
    s[top=1]=now;
    for(int i=now;!isroot(i);i=fa[i]) s[++top]=fa[i];
    while(top) down(s[top--]);
    while(!isroot(now))
    {
        int F=fa[now],Y=fa[F];
        if(!isroot(F))
        {
            if((c[Y][0]==F)^(c[F][0]==now)) rotate(now);
            else rotate(F);
        }
        rotate(now);
    }
}
void access(int now)
{
    int last=0;
    while(now) splay(now),c[now][1]=last,update(now),last=now,now=fa[now];
}

void makeroot(int x)
{
    access(x);splay(x);re[x]^=1;
}
void link(int x,int y)
{
    makeroot(x);fa[x]=y;
}
void cut(int x,int y)
{
    makeroot(x);access(y);splay(y);fa[x]=c[y][0]=0;
}
int query(int x,int y)
{
    makeroot(x);access(y);splay(y);return mx[y];
}


struct eage
{
    int u,v,l,id;
    bool po;
}e[N];
struct node
{
    int x,y,ans,id,fl; 
}q[N];
int n,m,Q;

bool comp1(eage aa,eage bb)
{
    return aa.u==bb.u?aa.v<bb.v:aa.u<bb.u;
}
bool comp2(eage aa,eage bb)
{
    return aa.l<bb.l;
}
bool comp3(eage aa,eage bb)
{
    return aa.id<bb.id;
}
int findit(int u,int v)
{
    int l=1,r=m;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(e[mid].u<u||(e[mid].u==u&&e[mid].v<v))l=mid+1;
        else if(e[mid].u==u&&e[mid].v==v)return mid;
        else r=mid-1;
    }
}
int f[N];
int get_f(int now)
{
    return now==f[now]?f[now]:f[now]=get_f(f[now]);
}
void KU()
{
    for(int i=1;i<=n;++i) f[i]=i;
    sort(e+1,e+m+1,comp3);
    int tot=0;
    for(int i=1;i<=m;++i)
    {
        if(e[i].po) continue; 
        int x=get_f(e[i].u),y=get_f(e[i].v);
        if(x==y) continue;
        tot++;
        f[x]=y;
        link(e[i].u,i+n);
        link(e[i].v,i+n);
        if(tot==n-1) return;
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&Q);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].l);
        if(e[i].u>e[i].v) swap(e[i].u,e[i].v);
    }
    //buid
    sort(e+1,e+m+1,comp2);
    for(int i=1;i<=m;++i)
    {
        e[i].id=i;
        val[n+i]=e[i].l;
        mx[n+i]=n+i;
    }
    //in
    sort(e+1,e+m+1,comp1);
    for(int i=1;i<=Q;++i)
    {
        scanf("%d%d%d",&q[i].fl,&q[i].x,&q[i].y);
        if(q[i].fl==2)
        {
            if(q[i].x>q[i].y) swap(q[i].x,q[i].y);
            int id=findit(q[i].x,q[i].y);t
            q[i].id=e[id].id;
            e[id].po=1;
        }
    }
    
    KU();
    for(int i=Q;i;--i) 
    {
        if(q[i].fl==1) q[i].ans=val[query(q[i].x,q[i].y)];
        else//join
        {
            int bi=query(q[i].x,q[i].y);
            if(val[bi]>val[q[i].id+n])
            {
                cut(e[bi-n].u,bi);
                cut(e[bi-n].v,bi);
                link(q[i].x,q[i].id+n);
                link(q[i].y,q[i].id+n);
            }
        }
    }
    for(int i=1;i<=Q;++i) if(q[i].fl==1) printf("%d\n",q[i].ans);
    return 0;
}