BZOJ3069: [Pa2011]Hard Choice 艰难的选择

最新推荐文章于 2021-01-07 20:13:24 发布

sckalrter

最新推荐文章于 2021-01-07 20:13:24 发布

阅读量345

点赞数

分类专栏：线段树 PA 树链剖分

本文链接：https://blog.csdn.net/qq_41798981/article/details/82892637

版权

线段树同时被 3 个专栏收录

2 篇文章

订阅专栏

1 篇文章

订阅专栏

树链剖分

1 篇文章

订阅专栏

博客探讨了一道编程竞赛题目BZOJ3069，作者首先直觉认为解决方案可能是利用LCT（Link-Cut Tree）维护强连通分量，但考虑到复杂性，他提出了一个不寻常的思路。通过离线处理询问，将删除边转化为添加边，并构建原图的生成树。当添加边时，增加路径上边的权值，如果两点间所有边权值大于等于2，则表明存在环，答案为“TAK”，否则为“NIE”。为了避免生成树与未添加的边形成环，需要找到每次操作后的最大生成树。该方法使用树剖来实现，虽然代码量可能比LCT更多，但思路独特。作者还分享了在不同oj平台上的测试结果差异，表达了一些困扰。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

第一眼感觉是LCT维护动态SCC…
想想感觉太码了，于是yy了个思路清奇的做法。
考虑离线询问这样删边就变成了加边。
考虑求出原图的生成树，然后每当加入一条边，就只要把树上两点路径间边权全部加一。
然后若两点间边权全部>=2则说明每条边都至少在一个环上，两点间路径不止一条,答案为TAK否则为NIE。
然后我们发现若求出的是任意生成树，可能造成“与当前不在生成树上的边形成环”的情况，我们只要求出原树关于删除时间的最大生成树即可。
上树剖维护就好了。
然后发现比LCT还码啊…
顺便吐槽一句：我Dbzoj上能A，本机能A,但bzoj狂T不止啊，坑爹死了。在这里插入图片描述
代码：

