This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ei1333/library
#include "structure/develop/link-cut-tree.hpp"
/** * @brief Link-Cut-Tree */ template< typename STp > struct LinkCutTree : STp { using ST = STp; using ST::ST; using Node = typename ST::Node; Node *expose(Node *t) { Node *rp = nullptr; for(Node *cur = t; cur; cur = cur->p) { this->splay(cur); cur->r = rp; this->update(cur); rp = cur; } this->splay(t); return rp; } void link(Node *child, Node *parent) { expose(child); expose(parent); child->p = parent; parent->r = child; this->update(parent); } void cut(Node *child) { expose(child); auto *parent = child->l; child->l = nullptr; parent->p = nullptr; this->update(child); } void evert(Node *t) { expose(t); this->toggle(t); this->push(t); } Node *lca(Node *u, Node *v) { if(get_root(u) != get_root(v)) return nullptr; expose(u); return expose(v); } Node *get_kth(Node *x, int k) { expose(x); while(x) { this->push(x); if(x->r && x->r->sz > k) { x = x->r; } else { if(x->r) k -= x->r->sz; if(k == 0) return x; k -= 1; x = x->l; } } return nullptr; } Node *get_root(Node *x) { expose(x); while(x->l) { this->push(x); x = x->l; } return x; } };
#line 1 "structure/develop/link-cut-tree.hpp" /** * @brief Link-Cut-Tree */ template< typename STp > struct LinkCutTree : STp { using ST = STp; using ST::ST; using Node = typename ST::Node; Node *expose(Node *t) { Node *rp = nullptr; for(Node *cur = t; cur; cur = cur->p) { this->splay(cur); cur->r = rp; this->update(cur); rp = cur; } this->splay(t); return rp; } void link(Node *child, Node *parent) { expose(child); expose(parent); child->p = parent; parent->r = child; this->update(parent); } void cut(Node *child) { expose(child); auto *parent = child->l; child->l = nullptr; parent->p = nullptr; this->update(child); } void evert(Node *t) { expose(t); this->toggle(t); this->push(t); } Node *lca(Node *u, Node *v) { if(get_root(u) != get_root(v)) return nullptr; expose(u); return expose(v); } Node *get_kth(Node *x, int k) { expose(x); while(x) { this->push(x); if(x->r && x->r->sz > k) { x = x->r; } else { if(x->r) k -= x->r->sz; if(k == 0) return x; k -= 1; x = x->l; } } return nullptr; } Node *get_root(Node *x) { expose(x); while(x->l) { this->push(x); x = x->l; } return x; } };