题意
维护一张无向图,要求支持以下操作:
- 切断一条边。
- 查询两个点是否有有两条完全不同的路径相连。
分析
因为断边操作不好维护,考虑离线后将断边变为加边。
因此,我们只需要维护加边操作即可。
考虑使用 LCT。
首先,因为涉及到边权,套路地用节点代替边。
如果某一条边连接的两个点属于两个不同的连通块,那么直接连边。
如果一条边连接的两个点属于同一个连通块,我们可以在它所连接的两点的路径上将所有的节点的权值 \(+1\),表示这些节点可以由两条路径连接。
查询的时候,如果两点之间的所有节点的权值都大于 \(1\),那么就满足,否则不满足。
所以我们只需要支持区间加和查询最小值即可。
Code
#include<bits/stdc++.h>
using namespace std;
namespace LCT
{
struct node
{
node *ch[2], *fa;
bool rev;
int v, mn, tag;
node(int x=0) {v=x, mn=x, rev=0, ch[0]=ch[1]=fa=0, tag=0;}
bool not_root() {return fa&&(fa->ch[0]==this||fa->ch[1]==this);}
bool is_rson() {return this==fa->ch[1];}
void reverse() {rev^=1;swap(ch[0], ch[1]);}
void add(int w) {tag+=w; mn+=w; v+=w;}
void push_up()
{
mn=v;
if(ch[0]) mn=min(mn, ch[0]->mn);
if(ch[1]) mn=min(mn, ch[1]->mn);
}
void push_down()
{
if(rev)
{
if(ch[0]) ch[0]->reverse();
if(ch[1]) ch[1]->reverse();
rev^=1;
}
if(tag)
{
if(ch[0]) ch[0]->add(tag);
if(ch[1]) ch[1]->add(tag);
tag=0;
}
}
};
void rotate(node *x)
{
bool k=x->is_rson();
node *y=x->fa, *z=y->fa, *w=x->ch[!k];
if(y->not_root()) z->ch[y->is_rson()]=x;
x->ch[!k]=y, y->ch[k]=w;
y->fa=x, x->fa=z;
if(w) w->fa=y;
y->push_up();
x->push_up();
}
stack<node*> s;
void splay(node *x)
{
s.emplace(x);
while(s.top()->not_root()) s.emplace(s.top()->fa);
while(!s.empty()) s.top()->push_down(), s.pop();
while(x->not_root())
{
if(x->fa->not_root())
rotate((x->is_rson()^x->fa->is_rson())?x:x->fa);
rotate(x);
}
}
void access(node *x)
{
for(node *y=0;x;x=(y=x)->fa)
splay(x), x->ch[1]=y, x->push_up();
}
void make_root(node *x)
{
access(x);
splay(x);
x->reverse();
}
node *find_root(node *x)
{
access(x);
splay(x);
while(x->push_down(), x->ch[0])
x=x->ch[0];
return x;
}
void link(node *x, node *y)
{
if(find_root(x)!=find_root(y))
make_root(x), x->fa=y;
}
void cut(node *x, node *y)
{
make_root(x);
access(y);
splay(y);
if(y->ch[0]==x) y->ch[0]=x->fa=0;
}
int query(node *x, node *y)
{
make_root(x);
access(y);
splay(y);
return y->mn;
}
void modify(node *x, node *y)
{
make_root(x);
access(y);
splay(y);
y->add(1);
}
}
set<pair<int, int>> s;
LCT::node *rt[100005];
vector<tuple<int, int, int>> vc;
vector<bool> ans;
int main()
{
int n, m, q;
cin>>n>>m>>q;
for(int i=1;i<=n;i++) rt[i]=new LCT::node;
for(int i=1, u, v;i<=m;i++)
{
cin>>u>>v;
if(u>v) swap(u, v);
s.emplace(u, v);
}
char c;
for(int i=1, x, y;i<=q;i++)
{
cin>>c>>x>>y;
if(c=='Z')
{
vc.emplace_back(1, x, y);
if(x>y) swap(x, y);
s.erase({x, y});
}
if(c=='P') vc.emplace_back(2, x, y);
}
for(auto [u, v]:s)
{
if(find_root(rt[u])==find_root(rt[v]))
modify(rt[u], rt[v]);
else
{
LCT::node *eg=new LCT::node;
link(rt[u], eg), link(eg, rt[v]);
}
}
for(auto [op, u, v]:views::reverse(vc))
{
if(op==1)
{
if(find_root(rt[u])==find_root(rt[v]))
modify(rt[u], rt[v]);
else
{
LCT::node *eg=new LCT::node;
link(rt[u], eg), link(eg, rt[v]);
}
}
else
{
int w=0;
if(find_root(rt[u])==find_root(rt[v]))
w=query(rt[u], rt[v]);
ans.emplace_back(w);
}
}
for(auto op:views::reverse(ans))
cout<<(op?"TAK\n":"NIE\n");
}
标签:node,rt,ch,题解,void,Hard,Choice,fa,root
From: https://www.cnblogs.com/redacted-area/p/18429467