简介
Link-Cut-Tree
是一种数据结构,我们用它来解决动态树问题。Link-Cut-Tree
,简称 LCT, 但它不叫动态树,动态树是指一类问题。Splay Tree
是 LCT 的基础,但是LCT
的Splay 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;
版权声明:本文是原创文章,版权归 星雾月雨 所有。
本文链接:https://www.ariels.xyz/archives/link-cut-tree.html
本站所有下方标记为「允许规范转载」的原创文章均采用 署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。
您可以自由地转载,但请务必注明文章来源且不可用于商业目的。