LCT
struct LinkCutTree {
struct Node {
int ch[2];
int fa;
int rev_tag;
// ...
};
vector<Node> tree;
map<pair<int, int>, bool> edge;
void init(int n /* ... */) {
tree.resize(n + 10);
for (int i = 1; i <= n; ++i) {
tree[i].ch[0] = tree[i].ch[1] = tree[i].fa = tree[i].rev_tag = 0;
// ...
}
}
void pushUp(int x) {
// ...
}
void pushDown(int x) {
if (tree[x].rev_tag) {
swap(tree[tree[x].ch[0]].ch[0], tree[tree[x].ch[0]].ch[1]);
tree[tree[x].ch[0]].rev_tag ^= 1;
swap(tree[tree[x].ch[1]].ch[0], tree[tree[x].ch[1]].ch[1]);
tree[tree[x].ch[1]].rev_tag ^= 1;
tree[x].rev_tag = 0;
}
// ...
}
int get(int x) { return tree[tree[x].fa].ch[1] == x; }
int isRoot(int x) { return tree[tree[x].fa].ch[0] != x && tree[tree[x].fa].ch[1] != x; }
void rotate(int x) {
int y = tree[x].fa, z = tree[y].fa, t = get(x);
if (!isRoot(y)) tree[z].ch[get(y)] = x;
tree[y].ch[t] = tree[x].ch[t ^ 1], tree[tree[x].ch[t ^ 1]].fa = y;
tree[x].ch[t ^ 1] = y, tree[y].fa = x;
tree[x].fa = z;
pushUp(y);
}
void update(int x) {
if (!isRoot(x)) update(tree[x].fa);
pushDown(x);
}
void splay(int x) {
update(x);
for (int fa = tree[x].fa; !isRoot(x); rotate(x), fa = tree[x].fa) {
if (!isRoot(fa)) rotate(get(fa) == get(x) ? fa : x);
}
pushUp(x);
}
int access(int x) {
splay(x);
tree[x].ch[1] = 0, pushUp(x);
while (tree[x].fa) {
int fa = tree[x].fa;
splay(fa), tree[fa].ch[1] = x, pushUp(fa);
x = fa;
}
return x;
}
void makeRoot(int x) {
access(x), splay(x);
swap(tree[x].ch[0], tree[x].ch[1]);
tree[x].rev_tag ^= 1;
}
int findRoot(int x) {
x = access(x);
pushDown(x);
while (tree[x].ch[0]) x = tree[x].ch[0], pushDown(x);
splay(x);
return x;
}
void link(int x, int y) {
if (findRoot(x) == findRoot(y)) return;
makeRoot(x), tree[x].fa = y;
edge[make_pair(x, y)] = edge[make_pair(y, x)] = 1;
}
void cut(int x, int y) {
if (!edge[make_pair(x, y)]) return;
makeRoot(x), access(x), splay(y), tree[y].fa = 0;
edge[make_pair(x, y)] = edge[make_pair(y, x)] = 0;
}
int split(int x, int y) {
makeRoot(x);
return access(y);
}
// ...
} LCT;
标签:Node,...,struct,int,tree,板子
From: https://www.cnblogs.com/zzzYheng/p/17644728.html