[bzoj4530][Bjoi2014]大融合

大融合 bzoj-4530 Bjoi-2014

题目大意：n个点，m个操作，支持：两点连边；查询两点负载：负载。边(x,y)的负载就是将(x,y)这条边断掉后能和x联通的点的数量乘以能和y联通的点的数量。数据保证任意时刻，点和边构成的都是森林或者树。

注释：$1\le n,m\le 10^5$。

想法：新学了一发LCT维护子树信息，更一道例题。

话说LCT维护子树信息应该怎么做？其实也非常简单。我们只需要将所有的信息都加到父节点上即可。

具体的，我们除了维护子树和sum之外另维护一个值other，表示这个节点的所有虚儿子的子树和。

然后这东西在access中将所有儿子都扔了的之后更新一下。

然后insert的时候更新一下即可。

然后维护我们用pushup维护。

最后，附上丑陋的代码... ...

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define ls ch[p][0]

#define rs ch[p][1]

#define get(x) (ch[f[x]][1]==x)

#define N 100010

using namespace std;

typedef long long ll;

int ch[N][2],oth[N],sum[N],f[N];

bool rev[N];

inline bool isroot(int p)

{

	// puts("Fuck:isroot");

	return ch[f[p]][0]!=p&&ch[f[p]][1]!=p;

}

inline void pushup(int p)

{

	// puts("Fuck:pushup");

	sum[p]=sum[ls]+sum[rs]+oth[p]+1;

}

inline void pushdown(int p)

{

	// puts("Fuck:pushdown");

	if(!rev[p]) return;

	swap(ch[ls][0],ch[ls][1]); swap(ch[rs][0],ch[rs][1]);

	rev[ls]^=1; rev[rs]^=1; rev[p]=0;

}

void update(int p)

{

	// puts("Fuck:update");

	if(!isroot(p)) update(f[p]);

	pushdown(p);

}

void rotate(int x)

{

	// puts("Fuck:rotate");

	int y=f[x],z=f[y],k=get(x);

	if(!isroot(y)) ch[z][ch[z][1]==y]=x;

	ch[y][k]=ch[x][!k]; f[ch[y][k]]=y;

	ch[x][!k]=y; f[y]=x; f[x]=z;

	pushup(y); pushup(x);

}

void splay(int x)

{

	// puts("Fuck:splay");

	update(x);

	for(int t;t=f[x],!isroot(x);rotate(x))

	{

		if(!isroot(t)) rotate(get(x)==get(t)?t:x);

	}

}

void access(int p)

{

	// puts("Fuck:access");

    int t=0;

    while(p) splay(p),oth[p]+=sum[rs]-sum[t],rs=t,pushup(p),t=p,p=f[p];

}

void makeroot(int p)

{

	// puts("Fuck:makeroot");

	access(p); splay(p);

	swap(ls,rs); rev[p]^=1;

}

void link(int x,int y)

{

	// puts("Fuck:link");

	makeroot(x); makeroot(y);

	f[x]=y; oth[y]+=sum[x]; pushup(y);

}

int main()

{

	int n,m,x,y;

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++) sum[i]=1;

	char str[10];

	while(m--)

	{

		scanf("%s%d%d",str,&x,&y);

		if(str[0]=='A') link(x,y);

		else makeroot(x),makeroot(y),printf("%lld\n",(ll)sum[x]*(sum[y]-sum[x]));

	}

	return 0;

}

/*

8 6

A 2 3

A 3 4

A 3 8

A 8 7

A 6 5

Q 3 8

*/

小结：如果没听懂可以到JCY的blog中看一看。

巴特西

[bzoj4530][Bjoi2014]大融合_LCT

最新文章

热门文章