LCT 维护边双 / 点双的模板
2024-09-05 18:27:24
用 \(\text{LCT}\) 维护边双的做法是：加入一条非树边时，将这段树上路径合并为一个点代表这个边双，具体实现用并查集合并点，在 \(\text{Splay}\) 与 \(\text{Access}\) 的过程中对辅助树上父亲做路径压缩。
用 \(\text{LCT}\) 维护点双的做法是：加入一条非树边时，将这段树上路径全部砍断，新建一个点代表这个点双，将原来那些点向新点连虚边。
实现方法：直接用 \(\text{Splay}\) 与 \(\text{Access}\) 提取路径并且 \(\text{DFS}\) 遍历这个路径就可以了。
代码是维护路径桥与割点的个数。 洛谷链接
#include<bits/stdc++.h>
using namespace std;
const int N = 200005;
int n,q,lst;
struct bcj
{
int f[N];
void init()
{
for(int i=1; i<=n; i++)
f[i]=i;
}
int find(int x)
{
return f[x]==x?x:f[x]=find(f[x]);
}
}G;
namespace LCT
{
const int maxn = N;
int ch[maxn][2],fa[maxn],s[maxn],rev[maxn];
#define lc(x) (ch[x][0])
#define rc(x) (ch[x][1])
bcj W;
#define F(x) (W.find(x))
int g(int x)
{
return rc(fa[x]) == x;
}
int nrt(int x)
{
return lc(fa[x]) == x || rc(fa[x]) == x;
}
void pushup(int x)
{
s[x] = s[lc(x)] + s[rc(x)] + 1;
}
void pushdown(int x)
{
if(rev[x])
{
swap(lc(lc(x)), rc(lc(x)));
rev[lc(x)] ^= 1;
swap(lc(rc(x)), rc(rc(x)));
rev[rc(x)] ^= 1;
rev[x] ^= 1;
}
}
void rot(int x)
{
int y = fa[x], v = g(x);
if(nrt(y))
ch[fa[y]][g(y)] = x;
fa[x] = fa[y];
ch[y][v] = ch[x][!v];
fa[ch[x][!v]] = y;
ch[x][!v] = y;
fa[y] = x;
pushup(y);
}
void splay(int x)
{
x = F(x);
int y; vector<int>v;
for(y = x; nrt(y); y = fa[y] = F(fa[y]))
v.push_back(y);
for(pushdown(y); !v.empty(); v.pop_back())
pushdown(v.back());
for(y = fa[x]; nrt(x); rot(x), y = fa[x] = F(fa[x]))
if(nrt(y))
rot(g(x) ^ g(y) ? x : y);
pushup(x);
}
void access(int x)
{
x = F(x);
for(int y = 0; x; y = x, x = fa[x] = F(fa[x]))
{
splay(x);
rc(x) = y;
}
}
void makeroot(int x)
{
x = F(x);
access(x);
splay(x);
swap(lc(x), rc(x));
rev[x] ^= 1;
}
void link(int x, int y)
{
x = F(x); y = F(y);
makeroot(x);
access(y);
splay(y);
fa[x] = y;
}
void dfs_merge(int x, int root)
{
W.f[x] = root;
if(lc(x)) dfs_merge(lc(x), root), lc(x) = 0;
if(rc(x)) dfs_merge(rc(x), root), rc(x) = 0;
}
void zip(int x, int y)
{
x = F(x); y = F(y);
makeroot(x);
access(y);
splay(y);
dfs_merge(y, y);
pushup(y);
}
int query(int x, int y)
{
x = F(x); y = F(y);
makeroot(x);
access(y);
splay(y);
return s[y] - 1;
}
#undef lc
#undef rc
#undef F
}
namespace RST
{
const int maxn = N << 1;
int cnt,ch[maxn][2],fa[maxn],s[maxn],rev[maxn];
#define lc(x) (ch[x][0])
#define rc(x) (ch[x][1])
int g(int x)
{
return rc(fa[x]) == x;
}
int nrt(int x)
{
return lc(fa[x]) == x || rc(fa[x]) == x;
}
void pushup(int x)
{
s[x] = s[lc(x)] + s[rc(x)] + (x <= n);
}
void pushdown(int x)
{
if(rev[x])
{
swap(lc(lc(x)), rc(lc(x)));
rev[lc(x)] ^= 1;
swap(lc(rc(x)), rc(rc(x)));
rev[rc(x)] ^= 1;
rev[x] ^= 1;
}
}
void rot(int x)
{
int y = fa[x], v = g(x);
if(nrt(y))
ch[fa[y]][g(y)] = x;
fa[x] = fa[y];
ch[y][v] = ch[x][!v];
fa[ch[x][!v]] = y;
ch[x][!v] = y;
fa[y] = x;
pushup(y);
}
void splay(int x)
{
int y; vector<int>v;
for(y = x; nrt(y); y = fa[y])
v.push_back(y);
for(pushdown(y); !v.empty(); v.pop_back())
pushdown(v.back());
for(y = fa[x]; nrt(x); rot(x), y = fa[x])
if(nrt(y))
rot(g(x) ^ g(y) ? x : y);
pushup(x);
}
void access(int x)
{
for(int y = 0; x; y = x, x = fa[x])
{
splay(x);
rc(x) = y;
}
}
void makeroot(int x)
{
access(x);
splay(x);
swap(lc(x), rc(x));
rev[x] ^= 1;
}
void link(int x, int y)
{
makeroot(x);
access(y);
splay(y);
fa[x] = y;
}
void dfs_merge(int x, int root)
{
fa[x] = root;
if(lc(x)) dfs_merge(lc(x), root), lc(x) = 0;
if(rc(x)) dfs_merge(rc(x), root), rc(x) = 0;
pushup(x);
}
void zip(int x, int y)
{
makeroot(x);
access(y);
splay(y);
dfs_merge(y, ++cnt);
pushup(cnt);
}
int query(int x, int y)
{
makeroot(x);
access(y);
splay(y);
return s[y];
}
#undef lc
#undef rc
}
int main()
{
scanf("%d %d", &n, &q);
G.init();
LCT::W.init();
RST::cnt = n;
for(int i = 1, opt, x, y; i <= q; i ++)
{
scanf("%d %d %d", &opt, &x, &y);
x = x ^ lst; y = y ^ lst;
if(opt == 1)
{
if(G.find(x) ^ G.find(y))
LCT::link(x, y), RST::link(x, y), G.f[G.find(x)] = G.find(y);
else
LCT::zip(x, y), RST::zip(x, y);
}
if(opt == 2)
{
if(G.find(x) ^ G.find(y))
puts("-1");
else
printf("%d\n", lst = LCT::query(x, y));
}
if(opt == 3)
{
if(G.find(x) ^ G.find(y))
puts("-1");
else
printf("%d\n", lst = RST::query(x, y));
}
}
return 0;
}
最新文章
- js获取鼠标位置的各种方法
- tomocat设置首次访问时的页面
- 安装python爬虫scrapy踩过的那些坑和编程外的思考
- React+Node.js+Express+mongoskin+MongoDB
- 慕课网-安卓工程师初养成-1-5 使用Eclipse开发Java程序
- 使用python获得git中分支存成list
- Jquery ajax请求导出Excel表格
- autocapticalize和autocorrect
- Day1_PHP快速入门
- SQLServer .mdf和.ldf文件
- 修改/etc/resolv.conf又恢复到原来的状态?[转]
- 团队作业4--第一次项目冲刺(Alpha版本) 5
- Python装饰器的进阶
- poj2441状态压缩dp基础
- weex安装失败，按照官网步骤多次失败后成功
- UCS2编码
- 设置环境下文本格式为UTF-8
- oracle sql 高级
- Map<String, String>循环遍历的方法
- java rsa 加解密