Luzhiled's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ei1333/library

:warning: Euler-Tour-Tree
(structure/lct/euler-tour-tree.hpp)

Code

/**
 * @brief Euler-Tour-Tree
 */
template< typename T >
struct EulerTourTree {

private:

  struct Node {
    Node *l, *r, *p;
    size_t sz;

    explicit Node() : sz(1), l(nullptr), r(nullptr), p(nullptr) {}

    bool is_root() const {
      return not p or (p->l != this and p->r != this);
    }
  };

  using NP = Node *;

  NP update(NP t) {
    t->sz = 1;
    if(t->l) t->sz += t->l->sz;
    if(t->r) t->sz += t->r->sz;
    return t;
  }

  void rotr(NP t) {
    NP x = t->p, y = x->p;
    if((x->l = t->r)) t->r->p = x;
    t->r = x, x->p = t;
    update(x), update(t);
    if((t->p = y)) {
      if(y->l == x) y->l = t;
      if(y->r == x) y->r = t;
      update(y);
    }
  }

  void rotl(NP t) {
    NP x = t->p, y = x->p;
    if((x->r = t->l)) t->l->p = x;
    t->l = x, x->p = t;
    update(x), update(t);
    if((t->p = y)) {
      if(y->l == x) y->l = t;
      if(y->r == x) y->r = t;
      update(y);
    }
  }

  void splay(NP t) {
    while(not t->is_root()) {
      NP q = t->p;
      if(q->is_root()) {
        if(q->l == t) rotr(t);
        else rotl(t);
      } else {
        NP r = q->p;
        if(r->l == q) {
          if(q->l == t) rotr(q), rotr(t);
          else rotl(t), rotr(t);
        } else {
          if(q->r == t) rotl(q), rotl(t);
          else rotr(t), rotl(t);
        }
      }
    }
  }

  NP splay_front(NP t) {
    splay(t);
    while(t->l) t = t->l;
    splay(t);
    return t;
  }

  NP splay_back(NP t) {
    splay(t);
    while(t->r) t = t->r;
    splay(t);
    return t;
  }

  template< typename... Args >
  NP merge(NP p, Args... args) {
    return merge(p, merge(args...));
  }

  NP merge(NP l, NP r) {
    if(!l && !r) return nullptr;
    if(!l) return splay(r), r;
    if(!r) return splay(l), l;
    splay(l), splay(r);
    l = splay_back(l);
    l->r = r;
    r->p = l;
    update(l);
    return l;
  }


  NP alloc() {
    return new Node();
  }

  NP reroot(NP t) {
    splay(t);
    NP l = t->l;
    if(not l) return t;
    t->l = nullptr;
    update(t);
    return merge(l, t);
  }

  NP link(NP u, NP v, NP e1, NP e2) {
    u = reroot(u);
    v = reroot(v);
    return merge(u, e1, v, e2);
  }

  NP cut(NP e1, NP e2) {
    splay(e1);
    splay(e2);
    NP p = e1->p;
    bool is_r;
    if(p != e2) {
      is_r = p == e2->r;
      p->p = nullptr;
      if(e1 == p->l) rotr(e1);
      else rotl(e1);
    } else {
      is_r = e1 == e2->r;
    }
    if(e1->l) {
      e1->l->p = nullptr;
    }
    if(e1->r) {
      e1->r->p = nullptr;
    }
    if(is_r) {
      if(e2->l) e2->l->p = nullptr;
      return merge(e2->l, e1->r);
    } else {
      if(e2->r) e2->r->p = nullptr;
      return merge(e1->l, e2->r);
    }
  }

  bool is_connected(NP u, NP v) {
    splay(u);
    splay(v);
    return u->p != nullptr;
  }

  vector< unordered_map< int, NP > > ptr;

  NP get_node(int l, int r) {
    if(ptr[l].find(r)) {
      ptr[l][r] = alloc();
    }
    return ptr[l][r];
  }

public:
  EulerTourTree() = default;

  explicit EulerTourTree(int n) : ptr(n) {}

  void reroot(int k) {
    reroot(get_node(k, k));
  }

  void link(int u, int v) {
    ptr[u][v] = alloc();
    ptr[v][u] = alloc();
    link(get_node(u, u), get_node(v, v), ptr[u][v], ptr[v][u]);
  }

  void cut(int u, int v) {
    auto it1 = ptr[u].find(v);
    auto it2 = ptr[v].find(u);
    cut(it1, it2);
    ptr[u].erase(it1);
    ptr[v].erase(it2);
  }

