题目

题目链接

解题思路

提一种不需要生成树的解法。
我们将询问挂到点上，使用启发式合并的并查集。当询问的两边合并到一起时，我们就得到了答案。
整体复杂度$O(nlo{g}_{2}n)$。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;const int N = 2e5 + 100;struct node {int u, v, w;node() {}node(int u, int v, int w) :u(u), v(v), w(w) {}
}sa[N];bool operator < (node a, node b) {return a.w > b.w;
}int fa[N], aa[N], bb[N], ans[N], R;
vector<int> Q[N];int find(int x) {if (fa[x] == x) return fa[x];return fa[x] = find(fa[x]);
}void join(int x, int y) {x = find(x); y = find(y);if (x == y) return;if (Q[x].size() > Q[y].size()) swap(x, y);fa[x] = y;for (int id : Q[x]) {if (ans[id] != -1);else if (find(aa[id]) == find(bb[id])) ans[id] = R;else Q[y].push_back(id);}
}int n, m, q;int main() {//freopen("0.txt", "r", stdin);scanf("%d%d", &n, &m);for (int i = 1; i <= m; i++) scanf("%d%d%d", &sa[i].u, &sa[i].v, &sa[i].w);scanf("%d", &q);for (int i = 1; i <= q; i++) {scanf("%d%d", &aa[i], &bb[i]);Q[aa[i]].push_back(i);Q[bb[i]].push_back(i);}for (int i = 1; i <= n; i++) fa[i] = i;sort(sa + 1, sa + m + 1);memset(ans, -1, sizeof(ans));for (int i = 1; i <= m; i++) {R = sa[i].w;join(sa[i].u, sa[i].v);}for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);return 0;
}