洛谷P4219 [BJOI2014]大融合（LCT，Splay）

LCT维护子树信息的思路总结与其它问题详见我的LCT总结

思路分析

动态连边，LCT题目跑不了了。然而这题又有点奇特的地方。

我们分析一下，查询操作就是要让我们求出砍断这条边后，x和y各自子树大小的乘积。

掌握了LCT如何维护虚子树信息和后，做法就很清晰了。split(x,y)后，输出x的虚子树和+1与y的虚子树和+1的乘积；或者，（以y为根）输出x的子树总和与y的子树总和减去x的子树总和的乘积。

代码如下（这次我试着写了一个单旋"Spaly"，好像常数还小不少。。。。。。）

#include<cstdio>

#include<cstdlib>

#define R register int

#define I inline void

const int N=100009;

int f[N],c[N][2],si[N],s[N];

bool r[N];

#define lc c[x][0]

#define rc c[x][1]

inline bool nroot(R x){return c[f[x]][0]==x||c[f[x]][1]==x;}

I pushup(R x){

	s[x]=s[lc]+s[rc]+si[x]+1;

}

I pushdown(R x){

	if(r[x]){

		R t=lc;lc=rc;rc=t;

		r[lc]^=1;r[rc]^=1;r[x]=0;

	}

}

I pushall(R x){

	if(nroot(x))pushall(f[x]);

	pushdown(x);

}

I rotate(R x){

	R y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];

	if(nroot(y))c[z][c[z][1]==y]=x;c[x][!k]=y;c[y][k]=w;

	f[w]=y;f[y]=x;f[x]=z;

	pushup(y);

}

I splay(R x){//请忽略这个spaly

	pushall(x);

	while(nroot(x))rotate(x);

	pushup(x);

}

I access(R x){

	for(R y=0;x;x=f[y=x]){

		splay(x);

		si[x]+=s[rc];

		si[x]-=s[rc=y];

		//pushup(x);试着去掉，发现对答案无影响

	}

}

I makeroot(R x){

	access(x);splay(x);

	r[x]^=1;

}

I split(R x,R y){

	makeroot(x);

    access(y);splay(y);

}

I link(R x,R y){

	split(x,y);

	si[f[x]=y]+=s[x];

	pushup(y);

}//LCT模板到此结束

#define G ch=getchar()

#define gc G;while(ch<'-')G

#define in(z) gc;z=ch&15;G;while(ch>'-')z*=10,z+=ch&15,G;

int main(){

	register char ch;

	register bool fl;

	R n,q,u,v;

	in(n);in(q);

	for(R i=1;i<=n;++i)s[i]=1;

	while(q--){

		gc;fl=ch=='A';in(u);in(v);

		if(fl)link(u,v);

		else{

			split(u,v);

			printf("%lld\n",(long long)(si[u]+1)*(si[v]+1));//可以换成上面提到的另一种

		}

	}

	return 0;

}

巴特西

洛谷P4219 [BJOI2014]大融合（LCT，Splay）

思路分析

最新文章

热门文章