SP8791 Dynamic LCA

SP8791 Dynamic LCA

用 LCT 可以实现动态的 LCA。。其实想想就知道这其实是一个非常简单的套路。

比如要求 u,vu , v 的 LCA ,先 access 一下 uu 然后在 access vv 的时候把最后一个虚实交替的位置给返回就好了。写出来大概长成这样:

int access( int u ) {
    for( int p = 0 ; ; p = u , u = fa[u] ) {
        splay( u ) , ch[u][1] = p;
        if( !fa[u] ) return u;
    }
}

很高兴 LCT 1A了(虽然是啥操作都没有的阉割版本)

#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 int long long
#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() {
//    freopen("input","r",stdin);
//    freopen("fuckout","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
    solve();
}
\