  bool is_conneced(int u, int v) {
    return is_connected(get_node(u, u), get_node(v, v));
  }
};
#line 1 "structure/lct/euler-tour-tree.hpp"
/**
 * @brief Euler-Tour-Tree
 */
template< typename T >
struct EulerTourTree {

private:

  struct Node {
    Node *l, *r, *p;
    size_t sz;

    explicit Node() : sz(1), l(nullptr), r(nullptr), p(nullptr) {}

    bool is_root() const {
      return not p or (p->l != this and p->r != this);
    }
  };

  using NP = Node *;

  NP update(NP t) {
    t->sz = 1;
    if(t->l) t->sz += t->l->sz;
    if(t->r) t->sz += t->r->sz;
    return t;
  }

  void rotr(NP t) {
    NP x = t->p, y = x->p;
    if((x->l = t->r)) t->r->p = x;
    t->r = x, x->p = t;
    update(x), update(t);
    if((t->p = y)) {
      if(y->l == x) y->l = t;
      if(y->r == x) y->r = t;
      update(y);
    }
  }

  void rotl(NP t) {
    NP x = t->p, y = x->p;
    if((x->r = t->l)) t->l->p = x;
    t->l = x, x->p = t;
    update(x), update(t);
    if((t->p = y)) {
      if(y->l == x) y->l = t;
      if(y->r == x) y->r = t;
      update(y);
    }
  }

  void splay(NP t) {
    while(not t->is_root()) {
      NP q = t->p;
      if(q->is_root()) {
        if(q->l == t) rotr(t);
        else rotl(t);
      } else {
        NP r = q->p;
        if(r->l == q) {
          if(q->l == t) rotr(q), rotr(t);
          else rotl(t), rotr(t);
        } else {
          if(q->r == t) rotl(q), rotl(t);
          else rotr(t), rotl(t);
        }
      }
    }
  }

  NP splay_front(NP t) {
    splay(t);
    while(t->l) t = t->l;
    splay(t);
    return t;
  }

  NP splay_back(NP t) {
    splay(t);
    while(t->r) t = t->r;
    splay(t);
    return t;
  }

  template< typename... Args >
  NP merge(NP p, Args... args) {
    return merge(p, merge(args...));
  }

  NP merge(NP l, NP r) {
    if(!l && !r) return nullptr;
    if(!l) return splay(r), r;
    if(!r) return splay(l), l;
    splay(l), splay(r);
    l = splay_back(l);
    l->r = r;
    r->p = l;
    update(l);
    return l;
  }


  NP alloc() {
    return new Node();
  }

  NP reroot(NP t) {
    splay(t);
    NP l = t->l;
    if(not l) return t;
    t->l = nullptr;
    update(t);
    return merge(l, t);
  }

  NP link(NP u, NP v, NP e1, NP e2) {
    u = reroot(u);
    v = reroot(v);
    return merge(u, e1, v, e2);
  }

  NP cut(NP e1, NP e2) {
    splay(e1);
    splay(e2);
    NP p = e1->p;
    bool is_r;
    if(p != e2) {
      is_r = p == e2->r;
      p->p = nullptr;
      if(e1 == p->l) rotr(e1);
      else rotl(e1);
    } else {
      is_r = e1 == e2->r;
    }
    if(e1->l) {
      e1->l->p = nullptr;
    }
    if(e1->r) {
      e1->r->p = nullptr;
    }
    if(is_r) {
      if(e2->l) e2->l->p = nullptr;
      return merge(e2->l, e1->r);
    } else {
      if(e2->r) e2->r->p = nullptr;
      return merge(e1->l, e2->r);
    }
  }

  bool is_connected(NP u, NP v) {
    splay(u);
    splay(v);
    return u->p != nullptr;
  }

  vector< unordered_map< int, NP > > ptr;

  NP get_node(int l, int r) {
    if(ptr[l].find(r)) {
      ptr[l][r] = alloc();
    }
    return ptr[l][r];
  }

public:
  EulerTourTree() = default;

  explicit EulerTourTree(int n) : ptr(n) {}

  void reroot(int k) {
    reroot(get_node(k, k));
  }

  void link(int u, int v) {
    ptr[u][v] = alloc();
    ptr[v][u] = alloc();
    link(get_node(u, u), get_node(v, v), ptr[u][v], ptr[v][u]);
  }

  void cut(int u, int v) {
    auto it1 = ptr[u].find(v);
    auto it2 = ptr[v].find(u);
    cut(it1, it2);
    ptr[u].erase(it1);
    ptr[v].erase(it2);
  }

  bool is_conneced(int u, int v) {
    return is_connected(get_node(u, u), get_node(v, v));
  }
};
Back to top page