洛谷 P2542 [AHOI2005]航线规划（Link-cut-tree）

题面

洛谷

 bzoj

题解

离线处理+LCT

有点像星球大战

我们可以倒着做，断边变成连边

我们可以把边变成一个点

连边时，如果两个点本身不联通，就\(val\)赋为\(1\)，并连接这条边

如果，两个点本身就联通，那么就不连接这条边，把两点之间的\(val\)全部赋为\(0\)

\(ans\)就是求两点之间的\(sum(val)\)

Code

#include<bits/stdc++.h>

#define LL long long

#define RG register

using namespace std;

inline int gi() {

	RG int x = 0; RG char c = getchar(); bool f = 0;

	while (c != '-' && (c < '0' || c > '9')) c = getchar();

	if (c == '-') c = getchar(), f = 1;

	while (c >= '0' && c <= '9') x = x*10+c-'0', c = getchar();

	return f ? -x : x;

}

const int N = 52000;

struct node {

	int ch[2], f, sum, rev, v, ly;

}t[N<<2];

bool isroot(int x) {

	return t[t[x].f].ch[0] != x && t[t[x].f].ch[1] != x;

}

inline int get(int x) {

	return t[t[x].f].ch[1] == x;

}

inline void pushup(int x) {

	t[x].sum = t[t[x].ch[0]].sum+t[t[x].ch[1]].sum+t[x].v;

}

void rotate(int x) {

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

	if (!isroot(y))

		t[z].ch[get(y)] = x;

	t[x].f = z;

	t[t[x].ch[k^1]].f = y; t[y].ch[k] = t[x].ch[k^1];

	t[y].f = x; t[x].ch[k^1] = y;

	pushup(y);

	return ;

}

int top, S[N<<2];

inline void putly(int x) {t[x].ly = 1; t[x].sum = t[x].v = 0;}

void pushdown(int x) {

	if (t[x].rev) {

		swap(t[x].ch[0], t[x].ch[1]);

		if (t[x].ch[0]) t[t[x].ch[0]].rev ^= 1;

		if (t[x].ch[1]) t[t[x].ch[1]].rev ^= 1;

		t[x].rev = 0;

	}

	if (t[x].ly) {

		if (t[x].ch[0]) putly(t[x].ch[0]);

		if (t[x].ch[1]) putly(t[x].ch[1]);

		t[x].ly = 0;

	}

	return ;

}

void splay(int x) {

	S[top=1] = x;

	for (int i = x; !isroot(i); i = t[i].f) S[++top] = t[i].f;

	for (int i = top; i; i--) pushdown(S[i]);

	while (!isroot(x)) {

		int y = t[x].f;

		if (!isroot(y))(get(x)^get(y)) ? rotate(x):rotate(y);

		rotate(x);

	}

	pushup(x);

	return ;

}

void access(int x) {for (int y=0;x;y=x,x=t[x].f) splay(x),t[x].ch[1]=y,pushup(x);}

void makeroot(int x){access(x),splay(x),t[x].rev ^= 1;}

void split(int x, int y){makeroot(x),access(y),splay(y);}

void link(int x, int y) {makeroot(x);t[x].f = y;}

int findroot(int x) {access(x); splay(x);while (t[x].ch[0]) x = t[x].ch[0];return x;}

struct Line {

	int u, v;

	bool flag;

}E[N<<2];

map<pair<int, int>, int> M;

struct question {

	int op, ans, u, v;

}q[N];

int main() {

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

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

	int n = gi(), m = gi();

	for (int i = 1; i <= m; i++) {

		int u = gi(), v = gi();

		if (u > v) swap(u, v);

		E[i] = (Line) {u, v, 0};

		t[i+n].v = 1;

		M[make_pair(u, v)] = i;

	}

	int cnt = 0;

	for (;;) {

		int c = gi(); if (c == -1) break;

		int u = gi(), v = gi(); if (u > v) swap(u, v);

		q[++cnt] = (question) {c, 0, u, v};

		if (!c) E[q[cnt].ans = M[make_pair(u, v)]].flag = 1;

	}

	for (int i = 1; i <= m; i++)

		if (!E[i].flag) {

			int u = E[i].u, v = E[i].v;

			if (findroot(u) != findroot(v))

				link(u, i+n), link(v, i+n);

			else {

				split(u, v);

				putly(v);

			}

		}

	for (int i = cnt; i; i--) {

		if (q[i].op) {

			int u = q[i].u, v = q[i].v;

			split(u, v);

			q[i].ans = t[v].sum;

		}

		else {

			int u = q[i].u, v = q[i].v;

			if (findroot(u) != findroot(v))

				link(u, q[i].ans+n), link(v, q[i].ans+n);

			else {

				split(u, v);

				putly(v);

			}

		}

	}

	for (int i = 1; i <= cnt; i++)

		if (q[i].op)

			printf("%d\n", q[i].ans);

	return 0;

}

巴特西

洛谷 P2542 [AHOI2005]航线规划（Link-cut-tree）

题面

题解

Code

最新文章

热门文章