简介

  • Link-Cut-Tree是一种数据结构,我们用它来解决动态树问题。
  • Link-Cut-Tree,简称 LCT, 但它不叫动态树,动态树是指一类问题。
  • Splay Tree是 LCT 的基础,但是LCTSplay Tree和普通的Splay在细节处不太一样(进行了一些扩展)。

代码

const int MAXN = 3e5 + 9;
struct LintCutTree {
#define lc c[x][0]
#define rc c[x][1]
    int f[MAXN], c[MAXN][2], v[MAXN], s[MAXN], st[MAXN];
    bool r[MAXN];
    inline bool nroot( int x ) {
        return c[f[x]][0] == x || c[f[x]][1] == x;
    }
    void pushup( int x ) {//Updata
        s[x] = s[lc] ^ s[rc] ^ v[x];
    }
    void pushr( int x ) {
        int t = lc;
        lc = rc;
        rc = t;
        r[x] ^= 1;
    }
    void pushdown( int x ) {
        if ( r[x] ) {
            if ( lc )
                pushr( lc );
            if ( rc )
                pushr( rc );
            r[x] = 0;
        }
    }
    void rotate( int x ) {
        int 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 );
    }
    void splay( int x ) {
        int y = x, z = 0;
        st[++z] = y;
        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 );
    }
    void access( int x ) {
        for ( int y = 0; x; x = f[y = x] )
            splay( x ), rc = y, pushup( x );
    }
    void makeroot( int x ) {
        access( x );
        splay( x );
        pushr( x );
    }
    int findroot( int x ) {
        access( x );
        splay( x );
        while ( lc )
            pushdown( x ), x = lc;
        splay( x );
        return x;
    }
    void split( int x, int y ) {
        makeroot( x );
        access( y );
        splay( y );
    }
    void link( int x, int y ) {
        makeroot( x );
        if ( findroot( y ) != x )
            f[x] = y;
    }
    void cut( int x, int y ) {
        makeroot( x );
        if ( findroot( y ) == x && f[y] == x && !c[y][0] ) {
            f[y] = c[x][1] = 0;
            pushup( x );
        }
    }
#undef lc
#undef rc
}g;
Last modification:January 17th, 2020 at 07:17 pm
如果您觉得我的文章有用,请赏一颗糖糖。