BZOJ2049: [Sdoi2008]Cave 洞穴勘测

Link-Cut-Tree 模板

此模板不包含进阶的区间操作,仅实现了LCT的基础操作,关于维护更多信息的LCT请参考Splay的操作 -> [Splay 区间模板]

注意:此模板的fa指针为辅助树和原树共用,虚边保证仅连接了fa而不连接ch[]指针。

#include <algorithm> #include <cstring> #include <cstdlib> #include <cstdio> #include <cctype> #include <cassert> #define null 0x0 #define N 200000 + 5 template <typename _Tp> __inline void read(_Tp &a, char c = 0) { for (c = getchar(); !isdigit(c); c = getchar()); for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar()); } int n, m, a, b; class node { public: int fa, ch[2], rev; node() { ch[0] = ch[1] = fa = rev = null; } } tr[N]; __inline void down(int u) { if (tr[u].rev) { if (tr[u].ch[0]) tr[tr[u].ch[0]].rev ^= 1; if (tr[u].ch[1]) tr[tr[u].ch[1]].rev ^= 1; tr[u].rev = 0; std::swap(tr[u].ch[0], tr[u].ch[1]); } } __inline int son(int u) { return tr[tr[u].fa].ch[1] == u; } __inline int isroot(int u) { return tr[tr[u].fa].ch[0] != u && tr[tr[u].fa].ch[1] != u; } __inline void rotate(int u) { int f = tr[u].fa, pf = tr[f].fa, d = son(u); tr[u].fa = pf; if (!isroot(f)) tr[pf].ch[son(f)] = u, tr[u].fa = pf; tr[f].ch[d] = tr[u].ch[d ^ 1]; if (tr[f].ch[d]) tr[tr[f].ch[d]].fa = f; tr[f].fa = u, tr[u].ch[d ^ 1] = f; } int st[N]; inline void splay(int u) { int top = 0; st[++top] = u; for (int v = u; !isroot(v); v = tr[v].fa) st[++top] = tr[v].fa; for (int i = top; i; i--) down(st[i]); while (!isroot(u)) { if (!isroot(tr[u].fa)) rotate(son(u) == son(tr[u].fa) ? tr[u].fa : u); rotate(u); } } inline void access(int u, int t = 0) { while (u) { splay(u); tr[u].ch[1] = t; t = u, u = tr[u].fa; } } inline void makeroot(int u) { access(u); splay(u); tr[u].rev ^= 1; } inline void link(int u, int v) { makeroot(u); tr[u].fa = v; splay(u); } inline void cut(int u, int v) { makeroot(u); access(v); splay(v); tr[u].fa = tr[v].ch[0] = null; } inline int getroot(int u) { access(u); splay(u); while (tr[u].ch[0]) u = tr[u].ch[0]; splay(u); return u; } inline int judge(int u, int v) { return getroot(u) == getroot(v); } int main() { read(n), read(m); while (m--) { char s[10]; scanf("%s", s); read(a), read(b); if (s[0] == 'Q') printf("%s\n", judge(a, b) ? "Yes" : "No"); if (s[0] == 'C') link(a, b); if (s[0] == 'D') cut(a, b); } return 0; }
Code language: PHP (php)

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注