删边操作不好处理,所以先将操作倒序,将删边转化为加边。

考虑对于两个点的询问,若这两点不连通或这两个点分别处于两个不同的边双连通分量中(两点间存在桥)时,是不满足题目要求的。

可以用\(LCT\)来维护原图的一个生成树,原先每条边带有边权,若在原图中或加边过程中出现了环,则在树上这两点之间的边全部边权清零。

此时如果对两点之间求路径权值和,若在原图中这两点处在一个环上,那么权值和肯定为\(0\),同时用并查集维护连通性,就可以对询问进行回答了。

具体实现看代码吧。

\(code:\)

#include<bits/stdc++.h>
#define maxn 300010
#define mk make_pair
using namespace std;
template<typename T> inline void read(T &x)
{
x=0;char c=getchar();bool flag=false;
while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
if(flag)x=-x;
}
int n,m,qu,tot;
int f[maxn],ans[maxn];
int fa[maxn],ch[maxn][2],rev[maxn],val[maxn],sum[maxn],tag[maxn];
char opt[maxn][2];
map<pair<int,int>,int> mp;
struct edge
{
int x,y;
}e[maxn],q[maxn];
int find(int x)
{
return f[x]==x?x:f[x]=find(f[x]);
}
bool check(int x)
{
return ch[fa[x]][1]==x;
}
void pushup(int x)
{
sum[x]=val[x]+sum[ch[x][0]]+sum[ch[x][1]];
}
void pushrev(int x)
{
rev[x]^=1,swap(ch[x][0],ch[x][1]);
}
void pushtag(int x)
{
tag[x]=1,sum[x]=val[x]=0;
}
void pushdown(int x)
{
int ls=ch[x][0],rs=ch[x][1];
if(rev[x]) pushrev(ls),pushrev(rs),rev[x]=0;
if(tag[x]) pushtag(ls),pushtag(rs),tag[x]=0;
}
bool notroot(int x)
{
return ch[fa[x]][0]==x||ch[fa[x]][1]==x;
}
void rotate(int x)
{
int y=fa[x],z=fa[y],k=check(x),w=ch[x][k^1];
if(notroot(y)) ch[z][check(y)]=x;
ch[x][k^1]=y,ch[y][k]=w;
if(w) fa[w]=y;
fa[x]=z,fa[y]=x;
pushup(y),pushup(x);
}
void all(int x)
{
if(notroot(x)) all(fa[x]);
pushdown(x);
}
void splay(int x)
{
all(x);
for(int y;notroot(x);rotate(x))
if(notroot(y=fa[x]))
rotate(check(x)^check(y)?x:y);
pushup(x);
}
void access(int x)
{
for(int y=0;x;y=x,x=fa[x])
splay(x),ch[x][1]=y,pushup(x);
}
void makeroot(int x)
{
access(x),splay(x),pushrev(x);
}
void split(int x,int y)
{
makeroot(x),access(y),splay(y);
}
void link(int x,int y)
{
makeroot(x),fa[x]=y;
}
void Link(int x,int y)
{
f[find(x)]=find(y),val[++tot]=1;
link(x,tot),link(tot,y);
}
int query(int x,int y)
{
split(x,y);
return sum[y];
}
int main()
{
read(n),read(m),read(qu),tot=n;
for(int i=1;i<=n;++i) f[i]=i;
for(int i=1;i<=m;++i)
{
read(e[i].x),read(e[i].y);
if(e[i].x>e[i].y) swap(e[i].x,e[i].y);
}
for(int i=1;i<=qu;++i)
{
scanf("%s",opt[i]),read(q[i].x),read(q[i].y);
if(q[i].x>q[i].y) swap(q[i].x,q[i].y);
if(opt[i][0]=='Z') mp[mk(q[i].x,q[i].y)]=1;
}
for(int i=1;i<=m;++i)
{
int x=e[i].x,y=e[i].y;
if(mp.count(mk(x,y))||find(x)==find(y)) continue;
mp[mk(x,y)]=1,Link(x,y);
}
for(int i=1;i<=m;++i)
{
int x=e[i].x,y=e[i].y;
if(mp.count(mk(x,y))) continue;
split(x,y),pushtag(y);
}
for(int i=qu;i;--i)
{
int x=q[i].x,y=q[i].y;
if(opt[i][0]=='Z')
{
if(find(x)==find(y)) split(x,y),pushtag(y);
else Link(x,y);
}
else
{
ans[i]=query(x,y);
if(find(x)!=find(y)) ans[i]=1;
}
}
for(int i=1;i<=qu;++i)
{
if(opt[i][0]=='P')
{
if(ans[i]) puts("NIE");
else puts("TAK");
}
}
return 0;
}
04-28 04:42