#include<bits/stdc++.h>
#define inf 1e9
#define mp make_pair
#define ls p*2
#define rs p*2+1
using namespace std;
const int N=200005;
typedef pair<int,int> pii;
int read(){
    int x=0,f=1; char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1; ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
struct Tre{
	int a,tag;
}tree[N<<2];
struct Edg{
	int nxt,poi;
}e[N<<1];
struct Roa{
	int u,v,tim,id;
}ro[N];
struct Que{
	int id,u,v,op;
}q[N];
int dfn[N],u[N],v[N],deep[N],l=0,tid[N],size[N],hs[N],first[N],f[N],fa[N];
int tot=0,top[N],n,m,z,ans[N];
bool use[N];
map<pii,int> ha,gf;
bool cmp(Roa a,Roa b){
	return a.tim>b.tim;
}
void addedge(int u,int v){
	l++;
	e[l].nxt=first[u];
	e[l].poi=v;
	first[u]=l;
}
int find(int x){
	return (f[x]==x)?x:(f[x]=find(f[x]));
}
void dfs(int u,int f){
	deep[u]=deep[f]+1; size[u]=1; fa[u]=f;
	for (int p=first[u];p;p=e[p].nxt){
		int v=e[p].poi;
		if (v==f) continue;
		dfs(v,u);
		if (size[v]>size[hs[u]]) hs[u]=v;
		size[u]+=size[v];
	}
}
void dfs1(int u,int hed){
	top[u]=hed; tid[u]=++tot;
	if (hs[u]) dfs1(hs[u],hed);
	for (int p=first[u];p;p=e[p].nxt){
		int v=e[p].poi;
		if (tid[v]) continue;
		dfs1(v,v);
	}
}
void down(int p,int l,int r){
	tree[ls].a+=tree[p].tag; tree[rs].a+=tree[p].tag;
	tree[ls].tag+=tree[p].tag; tree[rs].tag+=tree[p].tag;
	tree[p].tag=0;
}
void change(int p,int l,int r,int ql,int qr,int y){
	if (ql<=l&&r<=qr){tree[p].a+=y; tree[p].tag+=y; return;}
	if (tree[p].tag) down(p,l,r);
	int mid=(l+r)>>1;
	if (ql<=mid) change(ls,l,mid,ql,qr,y);
	if (qr>mid) change(rs,mid+1,r,ql,qr,y);
	tree[p].a=min(tree[ls].a,tree[rs].a);
}
void edit(int p,int l,int r,int x,int y){
	if (l==r){tree[p].a+=y; return;}
	int mid=(l+r)>>1;
	if (tree[p].tag) down(p,l,r);
	if (x<=mid) edit(ls,l,mid,x,y);
	else edit(rs,mid+1,r,x,y);
	tree[p].a=min(tree[ls].a,tree[rs].a);
}
int ask(int p,int l,int r,int ql,int qr){
	if (ql<=l&&r<=qr) return tree[p].a;
	if (tree[p].tag) down(p,l,r);
	int mid=(l+r)>>1,ans=inf;
	if (ql<=mid) ans=min(ans,ask(ls,l,mid,ql,qr));
	if (qr>mid) ans=min(ans,ask(rs,mid+1,r,ql,qr));
	return ans;
}
int lca(int x,int y){
	while (top[x]!=top[y]){
		if (deep[top[x]]<deep[top[y]]) swap(x,y);
		x=fa[top[x]];
	}
	if (deep[x]<deep[y]) swap(x,y);
	return y;
}
void modify(int x,int y){
	int lc=lca(x,y);
	while (top[x]!=top[y]){
		if (deep[top[x]]<deep[top[y]]) swap(x,y);
		change(1,1,n,tid[top[x]],tid[x],1);
		x=fa[top[x]];
	}
	if (tid[x]>tid[y]) swap(x,y);
	change(1,1,n,tid[x],tid[y],1);
	edit(1,1,n,tid[lc],-1);
}
int query(int x,int y){
	int lc=lca(x,y),ans=inf;
	edit(1,1,n,tid[lc],n);
	while (top[x]!=top[y]){
		if (deep[top[x]]<deep[top[y]]) swap(x,y);
		ans=min(ans,ask(1,1,n,tid[top[x]],tid[x]));
		x=fa[top[x]];
	}
	if (tid[x]>tid[y]) swap(x,y);
	ans=min(ans,ask(1,1,n,tid[x],tid[y]));
	edit(1,1,n,tid[lc],-n);
	return ans;
}
int main(){
	n=read(),m=read(),z=read();
	for (int i=1;i<=n;i++) f[i]=i;
	for (int i=1;i<=m;i++){
		u[i]=read(),v[i]=read();
		ro[i].tim=z+1; ro[i].u=u[i]; ro[i].v=v[i];
		gf[mp(u[i],v[i])]=gf[mp(v[i],u[i])]=i; ro[i].id=i;
	}
	for (int i=1;i<=z;i++){
		char ch[5]; scanf("%s",ch+1);
		if (ch[1]=='Z'){
			q[i].op=1; int u=read(),v=read(); ha[mp(u,v)]=ha[mp(v,u)]=1;
			q[i].u=u,q[i].v=v,q[i].id=i;
			ro[gf[mp(u,v)]].tim=i;
		}else{
			q[i].op=2; q[i].u=read(); q[i].v=read(); q[i].id=i;
		}
	}
	sort(ro+1,ro+1+m,cmp);
	for (int i=1;i<=m;i++){
		int u=ro[i].u,v=ro[i].v;
		if (find(u)==find(v)) continue;
		f[find(u)]=find(v);
		use[ro[i].id]=1;
		addedge(u,v); addedge(v,u);
	}
	for (int i=1;i<=n;i++)
	if (!fa[i]) dfs(i,i);
	for (int i=1;i<=n;i++)
	if (!tid[i]) dfs1(i,i);
	for (int i=1;i<=n;i++) f[i]=i;
	for (int i=1;i<=m;i++){
		if (ha[mp(u[i],v[i])]==0){f[find(u[i])]=find(v[i]); 
		modify(u[i],v[i]); }
	}
	for (int i=z;i>=1;i--){
		if (q[i].op==2){
			if (find(q[i].u)!=find(q[i].v)){ans[q[i].id]=1; continue;}
			int p=query(q[i].u,q[i].v);
			if (p>=2) ans[q[i].id]=2; else ans[q[i].id]=1;
		}else{
			modify(q[i].u,q[i].v); f[find(q[i].u)]=find(q[i].v);
		}
	}
	for (int i=1;i<=z;i++){
		if (q[i].op==1) continue;
		if (ans[i]==2) printf("TAK\n"); else printf("NIE\n");
	}
	return 0;
}