4.17 省选模拟赛远行 LCT 启发式合并倍增

容易写出nQ的暴力由于数据是期望的时间所以直接dfs可以跑的很快可以拿到70分。

当然可以进一步优化暴力使用换根dp 然后可以将暴力优化到n^2.

const int MAXN=300010;

int n,Q,T,len,maxx;

int lin[MAXN],d[MAXN],ver[MAXN<<1],nex[MAXN<<1];

inline void add(int x,int y)

{

	ver[++len]=y;

	nex[len]=lin[x];

	lin[x]=len;

}

inline void dfs(int x,int y)

{

	d[x]=d[y]+1;

	maxx=max(maxx,d[x]-1);

	go(x)if(tn!=y)dfs(tn,x);

}

int main()

{

	freopen("hike.in","r",stdin);

	freopen("hike.out","w",stdout);

	get(T);get(n);get(Q);

	rep(1,Q,i)

	{

		int op,x,y;

		get(op);get(x)^(T*maxx);

		if(op==1)get(y)^(T*maxx),add(x,y),add(y,x);

		else maxx=0,dfs(x,0),put(maxx);

	}

	return 0;

}

考虑离线。可以发现每次还是需要暴力。

进一步思考树上和一个点的最远点有什么特殊性质。

不难想到树的直径可以发现一个点的最远点一定是直降两端之一.

这个不难证明。分情况讨论这条路径是否穿过直径来讨论。

那么其实我们要维护一个联通树的直降两端即可。

离线可以先把树给建出来。

然后合并两个集合的最远点也比较简单可以证明新的直径的两端在这4个点之中。

至于证明和上面差不多也是分类讨论。

这样我们可以利用原树的倍增数组来求两点之间距离。

考虑在线发现两点距离难求出考虑启发式合并然后暴力重新处理倍增数组。

这样每个点最多被重构logn次每次倍增数组的更新也就是nlog^2+Qlogn 这个虽然已经可以通过了。

但是考虑更优的做法。

维护树的联通性容易想到 LCT.

连边的时候维护一下这个连通块的直径端点即可。两点之间的距离也比较好求。

一个设为根一个access 最后查splay大小即可。

复杂度 nlogn+Qlogn.

const int MAXN=300010;

int n,Q,T,maxx,top;

int f[MAXN],L[MAXN],s[MAXN],R[MAXN],re[MAXN],fa[MAXN],c[MAXN][2],sz[MAXN];//sz[x]表示x所在splay中的节点个数.

inline int getfather(int x){return x==fa[x]?x:fa[x]=getfather(fa[x]);}

inline int pd(int x){return c[f[x]][1]==x||c[f[x]][0]==x;}

inline void rev(int x)

{

	if(!x)return;

	swap(c[x][0],c[x][1]);

	re[x]^=1;

}

inline void pushup(int x)

{

	sz[x]=sz[c[x][0]]+sz[c[x][1]]+1;

}

inline void pushdown(int x){if(re[x])rev(c[x][0]),rev(c[x][1]),re[x]=0;}

inline void rotate(int x)

{

	int old=f[x],oldf=f[old],k=c[old][1]==x;

	c[old][k]=c[x][k^1];c[x][k^1]=old;

	if(pd(old))c[oldf][c[oldf][1]==old]=x;

	if(c[old][k])f[c[old][k]]=old;

	f[old]=x;f[x]=oldf;pushup(old);

}

inline void splay(int x)

{

	int y=x;top=0;

	s[++top]=y;

	while(pd(y))s[++top]=y=f[y];

	while(top)pushdown(s[top--]);

	while(pd(x))

	{

		int old=f[f[x]];

		if(pd(f[x]))rotate(((c[f[x]][0]==x)^(c[old][0]==f[x]))?x:f[x]);

		rotate(x);

	}

	pushup(x);return;

}

inline void access(int x)

{

	for(int y=0;x;x=f[y=x])

	{

		splay(x);

		c[x][1]=y;

		pushup(x);

	}

}

inline void make_root(int x)

{

	access(x);splay(x);

	rev(x);

}

inline int dis(int x,int y)

{

	make_root(x);

	access(y);

	splay(y);

	return sz[y];

}

inline void merge(int x,int y)

{

	int xx=getfather(x);

	int yy=getfather(y);

	int s1,s2,s3,s4;

	s1=L[xx],s2=L[yy];

	s3=R[xx],s4=R[yy];

	int l=0,r=0,w=0;

	int ww=dis(s1,s2);

	if(ww>w)w=ww,l=s1,r=s2;

	ww=dis(s1,s3);

	if(ww>w)w=ww,l=s1,r=s3;

	ww=dis(s1,s4);

	if(ww>w)w=ww,l=s1,r=s4;

	ww=dis(s2,s3);

	if(ww>w)w=ww,l=s2,r=s3;

	ww=dis(s2,s4);

	if(ww>w)w=ww,l=s2,r=s4;

	ww=dis(s3,s4);

	if(ww>w)w=ww,l=s3,r=s4;

	fa[xx]=yy;L[yy]=l;R[yy]=r;

}

inline void LINK(int x,int y)

{

	make_root(x);f[x]=y;

	merge(x,y);

}

int main()

{

	freopen("1.in","r",stdin);

	get(T);get(n);get(Q);

	rep(1,n,i)sz[i]=1,L[i]=R[i]=i,fa[i]=i;

	rep(1,Q,i)

	{

		int op,x,y;

		get(op);get(x)^(T*maxx);

		if(op==1)get(y)^(T*maxx),LINK(x,y);

		else

		{

			int xx=getfather(x);

			maxx=max(dis(x,L[xx]),dis(x,R[xx]))-1;

			put(maxx);

		}

	}

	return 0;

}

巴特西

4.17 省选模拟赛远行 LCT 启发式合并倍增

最新文章

热门文章

巴特西

4.17 省选模拟赛 远行 LCT 启发式合并 倍增

最新文章

热门文章

4.17 省选模拟赛远行 LCT 启发式合并倍增