BZOJ4530：[Bjoi2014]大融合

【题目描述】

小强要在N个孤立的星球上建立起一套通信系统。这套通信系统就是连接N个点的一个树。

这个树的边是一条一条添加上去的。在某个时刻，一条边的负载就是它所在的当前能够联通的树上路过它的简单路径的数量。

例如，在上图中，现在一共有了5条边。其中，(3,8)这条边的负载是6，因为有六条简单路径2-3-8,2-3-8-7,3-8,3-8-7,4-3-8,4-3-8-7路过了(3,8)。

现在，你的任务就是随着边的添加，动态的回答小强对于某些边的负载的询问。

【输入】

第一行包含两个整数N,Q，表示星球的数量和操作的数量。星球从1开始编号。

接下来的Q行，每行是如下两种格式之一：

A x y 表示在x和y之间连一条边。保证之前x和y是不联通的。

Q x y 表示询问(x,y)这条边上的负载。保证x和y之间有一条边。

1≤N,Q≤100000

【输出】

对每个查询操作，输出被查询的边的负载。

【输入样例】

【输出样例】

LCT维护子树信息的板子题，其实也很好理解。

思想还是比较简单，唯一不一样的是link的过程，因为子树不好上推所以我们干脆直接让一棵树成为另一棵树根的子树。这样就很好操作了。

维护的话就维护一个虚儿子大小和以及splay上每个点虚儿子大小和的子树和就可以了。

查询的时候相当于问cut后两边的大小乘积，这里我没有写cut。假设查询u,v。那么我们把u给makeroot，并且access掉v。这样u、v的虚儿子大小和+1就是两边的点数了。

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 5;
namespace LCT {
	struct node {
		int ch[2], fa, rv, sz, sum;
	} t[maxn];
	const int L = 0, R = 1;
	#define isrt(x) (t[t[x].fa].ch[L] != x && t[t[x].fa].ch[R] != x)
	void push_up(int rt) {
		t[rt].sum = 1 + t[t[rt].ch[L]].sum + t[t[rt].ch[R]].sum + t[rt].sz;
	}
	void push_down(int rt) {
		if(t[rt].rv) {
			swap(t[rt].ch[L], t[rt].ch[R]);
			int tl = t[rt].ch[L];
			int tr = t[rt].ch[R];
			if(tr) t[tr].rv ^= 1;
			if(tl) t[tl].rv ^= 1;
			t[rt].rv = 0;
		}
	}
	void rotate(int x) {
		int p = t[x].fa, a = t[p].fa;
		int l = t[p].ch[R] != x, r = l ^ 1;
		if(!isrt(p)) t[a].ch[t[a].ch[R] == p] = x;
		t[x].fa = a, t[p].fa = x, t[t[x].ch[l]].fa = p;
		t[p].ch[r] = t[x].ch[l], t[x].ch[l] = p;
		push_up(p), push_up(x);
	}
	void splay(int x) {
		while(!isrt(x)) {
			int p = t[x].fa, a = t[p].fa;
			push_down(a), push_down(p), push_down(x);
			if(!isrt(p))
				if((t[a].ch[R] == p) ^ (t[p].ch[R] == x)) rotate(x);
				else rotate(p);
			rotate(x);
		}
		push_down(x);
	}
	void change(int u, int v) {
		///????
		splay(u);
		t[u].sz -= t[v].sum;
		t[u].sz += t[t[u].ch[R]].sum;
		t[u].ch[R] = v;
		push_up(u);
	}
	int access(int u) {
		for(change(u, 0); t[u].fa; u = t[u].fa) 
			change(t[u].fa, u);
		while(push_down(u), t[u].ch[L]) 
			u = t[u].ch[L];
		return splay(u), u;
	}
	void makeroot(int x) {
		t[access(x)].rv ^= 1;
		splay(x);
	}
	void link(int x, int y) {
		makeroot(x), makeroot(y);
		t[x].fa = y, t[y].sz += t[x].sum;
	}
} 

char s[25];
int u, v, n, m;

int main() {
	using namespace LCT;
	scanf("%d%d", &n, &m);
	for(register int i = 1; i <= m; ++i) {
		scanf("%s", s);
		scanf("%d%d", &u, &v);
		if(s[0] == 'A') link(u, v);
		else {
			makeroot(u), access(v);
			printf("%lld\n", 1ll * (t[u].sz + 1) * (t[v].sz + 1));
		}
	}
	return 0;
}

Rockdu's Blog