bzoj4998 星球联盟 LCT + 并查集

题目传送门

https://lydsy.com/JudgeOnline/problem.php?id=4998

题解

根据题意，就是要动态维护点双，求出一个点双的权值和。

所以这道题就是和 bzoj2959 长跑一样了，每一次枚举一条路径上的点双暴力和合并，并查集维护。

本来是想再练一练 LCT 码力的，结果又调了半天。

大概错误都有：

connect 函数的 \(fa\) 和 \(o\) 的顺序写错；
每一次把一条链合并成一个点双的时候需要把代表点的孩子删掉！！！
要把连边和 dfs 一起写，因为 dfs 的时候初始点双还没有分清楚。

时间复杂度 \(O(m\log n)\)。

#include<bits/stdc++.h>

#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)

#define dbg(...) fprintf(stderr, __VA_ARGS__)

#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)

#define fi first

#define se second

#define pb push_back

template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b, 1 : 0;}

template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b, 1 : 0;}

typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;

template<typename I> inline void read(I &x) {

	int f = 0, c;

	while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;

	x = c & 15;

	while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);

	f ? x = -x : 0;

}

const int N = 200000 + 7;

#define lc c[0]

#define rc c[1]

int n, m, Q, tp, dfc, bccno;

int a[N], st[N], stt[N], dfn[N], low[N], bcc[N];

int fa[N];

struct Edge { int to, ne; } g[N << 1]; int head[N], tot = 1;

inline void addedge(int x, int y) { g[++tot].to = y, g[tot].ne = head[x], head[x] = tot; }

inline void adde(int x, int y) { addedge(x, y), addedge(y, x); }

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

struct Node { int c[2], fa, rev, v, s, sum; } t[N];

inline bool isroot(int o) { return t[find(t[o].fa)].lc != o && t[find(t[o].fa)].rc != o; }

inline bool idtfy(int o) { return t[find(t[o].fa)].rc == o; }

inline void connect(int fa, int o, int d) { t[fa].c[d] = o, t[o].fa = fa; }

inline void pushup(int o) {

	assert(find(o) == o);

	t[o].s = t[t[o].lc].s + t[t[o].rc].s + 1;

	t[o].sum = t[t[o].lc].sum + t[t[o].rc].sum + t[o].v;

}

inline void pushdown(int o) {

	if (!t[o].rev) return;

	if (t[o].lc) t[t[o].lc].rev ^= 1, std::swap(t[t[o].lc].lc, t[t[o].lc].rc);

	if (t[o].rc) t[t[o].rc].rev ^= 1, std::swap(t[t[o].rc].lc, t[t[o].rc].rc);

	t[o].rev = 0;

}

inline void rotate(int o) {

	assert(find(o) == o);

	assert(!isroot(o));

	int fa = find(t[o].fa), pa = find(t[fa].fa), d1 = idtfy(o), d2 = idtfy(fa), b = t[o].c[d1 ^ 1];

//	dbg("o = %d, fa = %d, pa = %d, d1 = %d, d2 = %d, b = %d\n", o, fa, pa, d1, d2, b);

	if (!isroot(fa)) t[pa].c[d2] = o; t[o].fa = pa;

	connect(o, fa, d1 ^ 1), connect(fa, b, d1);

	pushup(fa), pushup(o);

	assert(!t[0].lc && !t[0].rc);

	assert(t[o].fa != o), assert(t[b].fa != b), assert(t[fa].fa != fa), assert(t[pa].fa != pa);

}

inline void splay(int o) {

//	dbg("splay: o = %d, t[o].fa = %d\n", o, t[o].fa);

	int x = o, tp = 0;

	stt[++tp] = x;

 	while (!isroot(x)) /*dbg("splay_stakc: o = %d, x = %d, t[x].fa = %d, find(t[x].fa) = %d\n", o, x, t[x].fa, find(t[x].fa)), */stt[++tp] = x = find(t[x].fa);

	while (tp) pushdown(stt[tp--]);

	while (!isroot(o)) {

		int fa = find(t[o].fa);

//		dbg(": o = %d, fa = %d, isroot(o) = %d, isroot(fa) = %d\n", o, fa, (int)isroot(o), (int)isroot(fa));

		if (isroot(fa)) rotate(o);

		else if (idtfy(o) == idtfy(fa)) rotate(fa), rotate(o);

		else rotate(o), rotate(o);

	}

}

inline void access(int o) {

//	dbg("**** begin access, o = %d\n", o);

	for (int x = 0; o; o = find(t[x = o].fa))

		splay(o), t[o].rc = x, pushup(o);

//	dbg("**** end access\n");

}

inline void mkrt(int o) {

	access(o), splay(o);

	t[o].rev ^= 1, std::swap(t[o].lc, t[o].rc);

}

inline int getrt(int o) {

	access(o), splay(o);

	while (pushdown(o), t[o].lc) o = t[o].lc;

	return splay(o), o;

}

inline void link(int x, int y) {

//	dbg("x = %d, y = %d\n", x, y);

	mkrt(x);

	if (getrt(y) != x) t[x].fa = y;

}

inline void dfs1(int x, int fr = 0) {

//	dbg("x = %d, fr = %d\n", x, fr);

	dfn[x] = low[x] = ++dfc, st[++tp] = x;

	for fec(i, x, y) if ((i ^ fr) != 1) {

		if (!dfn[y]) dfs1(y, i), smin(low[x], low[y]);

		else if (!bcc[y]) smin(low[x], dfn[y]);

	}

	if (dfn[x] == low[x]) {

		++bccno;

		while (1) {

			int y = st[tp--];

			bcc[y] = bccno, fa[y] = x, x != y && (t[x].v += t[y].v);

//			dbg("is bcc : x = %d, y = %d, tp = %d, st* = %d\n", x, y, tp, st[1]);;

			if (x == y) break;

		}

		pushup(x);

	}

}

inline void dfs2(int o) {

	if (!o) return;

	assert(find(o) == o);

	pushdown(o);

	dfs2(t[o].lc);

	st[++tp] = o;

	dfs2(t[o].rc);

}

inline void work() {

	for (int i = 1; i <= n; ++i) if (!dfn[i]) dfs1(i);

	for (int x = 1; x <= n; ++x) for fec(i, x, y) link(find(x), find(y));

//	dbg("*****\n");

	while (Q--) {

		int x, y;

		read(x), read(y);

//		dbg("x = %d, y = %d\n", x, y);

		x = find(x), y = find(y);

		if (getrt(x) != getrt(y)) link(x, y), puts("No");

		else if (x == y) printf("%d\n", t[x].v);

		else {

//			dbg("query : x = %d, y = %d\n", x, y);

			mkrt(x), access(y), splay(y);

			tp = 0, dfs2(y);

			for (int i = 1; i < tp; ++i) t[st[tp]].v += t[st[i]].v, fa[st[i]] = st[tp];

			t[st[tp]].lc = 0, pushup(st[tp]), printf("%d\n", t[st[tp]].v);

//			dbg("************* x = %d, y = %d, st[1] = %d, %d\n", x, y, st[tp], t[st[tp]].fa);

		}

	}

}

inline void init() {

	read(n), read(m), read(Q);

	int x, y;

	for (int i = 1; i <= m; ++i) read(x), read(y), adde(x, y);

	for (int i = 1; i <= n; ++i) fa[i] = i, t[i].v = 1, pushup(i);

}

int main() {

#ifdef hzhkk

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

#endif

	init();

	work();

	fclose(stdin), fclose(stdout);

	return 0;

}

巴特西

bzoj4998 星球联盟 LCT + 并查集

题目传送门

题解

最新文章

热门文章