D5 - 并查集

class Union_Find {
	int ar[maxn+1] {};
	int cnt[maxn + 1] {};
	int dis[maxn + 1] {};
	int dsu(const int x) {
		if (x != ar[x]) {
			static int fa;
			fa = dsu(ar[x]);
			dis[x] += dis[ar[x]];
			ar[x] = fa;
		}
		return ar[x];
	}
public:
	explicit Union_Find(const int n) {
		for (int i = 1; i <= n; i++) ar[i] = i;
		fill(cnt + 1, cnt + n + 1, 1);
	}
	bool query(const int x, const int y) { return dsu(x) == dsu(y); }
	void merge(const int x, const int y, const int k = 1) {	// 将y所在的集合并入x所在的集合
		static int fay;
		if (query(x, y)) return ;
		fay = dsu(y);	// 非常非常重要!!维护深度时是必要的
		dis[fay] = k;
		cnt[dsu(x)] += cnt[fay];
		ar[fay] = dsu(x);	// 必须最后更新
	}
	int size(const int x) {
		return cnt[dsu(x)];
	}
	int depth(const int x) {
		dsu(x);
		return dis[x];
	}
};