首页 > 其他 > 详细

[LOJ6038]远行

时间:2018-01-21 13:34:32      阅读:89      评论:0      收藏:0      [点我收藏+]

标签:oid   自己   有变   access   pri   include   light   并查集   make   

用合并直径的定理,并查集维护每棵树的直径

主要是看看过了这么久自己的lct有没有变残废2333(1A还行

#include<stdio.h>
int ch[300010][2],fa[300010],r[300010],siz[300010],sfa[300010],d1[300010],d2[300010];
void pushup(int x){siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;}
void swap(int&a,int&b){a^=b^=a^=b;}
void rev(int x){
	r[x]^=1;
	swap(ch[x][0],ch[x][1]);
}
void pushdown(int x){
	if(r[x]){
		if(ch[x][0])rev(ch[x][0]);
		if(ch[x][1])rev(ch[x][1]);
		r[x]=0;
	}
}
bool isrt(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
void rot(int x){
	int y,z,f,B;
	y=fa[x];
	z=fa[y];
	f=(ch[y][0]==x);
	B=ch[x][f];
	fa[x]=z;
	fa[y]=x;
	if(B)fa[B]=y;
	ch[x][f]=y;
	ch[y][f^1]=B;
	if(ch[z][0]==y)ch[z][0]=x;
	if(ch[z][1]==y)ch[z][1]=x;
	pushup(y);
	pushup(x);
}
void gao(int x){
	if(fa[x])gao(fa[x]);
	pushdown(x);
}
void splay(int x){
	gao(x);
	int y,z;
	while(!isrt(x)){
		y=fa[x];
		z=fa[y];
		if(!isrt(y))rot((ch[z][0]==y&&ch[y][0]==x)||(ch[z][1]==y&&ch[y][1]==x)?y:x);
		rot(x);
	}
}
void access(int x){
	int y=0;
	while(x){
		splay(x);
		ch[x][1]=y;
		pushup(x);
		y=x;
		x=fa[x];
	}
}
void makert(int x){
	access(x);
	splay(x);
	rev(x);
}
void link(int x,int y){
	makert(x);
	fa[x]=y;
}
int query(int x,int y){
	makert(x);
	access(y);
	splay(y);
	return siz[y]-1;
}
int getfa(int x){return(x==sfa[x])?x:(sfa[x]=getfa(sfa[x]));}
int max(int a,int b){return a>b?a:b;}
int main(){
	int type,n,m,i,j,x,y,mx,p1,p2,las,tmp,t[4];
	scanf("%d%d%d",&type,&n,&m);
	for(i=1;i<=n;i++){
		siz[i]=1;
		sfa[i]=d1[i]=d2[i]=i;
	}
	las=0;
	while(m--){
		scanf("%d",&i);
		if(i==1){
			scanf("%d%d",&x,&y);
			if(type==1){
				x^=las;
				y^=las;
			}
			link(x,y);
			x=getfa(x);
			y=getfa(y);
			t[0]=d1[x];
			t[1]=d2[x];
			t[2]=d1[y];
			t[3]=d2[y];
			mx=0;
			for(i=0;i<3;i++){
				for(j=i+1;j<4;j++){
					tmp=query(t[i],t[j]);
					if(tmp>mx){
						mx=tmp;
						p1=t[i];
						p2=t[j];
					}
				}
			}
			d1[x]=p1;
			d2[x]=p2;
			sfa[y]=x;
		}else{
			scanf("%d",&x);
			if(type==1)x^=las;
			y=getfa(x);
			las=max(query(x,d1[y]),query(x,d2[y]));
			printf("%d\n",las);
		}
	}
}

[LOJ6038]远行

标签:oid   自己   有变   access   pri   include   light   并查集   make   

原文:https://www.cnblogs.com/jefflyy/p/8323813.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号