并查集的应用

周末的ccpc网络赛里面有一道题，需要用到并查集，和我之前遇到的一个问题的处理方式差不多，这里做一下总结。

首先是一道题目。

给你一棵树，n个节点。

你需要满足以下操作

0 ： 删除一个节点，并将它的儿子连接到这个节点的父节点上

1： 查询一个节点的父节点，如果这个节点已经被删除就不输出。

根节点的父节点为0

首先，我们可以想到一个暴力的做法，记录所有的节点的父节点，每删除一个节点，就遍历所有的节点，若其父节点是要删除的那个节点，就更新。

	for (int i = 1; i <= n; i++) {
		if (fa[i] == u)fa[i] = fa[u];
	}

但是这样明显是会超时的，一个 一半菊花一半链的树就可以卡掉暴力。

那怎么做呢？我们还是只需要保留每个节点的父节点，如果删除了某个节点u，我们就希望对于所有的u的儿子v，在之后我们查询v的父节点，fa[v] 会变。那么我们可以做一下映射了。（为了方便就叫hs吧）

对于这个样的一颗树

初始的时候我们有 （前面一块是fa[]代表父节点，后面是hs代表映射）

• 1 2 3 4 5 6 - 1 2 3 4 5 6
• 0 4 1 3 4 3 - 1 2 3 4 5 6

如果我要删除4这个节点，只需要 hs[4] = 3。 这样当我询问5或者2 的父节点的时候 直接 hs[fa[5/2]]即可

• 1 2 3 4 5 6 - 1 2 3 4 5 6
• 0 4 1 3 4 3 - 1 2 3 3 5 6

如果接下来我要删除3怎么办呢？可以将hs[3] = 1 但是要注意，hs[4] = 1。 也就是说接下来，hs变成了

• 1 2 3 4 5 6
• 1 2 1 1 5 6

看到这里想到了什么？当然是并查集啊。。。

while (m--) {
		cin >> op >> u;
		if (op == 0) {
			vis[u] = 1;
			uf.Union(u, uf.findFather(fa[u]));
		}
		else {
			if (!vis[u]) {
				cout << uf.findFather(fa[u]) << endl;
			}
		}
	}
//findFather是并查集的fa数组，Union合并

网络赛的题目呢？

略微的说一下做法。首先，所有的节点都可以到达权值最大的那个节点。如果权值最大的节点将整个树划分成了几个部分，那么各个部分是不能互通的（一块里面的节点必然不能跳到另一块的节点，因为隔了个权值最大的（题目里面说了，权值各不相同））

对于划分出来的那几块，可以如法炮制了，这样分下去就有答案了，我们可以看到，这样搞的最后，出来的是一颗树，每个节点的深度就是最后的答案。

我们按照权值排序，从小到大遍历。

举个例子 现在遍历到i了，而 a b c的权值都小于 i 的权值，那么 a b c 一定是可以跳到 i 的 。

接下来，遍历到 j 了，a的权值是小于 j 的，那么 a 是也可以跳到 j ，但是，也可以先跳到i 再跳到 j 因为我们是按照升序遍历的，所以 i 的权值是一定小于 j 的。同时 b c 也可以 先跳到 i 再 跳到 j

对于这个一部分我们就可以里面为是生成了这样的一棵树。

这样我们生成最后的树后，一遍dfs求深度即可。

int n;
vector<int>g[maxnum];
vector<int>gg[maxnum];
int ans[maxnum];
void dfs(int u, int f) {
	ans[u] = ans[f] + 1;
	for (int v : gg[u])dfs(v, u);
}
int u, v;
int a[maxnum];
bool cmp(int x, int y) {
	return a[x] < a[y];
}
void slove() {
	cin >> n;
	UF uf = UF(n);
	for (int i = 1; i <= n; i++)g[i].clear(), gg[i].clear(), ans[i] = 0;
	for (int i = 1; i <= n - 1; i++) {
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for (int i = 1; i <= n; i++)cin >> a[i];
	vector<int>vec; for (int i = 1; i <= n; i++)vec.push_back(i);
	sort(vec.begin(), vec.end(), cmp);
	for (int u : vec) {
		for (int v : g[u]) {
			if (a[v] < a[u]) {
				if (!uf.connect(v, u)) {
					int ft = uf.findFather(v);
					uf.Union(v, u);
					gg[u].push_back(ft);
				}
			}
		}
	}
	dfs(vec.back(), 0);
	for (int i = 1; i <= n; i++)cout << ans[i] << endl;
}

当时比赛的时候没有考虑到倒着想，一直在考虑dfs序和树链剖分（呜呜呜