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
| #include <cstring>
#include <cctype>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 300000+5;
inline int read()
{
int f = 1, x = 0; char ch;
while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
while(isdigit(ch)) { x = x*10+ch-'0'; ch = getchar(); }
return f*x;
}
int n, q, type;
int ch[N][2], fa[N], f[N];
int val[N], rev[N];
int d1[N], d2[N];
void pushup(int x) { if(x) val[x] = val[ch[x][0]]+val[ch[x][1]]+1; }
bool nroot(int x) { return ch[fa[x]][0] == x || ch[fa[x]][1] == x; }
void pushr(int x) { if(x) swap(ch[x][0], ch[x][1]), rev[x] ^= 1; }
void pushdown(int x) { if(rev[x]) pushr(ch[x][0]), pushr(ch[x][1]), rev[x] = 0; }
void rotate(int x)
{
int y = fa[x], z = fa[y], k = ch[y][1]==x, w = ch[x][!k];
ch[x][!k] = y; ch[y][k] = w; if(nroot(y)) ch[z][ch[z][1]==y] = x;
fa[x] = z; fa[y] = x; if(w) fa[w] = y;
pushup(y); pushup(x);
}
void pushshall(int x)
{
if(nroot(x)&&x) pushshall(fa[x]);
pushdown(x);
}
void splay(int x)
{
pushshall(x);
while(nroot(x))
{
int y = fa[x], z = fa[y];
if(nroot(y)) (ch[y][1]==x)^(ch[z][1]==y)?rotate(x):rotate(y);
rotate(x);
}
}
void access(int x)
{
for(int y = 0; x; x = fa[y=x])
splay(x), ch[x][1] = y, pushup(x);
}
void makeroot(int x) { access(x); splay(x); pushr(x); }
void split(int x, int y) { makeroot(x); access(y); splay(y); }
int query(int x, int y) { split(x, y); return val[y]; }
int find(int x) { return f[x] == x?x:f[x] = find(f[x]); }
void link(int x, int y)
{
makeroot(x); fa[x] = y;
int fx = find(x), fy = find(y); f[fx] = fy;
int x1 = d1[fx], y1 = d2[fx], x2 = d1[fy], y2 = d2[fy];
int v = query(x2, y2), t = 0;
t = query(x1, y1); if(t > v) v = t, d1[fy] = x1, d2[fy] = y1;
t = query(x1, y2); if(t > v) v = t, d1[fy] = x1, d2[fy] = y2;
t = query(x2, y1); if(t > v) v = t, d1[fy] = x2, d2[fy] = y1;
t = query(x1, x2); if(t > v) v = t, d1[fy] = x1, d2[fy] = x2;
t = query(y1, y2); if(t > v) v = t, d1[fy] = y1, d2[fy] = y2;
}
int ans;
int main()
{
type = read();
n = read(), q = read();
for(int x = 1; x <= n; ++x) val[x] = 1, d1[x] = d2[x] = f[x] = x;
while(q--)
{
int op = read(), x = read()^ans, y;
if(op == 1) y = read()^ans, link(x, y);
else y = find(x), printf("%d\n", ans = max(query(d1[y], x), query(d2[y], x))-1);
if(!type) ans = 0;
}
return 0;
}
|