[数据结构与算法]HDU 7136 Jumping Monkey 与 kruscal重构树

题目传送门：HDU7156

题意：
给定一棵树，有 $n$ 个点，树上每个点都有互异的一个权值 $a_i$ 。如果 $u$ 能跳到 $v$ ，那么 $u$ 到 $v$ 最短路径中没有权值比 $a_u$ 大，且 $a_v$ 比 $a_u$ 大。
问每个节点最多跳转多少次。

思考：
这道题画画图，就可以发现如果 $u$ 能够跳转到 $v$，且 $u$ 能和 $p$ 直接相连，如果 $a_v$ 小于 $a_p$，那么 $u$ 能跳转到 $v$ ，然后再跳转到 $p$ 。因为 $u$ 到 $v$ 路径上没有超过 $a_v$ 的值。
那么，仔细分析一下，可以发现终点一定是最大值点。考虑逆向过程，把最大值点删除后，分成了几个联通块。接下来就是每个联通块的最大值。
但是正向这么操作其实是不好做的，如果暴力做，在链的情况会被卡到 $O(n^2)$。所以考虑逆向去做。
逆向做就是从小到大进行重构树，将点的权值从小到大排序，依次加入每个点。枚举每个点，将该点与之相邻的联通块的根。也就是枚举每个点 $u$ ，枚举与之相邻的点 $v$ ，如果 $a_u$ 大于 $a_v$ ，那么 $v$ 是可以到 $u$ 的，所以将 $u$ 作为 $v$ 所在联通块的根。这是由于按照顺序枚举，所有比他小的点已经被枚举过了，那么与 $u$ 直接相连的联通块都是能到达 $u$ 的，而不直接相连的联通块则是不能够到达的。用并查集维护联通块，最后从最大点开始进行 $dfs$ ，那么深度就是每个点的答案。

#include<bits/stdc++.h>
#define For(aa, bb, cc) for(int aa = (bb); aa <= (int)(cc); ++aa)
using namespace std;
const int maxn = 1e5 + 10;
int n;
int b[maxn], ans[maxn], fa[maxn];
vector<int> G[maxn], P[maxn];
struct node {
	int id, w;
}a[maxn];

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

void dfs(int u, int d) {
	ans[u] = d;
	for(auto v :P[u]) dfs(v, d + 1);
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int _;
	scanf("%d", &_);
	while(_--) {
		scanf("%d", &n);
		For(i, 1, n) G[i].clear(), P[i].clear(), fa[i] = i;
		For(i, 1, n - 1) {
			int x, y;
			scanf("%d%d", &x, &y);
			G[x].push_back(y);
			G[y].push_back(x);
		}
		For(i, 1, n) {
			scanf("%d", &b[i]);
			a[i].w = b[i], a[i].id = i;
		}
		sort(a + 1, a + 1 + n, [&](node x, node y) { return x.w < y.w; });
		For(i, 1, n) {
			int x = a[i].id;
			for(auto y: G[x]) {
				if(b[y] > b[x]) continue;
				int fy = find(y);
				fa[fy] = x;
				P[x].push_back(fy);
			}
		}
		dfs(a[n].id, 1);
		For(i, 1, n) printf("%d\n", ans[i]);
	}
	return 0;
}

这道题当时和队友讨论了一下，然后队友很快就搞出了做法，我却对实现有点问题。然后当时队友提了一嘴重构树，然后我就顺便把 $kruscal$重构树学了。下面来简介一下这个比较有意思的算法。

kruscal重构树是化边为点思想，按照kruscal的做法，对边排序，每次一边的两点 $x,y$ 合并时，开辟一个新点 $u$ ，两个儿子分别是 $find(x),find(y)$，且 $val(u)=w(x,y)$。这样开辟的点数 $n?1$，那么总共就是 $2n?1$ 个点。

kruscal重构树有以下的性质：
1.是一个二叉树
2.如果是按最小生成树建立的话是一个大根堆，也可以反过来建立小根堆
3.任意两个点路径上边权的最大值为它们的LCA的点权，反过来排序的话就是最小值。

重构树直接在树上建的话，就可以得到树上路径的一些的最值信息，比较方便。

例题：bzoj3551以及NOI2018 归程