LCT样例输出0,调试了1h了求助
查看原帖
LCT样例输出0,调试了1h了求助
285617
黑影洞人楼主2022/8/25 14:23
#include<cstdio>
#include<algorithm>
#include<map>
#define N 1919810
using namespace std;
int n,m,q,f[N],cnt,ans,we[N];
map<pair<int,int>,int>mp;
struct edge{
	int u,v,w,k,o;
	void in(){scanf("%d%d%d",&u,&v,&w);if(u>v)swap(u,v);}
	bool operator<(const edge &a)const{return w<a.w;}
}e[N];
struct question{
	int u,v,typ,res,k;	
	void in(int i){scanf("%d%d%d",&typ,&u,&v);if(u>v)swap(u,v);k=e[mp[{u,v}]].k;e[k].o=1;}
}a[N]; 
int uu[N],vv[N];
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
struct link_cut_tree{
	int ch[N][2],f[N],st[N],bh[N];
	bool r[N];
	#define lc ch[x][0]
	#define rc ch[x][1]
	void pushup(int x){
		if(e[bh[lc]].w>e[bh[x]].w)bh[x]=bh[lc];
		if(e[bh[rc]].w>e[bh[x]].w)bh[x]=bh[rc];
	}
	void rev(int x){swap(lc,rc),r[x]^=1;}
	int son(int x){return ch[f[x]][1]==x;}
	int nroot(int x){return ch[f[x]][1]==x||ch[f[x]][0]==x;}
	void rotate(int x){
		int y=f[x],z=f[y],k=son(x),w=ch[x][!k];
		if(nroot(y))ch[z][son(y)]=x;
		ch[y][k]=w,ch[x][!k]=y;
		if(w)f[w]=y;
		f[y]=x,f[x]=z;
		pushup(y);
	}
	void pushdown(int x){
		if(r[x]){
			if(lc)rev(lc);
			if(rc)rev(rc);
			r[x]=0;
		}
	}
	void splay(int x){
		int y=x,z=0;
		st[++z]=y;
		while(nroot(y))st[++z]=y=f[y];
		while(z)pushdown(st[z--]);
		while(nroot(x)){
			y=f[x];
			if(nroot(y))rotate(son(x)!=son(y)?x:y);
			rotate(x);
		}
		pushup(x);
	}
	void access(int x){for(int y=0;x;x=f[y=x])splay(x),rc=y,pushup(x);}
	void makeroot(int x){access(x),splay(x),rev(x);}
	void split(int x,int y){makeroot(x),access(y),splay(y);}
	void link(int x,int y){makeroot(x);f[x]=y;}
	void cut(int x,int y){split(x,y);f[x]=ch[y][0]=0;pushup(y);}
}lct;
signed main(){
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=m;i++)e[i].in();
	for(int i=1;i<=n;i++)f[i]=i;
	for(int i=1;i<=m;i++)we[i+n]=e[i].w,e[i].k=i,lct.bh[i+n]=i+n;
	sort(e+1,e+m+1);
	for(int i=1;i<=q;i++)a[i].in(i);
	for(int i=1;i<=m;i++){
		if(e[i].o)continue;
		int u=e[i].u,v=e[i].v,w=e[i].w,k=e[i].k;
		uu[k]=u,vv[k]=v;
		mp[{u,v}]=k;
		if(find(u)==find(v))continue;
		f[find(u)]=find(v);
		ans+=w;
		lct.link(k+n,u);
		lct.link(k+n,v);
		if(++cnt==n-1)break;
	}
	for(int i=q;i>=1;i--){
		int u=a[i].u,v=a[i].v,typ=a[i].typ;
		if(typ==1){
			lct.split(u,v);
			a[i].res=we[lct.bh[v]];
		}else{
			lct.split(u,v);
			int mx=lct.bh[v];
			if(we[mx]>we[a[i].k+n]){
				lct.cut(e[mx-n].u,mx);
				lct.cut(e[mx-n].v,mx);
				lct.link(u,a[i].k+n);
				lct.link(v,a[i].k+n);
			}
		}
	}
	for(int i=1;i<=q;i++)if(a[i].typ==1)printf("%d\n",a[i].res);
	return 0;
}



2022/8/25 14:23
加载中...