825

[洛谷传送门](https://www.luogu.com.cn/problem/CF825G "洛谷传送门") [CF 传送门](https://codeforces.com/problemset/problem/825/G "CF 传送门") 模拟赛赛时做法。 看到查询路径点权最小值，想到建重构 ......

点权转边权，把边权设为两个端点的 $\min$，然后发现询问 $x$ 的答案，就是询问 $x$ 与所有黑点的虚树，边权的 $\min$ 是多少。假设要判定答案是否 $\geq k$，那么就是询问 $x$ 只经过 $\geq k$ 是否能到达所有黑点，于是想到建立 Kruskal 重构树，那么 $x$ ......

#include<bits/stdc++.h> using namespace std; typedef long long ll; #define endl "\n" inline int gcd(int a, int b) { return b > 0 ? gcd(b, a % b) : a; ......

偶然间翻到三个月前写的这个题，发现现有的题解均未给出解法的正确性证明，只是不明不白地写了一些对理解做法毫无帮助的话。我认为解法的正确性并不显然，因此这篇题解主要给出正确性证明，补上逻辑漏洞。 解法与其他题解一样，即：建反图，然后跑拓扑排序，每次优先取出可以取出的编号最大的点，从 $n$ 到 $1$ ......