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
| #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 200006
#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;
int n , q , L;
int ch[MAXN][2] , fa[MAXN];
bool notr( int u ) { return ch[fa[u]][0] == u || ch[fa[u]][1] == u; }
void rot( int u ) {
int f = fa[u] , g = fa[f] , w = ch[f][1] == u , k = ch[u][w ^ 1];
if( notr( f ) ) ch[g][ch[g][1] == f] = u; ch[f][w] = k , ch[u][w ^ 1] = f;
fa[u] = g , fa[f] = u , fa[k] = f;
}
void splay( int u ) {
int f , g;
while( notr( u ) ) {
f = fa[u] , g = fa[f];
if( notr( f ) ) rot( ( (ch[f][1] == u) ^ (ch[g][1] == f) ) ? u : f );
rot( u );
}
}
int access( int u ) {
for( int p = 0 ; ; p = u , u = fa[u] ) {
splay( u ) , ch[u][1] = p;
if( !fa[u] ) return u;
}
}
void link( int u , int v ) {
access( u ) , splay( u ) , fa[u] = v;
}
void cut( int u ) {
access( u ) , splay( u );
ch[u][0] = fa[ch[u][0]] = 0;
}
void solve() {
cin >> n >> q;
char ch[6]; int u , v;
rep( i , 1 , q ) {
scanf("%s",ch);
if( ch[1] == 'i' ) {
scanf("%d%d",&u,&v);
link( u , v );
} else if( ch[1] == 'u' ) {
scanf("%d",&u);
cut( u );
} else {
scanf("%d%d",&u,&v);
access( u );
printf("%d\n",access( v ));
}
}
}
signed main() {
solve();
}
|
