BZOJ4668: 冷战

题意：

给定 n 个点的图。动态的往图中加边，并且询问某两个点最早什

么时候联通，强制在线。

---

还可以这样乱搞

并查集按秩合并的好处：

1. 深度不会超过\(O(\log n)\)
2. 树的结构保持较稳定 -> 虽说连边的时候依旧是祖先来连边，但连边不会改变原来的结构，并且(u,v)路径上会经过新连的边

于是就可以乱搞了

维护一个按秩合并的并查集，给连边操作加时间戳，查询的时候暴力求路径上时间戳最大值

PS：暴力lca也是需要deep

PS2：按秩合并是看高度的吧，为什么我的好慢？？？人傻自带大常数？？？并且改成启发式合并我的就T掉了

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

const int N = 5e5+5;

int n, m, fa[N], val[N], he[N], deep[N], tim, ans;

int find(int x) {

	if(x == fa[x]) return x;

	else {

		int f = find(fa[x]);

		deep[x] = deep[fa[x]] + 1;

		return f;

	}

}

void Union(int x, int y) {

	tim++;

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

	if(x == y) return;

	if(he[x] < he[y]) swap(x, y);

	fa[y] = x;

	val[y] = tim;

	he[x] = max(he[x], he[y]+1);

}

void Find(int x, int y) {

	int fx = find(x), fy = find(y);

	ans = 0;

	if(fx != fy) cout << ans << '\n';

	else {

		while(x != y) {

			if(deep[x] < deep[y]) swap(x, y);

			ans = max(ans, val[x]); x = fa[x];

		}

		cout << ans << '\n';

	}

}

int main() {

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

	ios::sync_with_stdio(false); cin.tie(); cout.tie();

	cin >> n >> m;

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

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

		int c, x, y;

		cin >> c >> x >> y;

		x ^= ans; y ^= ans; //printf("hi %d %d %d\n", c, x, y);

		if(c == 0) Union(x, y);

		else Find(x, y);

	}

}